高中数学人教版必修三讲读设计：1．3 算法案例

编制人 审 核 人 主讲人 评价等级
班 别 学生姓名 组 别 学习日期
1.3 算法案例 讲读设计
教学目标：
1.理解辗转相除法与更相减损术中蕴含的数学原理，并能根据这些原理进行算法分析。
2.理解秦九韶算法与进位制中蕴含的数学原理，并能根据这些原理进行算法分析。
3.基本能根据算法语句与程序框图的知识设计完整的程序框图并写出算法程序.
教学重点：根据原理进行算法分析.
教学难点：设计完整的程序框图并写出算法程序.
教学过程：
一、预习反馈
（预习教材，找出疑惑之处）

二、学习目标
1.理解辗转相除法与更相减损术中蕴含的数学原理，并能根据这些原理进行算法分析。
2.理解秦九韶算法与进位制中蕴含的数学原理，并能根据这些原理进行算法分析。
3.基本能根据算法语句与程序框图的知识设计完整的程序框图并写出算法程序.
(一)自学提示 整合教材知识,落实基本能力
探究一：辗转相除法
问题： 求两个正数8251和6105的最大公约数。
（分析：8251与6105两数都比较大，而且没有明显的公约数，如能把它们都变小一点，根据已有的知识即可求出最大公约数）
解：8251＝6105×1＋2146
显然8251的最大公约数也必是2146的约数，同样6105与2146的公约数也必是8251的约数，所以8251与6105的最大公约数也是6105与2146的最大公约数。
6105＝2146×2＋1813
2146＝1813×1＋333
1813＝333×5＋148
333＝148×2＋37
148＝37×4＋0
则37为8251与6105的最大公约数。
新知1：以上我们求最大公约数的方法就是辗转相除法。也叫欧几里德算法，它是由欧几里德在公元前300年左右首先提出的。利用辗转相除法求最大公约数的步骤如下：
第一步：用较大的数m除以较小的数n得到一个商q0和一个余数r0；
第二步：若r0＝0，则n为m，n的最大公约数；若r0≠0，则用除数n除以余数r0得到一个商q1和一个余数r1；
第三步：若r1＝0，则r1为m，n的最大公约数；若r1≠0，则用除数r0除以余数r1得到一个商q2和一个余数r2；……
依次计算直至rn＝0，此时所得到的rn－1即为所求的最大公约数。

探究二：更相减损术
问题：用更相减损术求98与63的最大公约数.
解：由于63不是偶数，把98和63以大数减小数，并辗转相减，即：98－63＝35
63－35＝28
35－28＝7
28－7＝21
21－7＝14
14－7＝7
所以，98与63的最大公约数是7。
新知2：我国早期也有解决求最大公约数问题的算法，就是更相减损术。更相减损术求最大公约数的步骤如下：可半者半之，不可半者，副置分母·子之数，以少减多，更相减损，求其等也，以等数约之。
翻译出来为：
第一步：任意给出两个正数；判断它们是否都是偶数。若是，用2约简；若不是，执行第二步。
第二步：以较大的数减去较小的数，接着把较小的数与所得的差比较，并以大数减小数。继续这个操作，直到所得的数相等为止，则这个数（等数）就是所求的最大公约数。

探究三：秦九韶算法
新知3：我们已经学过了多项式的计算，下面我们计算一下多项式f(x)=x5+x4+x3+x2+x+1当x=5时的值，并统计所做的计算的种类及计算次数。根据我们的计算统计可以得出我们共需要____次乘法运算，______次加法运算。
我们把多项式变形为：f(x)= x2(1+x(1+x(1+x)))+x+1,再统计一下计算当x=5时的值时需要的计算次数，可以得出仅需____次乘法和_____次加法运算即可得出结果。显然少了_____次乘法运算。这种算法就叫秦九韶算法。
秦九韶计算多项式的方法：（详见教材37页。）

探究四：进位制
进位制是一种记数方式，用有限的数字在不同的位置表示不同的数值。可使用数字符号的个数称为基数，基数为n，即可称n进位制，简称n进制。现在最常用的是十进制，通常使用10个阿拉伯数字0-9进行记数。
问题1：把二进制数110011(2)化为十进制数.
解:110011=1×25+1×24+0×23+1×24+0×22+1×21+1×20
=32+16+2+1=51
问题2：把89化为二进制数.
解:根据二进制数满二进一的原则,可以用2连续去除89或所得商,然后取余数.
具体的计算方法如下:
89=2×44+1
44=2×22+0
22=2×11+0
11=2×5+1
5=2×2+1
所以:89=2×(2×(2×(2×(2×2+1)+1)+0)+0)+1
=1×26+0×25+1×24+1×23+0×22+0×21+1×20=1011001(1)
这种算法叫做除2取余法,还可以用下面的除法算式表示:

把上式中的各步所得的余数从下到上排列即可得到89=1011001(2)
新知4：上述方法也可以推广为把十进制化为k进制数的算法,这种算法成为除k取余法.

(二)合作探讨
例1利用辗转相除法求两数4081与20723的最大公约数。




例2 用更相减损术求两个正数84与72的最大公约数。





思考：比较辗转相除法与更相减损术的区别。
结论：（1）都是求最大公约数的方法，计算上辗转相除法以除法为主，更相减损术以减法为主，计算次数上辗转相除法计算次数相对较少，特别当两个数字大小区别较大时计算次数的区别较明显。
（2）从结果体现形式来看，辗转相除法体现结果是以相除余数为0则得到，而更相减损术则以减数与差相等而得到
练1.用辗转相除法求下列各组数的最大公约数。
（1）225；135 （2）98；196



练2.用更相减损术求两个正数96与70的最大公约数。



例1.已知一个5次多项式为f(x)=4x5+2x4+3.5x3-2.6x2+1.7x-0.8用秦九韶算法求这个多项式当x=5时的值。





思考：（1）例1计算时需要多少次乘法运算？多少次加法计算？（2）在利用秦九韶算法运算n次多项式当x=x0时需要多少次乘法运算和多少次加法运算？

例2. (1)把二进制数110 011(2)化为十进制数； (2)把89化为二进制数.







练1.把73转换为二进制数。 练2.利用除k取余法把89转换为5进制数。







四、当堂检测
1.我国古代数学发展一直处于世界领先水平，特别是宋、元时期的“算法”，其中可以同欧几里得辗转相除法相媲美的是（ ）
A.中国剩余定理 B.更相减损术 C.割圆术 D.秦九韶算法
2. 840和1764的最大公约数是（ ）
A．84 B．12 C．168 D．252
3. 用辗转相除法求下列各组数的最大公约数。
（1）72；168 （2）153；119




4. 把89化成五进制的末尾数是 （ ）
A．1 B．2 C ．3 D ．4
5.用秦九韶算法计算多项式
在时的值时,的值为 ( )
A. －845 B. 220 C. －57 D. 34
6. 下列各数中最小的数是 ( )
A. B. C. D.
7.利用秦九韶算法计算
当时的值（要求写出详细过程），并统计需要______次乘法运算和________次加法运算？

五、归纳小结

六、课后作业 见练习册


7、板书设计

八、课后反思