tceic.com
学霸学习网 这下你爽了
相关标签
当前位置:首页 >> 数学 >>

1.3算法案例教案


考试指南报——课堂网(www.k45.cn)

算法案例
一. 【课标要求】
通过阅读中国古代数学中的算法案例,体会中国古代数学对世界数学发展的贡献。

二. 【命题走向】
算法是高中数学新课程中的新增内容, 本讲的重点是几种重要的算法案例思想, 复习时 重算法的思想轻算法和程序的构造。 预测 2010 年高考队本讲的考察是:以选择题或填空题的形式出现,分值在 5 分左右, 考察的热点是算法实例和传统数学知识的结合题目

三. 【要点精讲】
1.求最大公约数 (1)短除法 求两个正整数的最大公约数的步骤: 先用两个数公有的质因数连续去除, 一直除到所得 的商是两个互质数为止,然后把所有的除数连乘起来 (2)穷举法(也叫枚举法) 穷举法求两个正整数的最大公约数的解题步骤:从两个数中较小数开始由大到小列举, 直到找到公约数立即中断列举,得到的公约数便是最大公约数 (3)辗转相除法 辗转相除法求两个数的最大公约数,其算法可以描述如下: ① 输入两个正整数 m 和 n; ② 求余数 r:计算 m 除以 n,将所得余数存放到变量 r 中; ③更新被除数和余数:m=n,n=r; ④判断余数 r 是否为 0。若余数为 0,则输出结果;否则转向第②步继续循环执行 如此循环,直到得到结果为止。 (4)更相减损术 我国早期也有解决求最大公约数问题的算法,就是更相减损术。在《九章算术》中记载 了更相减损术求最大公约数的步骤: 可半者半之,不可半者,副置分母? 子之数,以少减多, 更相减损,求其等也,以等数约之 步骤: Ⅰ.任意给出两个正数;判断它们是否都是偶数。若是,用 2 约简;若不是,执行第二 步。 Ⅱ.以较大的数减去较小的数,接着把较小的数与所得的差比较,并以大数减小数。继 续这操作,直到所得的数相等为止,则这个数(等数)就是所求的最大公约数。 2.秦九韶算法 秦九韶算法的一般规则: 秦九韶算法适用一般的多项式 f(x)=anxn+an-1xn-1+….+a1x+a0 的求值问题。用秦九韶算法求 一般多项式 f(x)= anxn+an-1xn-1+….+a1x+a0 当 x=x0 时的函数值, 可把 n 次多项式的求值问题转化 成求 n 个一次多项式的值的问题,即求 v0=an v1=anx+an-1 v2=v1x+an-2 v3=v2x+an-3 …….. vn=vn-1x+a0
编辑部地址:武汉市前三眼桥 85 号(430000) 联系电话:027—85789995

考试指南报——课堂网(www.k45.cn)

观察秦九韶算法的数学模型,计算 vk 时要用到 vk-1 的值,若令 v0=an。 我们可以得到下面的递推公式: v0=an vk=vk-1+an-k(k=1,2,…n) 这是一个在秦九韶算法中反复执行的步骤,可以用循环结构来实现 3.进位制 (1)概念 进位制是一种记数方式, 用有限的数字在不同的位置表示不同的数值。 可使用数字符号 的个数称为基数,基数为 n,即可称 n 进位制,简称 n 进制。现在最常用的是十进制,通常 使用 10 个阿拉伯数字 0—9 进行记数。 对于任何一个数,我们可以用不同的进位制来表示。比如:十进数 57,可以用二进制 表示为 111001,也可以用八进制表示为 71、用十六进制表示为 39,它们所代表的数值都是 一样的。 一般地,若 k 是一个大于一的整数,那么以 k 为基数的 k 进制可以表示为:

an an?1...a1a0( k )

(0 ? an ? k ,0 ? an?1,..., a1, a0 ? k ) ,

而表示各种进位制数一般在数字右下脚加注来表示 ,如 111001(2)表示二进制数,34(5)表 示 5 进制数。 (2)进位制间的转换 关于进位制的转换, 教科书上以十进制和二进制之间的转换为例讲解, 并推广到十进制 和其它进制之间的转换。 这样做的原因是, 计算机是以二进制的形式进行存储和计算数据的, 而一般我们传输给计算机的数据是十进制数据, 因此计算机必须先将十进制数转换为二进制 数,再处理,显然运算后首次得到的结果为二进制数,同时计算机又把运算结果由二进制数 转换成十进制数输出。 非十进制数转换为十进制数比较简单,只要计算下面的式子值即可:

an an?1.....a1a0 (k ) ? an ? k n ? an?1 ? k n?1 ? .........? a1 ? k ? a0
第一步:从左到右依次取出 k 进制数 anan ?1..... a1a0 (k ) 各位上的数字,乘以相应的 k 的幂, k 的幂从 n 开始取值,每次递减 1,递减到 0,即 an ? k n , an?1 ? k n?1 ,......... , a1 ? k , a0 ? k 0 ; 第二步:把所得到的乘积加起来,所得的结果就是相应的十进制数。 十进制数转换成非十进制数 把十进制数转换为二进制数,教科书上提供了“除 2 取余法” ,我们可以类比得到十进 制数转换成 k 进制数的算法“除 k 取余法” 。 非十进制之间的转换 一个自然的想法是利用十进制作为桥梁。教科书上提供了一个二进制数据与 16 进制数 据之间的互化的方法,也就是先有二进制数转化为十进制数,再由十进制数转化成为 16 进 制数。

四. 【典例解析】
题型 1:求最大公约数 例 1. (1)用辗转相除法求 123 和 48 的最大公约数? (2)用更相减损来求 80 和 36 的最大公约数? 解析:(1)辗转相除法求最大公约数的过程如下:(建立带余除式)
编辑部地址:武汉市前三眼桥 85 号(430000) 联系电话:027—85789995

考试指南报——课堂网(www.k45.cn)

123=2×48+27 48=1×27+21 27=1×21+6 21=3×6+3 6=2×3+0 最后 6 能被 3 整除,得 123 和 48 的最大公约数为 3。 (2)分析:我们将 80 作为大数,36 作为小数,执行更相减损术来求两数的最大公约 数。执行结束的准则是减数和差相等 更相减损术: 因为 80 和 36 都是偶数,要去公因数 2。 80÷2=40,36÷2=18; 40 和 18 都是偶数,要去公因数 2。 40÷2=20,18÷2=9 下面来求 20 与 9 的最大公约数, 20-9=11 11-9=2 9-2=7 7-2=5 5-2=3 3-2=1 2-1=1 可得 80 和 36 的最大公约数为 22×1=4。 点评:对比两种方法控制好算法的结束,辗转相除法是到达余数为 0,更相减损术是到 达减数和差相等。 例 2.设计一个算法,求出 840 与 1764 的最大公因数。 解析: 我们已经学习过了对自然数的素因数分解的方法, 下面的算法就是在此基础上设 计的。 解题思路如下: 首先对两个数进行素因数分解: 840=23×3×5×7,1764=22×32×72, 其次,确定两个数的公共素因数:2,3,7。 接着确定公共素因数的指数:对于公共素因数 2,840 中为 23,1764 中为 22,应取较少 的一个 22,同理可得下面的因数为 3 和 7。 算法步骤: 第一步:将 840 进行素数分解 23×3×5×7; 第二步:将 1764 进行素数分解 22×32×72; 第三步:确定它们的公共素因数:2,3,7; 第四步:确定公共素因数 2,3,7 的指数分别是:2,1,1; 第五步:最大公因数为 22×31×71=84。 点评:质数是除1以外只能被1和本身整除的正整数,它应该是无限多个,但是目前没 有一个规律来确定所有的质数 题型 2:秦九韶算法 例 3. (2009 福州模拟)如果执行右面的程序框图,那么输出的 S ? ( )
编辑部地址:武汉市前三眼桥 85 号(430000) 联系电话:027—85789995

考试指南报——课堂网(www.k45.cn)

开始
i ? 1, s ? 1
i ? i ?1

s ? 2(s ? 1)
i ? 5?

输出s



结束

A.22 B.46 C. 94 D.190 答案 C 2、 (2009 浙江卷理)某程序框图如图所示,该程序运行后输出的 k 的 值是 A. 4 B. 5 ( ) C. 6 D. 7

【解析】对于 k ? 0, s ? 1,? k ? 1 ,而对于 k ? 1, s ? 3,? k ? 2 ,则

k ? 2, s ? 3 ? 8,? k ? 3 ,后面是 k ? 3, s ? 3 ? 8 ? 211,? k ? 4 ,不
符合条件时输出的 k ? 4 . 答案 A

3、 (2009 天津卷理)阅读上(右)图的程序框图,则输出的 S= ( A 26 B 35 C 40 D 57

)

【解析】当 i ? 1 时, T ? 2, S ? 2 ;当 i ? 2 时, T ? 5, S ? 7 ;当 i ? 3 时, T ? 8, S ? 15 ;当 i ? 4 时, T ? 11, S ? 26 ;当 i ? 5 时,

T ? 14, S ? 40 ;当 i ? 6 时, T ? 17, S ? 57 ,故选择 C。
编辑部地址:武汉市前三眼桥 85 号(430000) 联系电话:027—85789995

考试指南报——课堂网(www.k45.cn)

答案



4(2009 安徽卷文)程序框图上(右)(即算法流程图)如图所示,其输入结果是_______。

【解析】根据流程图可得 a 的取值依次为 1、3、7、15、31、63?? 答案 127 点评:秦九韶算法适用一般的多项式 f(x)=anxn+an-1xn-1+….+a1x+a0 的求值问题。直接法乘 法运算的次数最多可到达

( n ? 1) n , 加法最多 n 次。 秦九韶算法通过转化把乘法运算的次数 2

减少到最多 n 次,加法最多 n 次。 例 4.已知多项式函数 f(x)=2x5-5x4-4x3+3x2-6x+7,求当 x=5 时的函数的值。 解析:把多项式变形为:f(x)= 2x5-5x4-4x3+3x2-6x+7 =((((2x-5)x-4)x+3)x-6)x+7 计算的过程可以列表表示为: 多项式 x 系数 运算所得的值 变形后 x 的"系数" 2 2 -5 10 -4 25 3 105 -6 540 7 2670 运算 + *5

5

21

108

534

2677

最后的系数 2677 即为所求的值 算法过程: v0=2 v1=2×5-5=5 v2=5×5-4=21 v3=21×5+3=108 v4=108×5-6=534 v5=534×5+7=2677
编辑部地址:武汉市前三眼桥 85 号(430000) 联系电话:027—85789995

考试指南报——课堂网(www.k45.cn)

点评:如果多项式函数中有缺项的话,要以系数为 0 的项补齐后再计算。 题型 3:进位值 例 5.把十进制数 89 化为三进制数,并写出程序语句. 解析:具体的计算方法如下: 89=3×29+2 29=3×9+2 9=3×3+0 3=3×1+0 1=3×0+1 所以:89(10)=1011001(3)。 点评:根据三进制数满三进一的原则,可以用 3 连续去除 89 及其所的得的商,然后按 倒序的先后顺序取出余数组成数据即可。 例 6.将 8 进制数 314706(8)化为十进制数,并编写出一个实现算法的程序。 解析:314706(8)=3×8 +1×8 +4×8 +7×8 +0×8 +6×8 =104902。 所以,化为十进制数是 104902。 点评: 利用把 k 进制数转化为十进制数的一般方法就可以把 8 进制数 314706(8)化为十进制数,然后根据该算法,利用 GET 函数,应用循环结 构可以设计程序。
5

4

3

2

1

0

开始

输入:m,n

五. 【思维总结】
1.求最大公约数 (1)辗转相除法 程序框图与程序语句 程序: INPUT “m,n=”;m,n DO r=m MOD n m=n n=r LOOP UNTIL r=0 PRINT END N

r=m MOD n m=n

n=r

r=0? Y 输出:

开始

(2)更相减损术 更相减损术程序: INPUT “请输入两个不相等的正整数” ;a,b i=0
编辑部地址:武汉市前三眼桥 85 号(430000) 联系电话:027—85789995

考试指南报——课堂网(www.k45.cn)

WHILE a MOD 2=0 AND b MOD 2=0 a=a/2 b=b/2 i=i+1 WEND DO IF b<a THEN t=a a=b b=t END IF c=a-b a=b b=c LOOP UNTIL a=b PRINT a^i END 对于两个正整数如何选择合适的方法求他们的最大公约数 方法 短除法 穷举法 辗转相除法 更相减损术 适用范围及特点 适合两个较小的正整数或两个质因数较少的正整数,简便易操作。 适合计算机操作,但一一验证过于繁琐。 适用于两个较大的正整数,以除法为主,辗转相除法计算次数相对较少,特 别当两个数字大小差别较大时计算次数较明显。 适用于两个较大的正整数,更相减损术以减法为主,计算次数上相对于辗转 相处法较多。

2.我们以这个 5 次多项式函数为例加以说明,设: f(x)=a5x5+a4x4+a3x3+a2x2+a1x+a0 首先,让我们以 5 次多项式一步步地进行改写: f(x)=(a5x4+a4x3+a3x2+a2x+a1)x+a0 =( (a5x3+a4x2+ a3x+a2)x+a1)x+a0 =( ( (a5x2+a4x+ a3)x+a2)x+a1)x+a0 =( ( ( (a5x+a4)x+ a3)x+a2)x+a1)x+a0 上面的分层计算。 只用了小括号, 计算时, 首先计算最内层的括号, 然后由里向外逐层计算, 直到最外层的括号,然后加上常数项即可。

开始

输入 a1,a2,a3,a4,a5,x0

n=1,v=v5

编辑部地址:武汉市前三眼桥 85 号(430000 ) ×x0+a v=v

n≤6?

5-n

联系电话:027 —85789995 n=n+1

输出 v

考试指南报——课堂网(www.k45.cn)

编辑部地址:武汉市前三眼桥 85 号(430000)

联系电话:027—85789995


推荐相关:

1.3_算法案例

1.3_算法案例_高一数学_数学_高中教育_教育专区。1.3 算法案例 教学分析 在学生学习了算法的初步知识, 理解了表示算法的算法步骤、 程序框图和程序三种不同 ...


数学:1.3 《算法案例》教案(新人教A版必修3)

数学:1.3 《算法案例》教案(新人教A版必修3)_数学_高中教育_教育专区。1.3 《算法案例》教案 1.3 算法案例 第一、二课时 辗转相除法与更相减损术 (1)...


1.3算法案例教案

1.3算法案例教案_数学_高中教育_教育专区。算法案例 (第一课时) 教学目标 掌握求最大公约数的方法:辗转相除法、更相减损术 教学重点 辗转相除法、更相减损术 ...


人教版高中数学必修三《1.3算法案例(教、学案)

临清三中数学组 编写人:赵万龙 审稿人: 郭振宇 李怀奎 1.3 算法案例教学目标】 : 1.理解辗转相除法与更相减损术中蕴含的数学原理,并能根据这些原理进行算...


《算法案例(1)》教学设计

算法案例(1) 》教学设计 教学目标 (1)介绍中国古代算法的案例-韩信点兵-孙子问题; (2)用三种方法熟练的表示个算法; (3)让学生感受算法的意义和价值. ...


1.3 算法案例 教学设计2

人教A 版高中数学必修三第一章教学 课题 课程 类型 课时 《算法案例教学设计 2 1.3.2 秦九韶算法新授课 一课时 教学 重点 1.秦九韶算法的特点 2.两种...


《1.3算法案例(1)》教学案-公开课-优质课(人教A版必修...

1.3算法案例(1)》教学案-公开课-优质课(人教A版必修三精品)_高一数学_数学_高中教育_教育专区。《1.3算法案例(1) 》教学案 (1)教学目标 (a)知识与...


算法案例教学设计

算法案例教学设计秦九韶算法 浙江省黄岩中学 一、 教材分析本节内容选自《普通高中课程标准实验教科书数学 3 必修本(A 版) 》第一章 1.3 算 法案例。算法...


1.3 算法案例 教学设计2 (1)

人教A 版高中数学必修三第一章教学 课题 课程 类型 课时 《算法案例教学设计 2 1.3.2 秦九韶算法新授课 一课时 教学 重点 1.秦九韶算法的特点 2.两种...


《1.4算法案例(3)》教案

《1.4算法案例(3)》教案_高一数学_数学_高中教育_教育专区。《算法案例(3) 》教案 教学目标: 1.了解这种方法是求方程近似解的一般方法,能利用计算器求精确到...

网站首页 | 网站地图
All rights reserved Powered by 学霸学习网 www.tceic.com
copyright ©right 2010-2021。
文档资料库内容来自网络,如有侵犯请联系客服。zhit325@126.com