1.3 算法案例 学案4（无答案）

1.3
算法案例
学案
学习目标
1.理解辗转相除法与更相减损术中蕴含的数学原理，并能根据这些原理进行算法分析.
2.基本能根据算法语句与程序框图的知识设计完整的程序框图并写出算法程序.
学习过程
一、课前准备
(预习教材P34~
P36，找出疑惑之处)
问题1:在初中，我们已经学过求最大公约数的知识，你能求出18与30的公约数吗？
问题2:如果公约数比较大而且根据我们的观察又不能得到一些公约数，我们又应该怎样求它们的最大公约数？比如求8251与6105的最大公约数？
二、新课导学
※
探索新知
探究：辗转相除法
问题：
求两个正数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约简；若不是，执行第二步.
第二步：以较大的数减去较小的数，接着把较小的数与所得的差比较，并以大数减小数.继续这个操作，直到所得的数相等为止，则这个数(等数)就是所求的最大公约数.
※
典型例题
例1利用辗转相除法求两数4081与20723的最大公约数.
例2
用更相减损术求两个正数84与72的最大公约数.
思考：比较辗转相除法与更相减损术的区别.
结论：(1)都是求最大公约数的方法，计算上辗转相除法以除法为主，更相减损术以减法为主，计算次数上辗转相除法计算次数相对较少，特别当两个数字大小区别较大时计算次数的区别较明显.
(2)从结果体现形式来看，辗转相除法体现结果是以相除余数为0则得到，而更相减损术则以减数与差相等而得到
探究：写出辗转相除法与更相减损术计算的程序框图及程序.
※
动手试试
练1.用辗转相除法求下列各组数的最大公约数.
(1)225；135
(2)98；196
练2.
用更相减损术求两个正数96与70的最大公约数.
三、总结提升
※
学习小结
本课学习了辗转相除法与更相减损术求最大公约数的计算方法及完整算法程序的编写.
※
知识拓展
利用辗转相除法与更相减损术的计算算法，我们可以设计出程序框图以及BSAIC程序来在计算机上实现辗转相除法与更相减损术求最大公约数，下面由同学们设计相应框图并相互之间检查框图与程序的正确性.
学习评价
※
当堂检测
1.我国古代数学发展一直处于世界领先水平，特别是宋、元时期的“算法”，其中可以同欧几里得辗转相除法相媲美的是(
)
A.中国剩余定理
B.更相减损术
C.割圆术
D.秦九韶算法
2.
840和1764的最大公约数是(
)
A．84
B．12
C．168
D．252
3.
用辗转相除法求下列各组数的最大公约数.
(1)72；168
(2)153；119
课后作业
1.用辗转相除法或者更相减损术求三个数
324
，
243
，
135
的最大公约数.
2.教材48页第1题.