1.3辗转相除法
图片预览
文档简介
课件21张PPT。1.3 算法案例 第一课时 问题提出 1.研究一个实际问题的算法，主要从算法步骤、程序框图和编写程序三方面展开.在程序框图中算法的基本逻辑结构有哪三种？在程序设计中基本的算法语句有哪五种？ 2.“求两个正整数的最大公约数”是数学中的一个基础性问题，它有各种解决办法，我们以此为案例，对该问题的算法作一些探究.辗转相除法与
更相减损术知识探究（一）:辗转相除法思考1:18与30的最大公约数是多少？你是怎样得到的？ 先用两个数公有的质因数连续去除，一直除到所得的商是互质数为止，然后把所有的除数连乘起来即为最大公约数. 思考2:对于8251与6105这两个数，由于其公有的质因数较大，利用上述方法求最大公约数就比较困难.注意到:
8251=6105×1+2146
那么8251与6105这两个数的公约数和6105与2146的公约数有什么关系？
思考3:又6105=2146×2+1813，同理，6105与2146的公约数和2146与1813的公约数相等.重复上述操作，你能得到8251与6105这两个数的最大公约数吗？2146=1813×1+333，148=37×4+0.333=148×2+37，1813=333×5+148，8251=6105×1+2146，6105=2146×2+1813，练习1 用辗转相除法求最大公约数（1）378 90
（2）90 36
（3）16 12
（4）228 1995思考4:上述求两个正整数的最大公约数的方法称为辗转相除法或欧几里得算法.一般地，用辗转相除法求两个正整数m，n的最大公约数，可以用什么逻辑结构来构造算法？其算法步骤如何设计？ 第一步，给定两个正整数m，n(m>n).第二步，计算m除以n所得的余数r. 第三步，m=n，n=r.第四步，若r=0，则m，n的最大公约数等 于m；否则，返回第二步. 思考5:该算法的程序框图如何表示？思考6:该程序框图对应的程序如何表述？INPUT m，nDOr=m MOD nm=nn=rLOOP UNTIL r=0PRINT mENDINPUT m，nWHILE n<>0r=m MOD nm=nn=rWENDPRINT mEND思考7:用当型循环结构构造算法:“更相减损术”在中国古代数学专著《九章算术》中记述为：可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也，以等数约之. 知识探究（二）:更相减损术 第一步：任意给定两个正整数；判断他们是否都是偶数。若是，则用2约简；若不是则执行第二步。第二步：以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止，则这个等数就是所求的最大公约数。思考1:求98与63的最大公约数？98-63=3514-7=721-7=1428-7=2135-28=763-35=28练习2用更相减损术求最大公约数（1）28 13
（2）90 36
（3）16 12理论迁移 例1 分别用辗转相除法和更相减损术求168与93的最大公约数. 辗转相除法：168=93×1+75， 93=75×1+18， 75=18×4+3， 18=3×6+0.更相减损术:168-93=75，
93-75=18，
75-18=57，
57-18=39，
39-18=21，
21-18=3，
18-3=15，
15-3=12，
12-3=9，
9-3=6，
6-3=3. 例3 求325，130，270三个数的最大公约数. 因为325=130×2+65，130=65×2，所以325与130的最大公约数是65. 因为270=65×4+10，65=10×6+5，10=5×2+0，所以65与270最大公约数是5. 故325，130，270三个数的最大公约数是5.练习3 求319，377，116三个数的最大公约数. 1.辗转相除法，就是对于给定的两个正整数，用较大的数除以较小的数，若余数不为零，则将余数和较小的数构成新的一对数，继续上面的除法，直到大数被小数除尽为止，这时的较小的数即为原来两个数的最大公约数. 小结作业 2. 更相减损术，就是对于给定的两个正整数，用较大的数减去较小的数，然后将差和较小的数构成新的一对数，继续上面的减法，直到差和较小的数相等，此时相等的两数即为原来两个数的最大公约数.比较辗转相除法与更相减损术的区别 1.都是求最大公约数的方法，计算上辗转相除法以除法为主，更相减损术以减法为主，计算次数上辗转相除法计算次数相对较少，特别当两个数字大小区别较大时计算次数的区别较明显.
2.从结果体现形式来看，辗转相除法体现结果是以相除余数为0则得到，而更相减损术则以减数与差相等而得到.作业：同步作业本P15—P16
更相减损术知识探究（一）:辗转相除法思考1:18与30的最大公约数是多少？你是怎样得到的？ 先用两个数公有的质因数连续去除，一直除到所得的商是互质数为止，然后把所有的除数连乘起来即为最大公约数. 思考2:对于8251与6105这两个数，由于其公有的质因数较大，利用上述方法求最大公约数就比较困难.注意到:
8251=6105×1+2146
那么8251与6105这两个数的公约数和6105与2146的公约数有什么关系？
思考3:又6105=2146×2+1813，同理，6105与2146的公约数和2146与1813的公约数相等.重复上述操作，你能得到8251与6105这两个数的最大公约数吗？2146=1813×1+333，148=37×4+0.333=148×2+37，1813=333×5+148，8251=6105×1+2146，6105=2146×2+1813，练习1 用辗转相除法求最大公约数（1）378 90
（2）90 36
（3）16 12
（4）228 1995思考4:上述求两个正整数的最大公约数的方法称为辗转相除法或欧几里得算法.一般地，用辗转相除法求两个正整数m，n的最大公约数，可以用什么逻辑结构来构造算法？其算法步骤如何设计？ 第一步，给定两个正整数m，n(m>n).第二步，计算m除以n所得的余数r. 第三步，m=n，n=r.第四步，若r=0，则m，n的最大公约数等 于m；否则，返回第二步. 思考5:该算法的程序框图如何表示？思考6:该程序框图对应的程序如何表述？INPUT m，nDOr=m MOD nm=nn=rLOOP UNTIL r=0PRINT mENDINPUT m，nWHILE n<>0r=m MOD nm=nn=rWENDPRINT mEND思考7:用当型循环结构构造算法:“更相减损术”在中国古代数学专著《九章算术》中记述为：可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也，以等数约之. 知识探究（二）:更相减损术 第一步：任意给定两个正整数；判断他们是否都是偶数。若是，则用2约简；若不是则执行第二步。第二步：以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止，则这个等数就是所求的最大公约数。思考1:求98与63的最大公约数？98-63=3514-7=721-7=1428-7=2135-28=763-35=28练习2用更相减损术求最大公约数（1）28 13
（2）90 36
（3）16 12理论迁移 例1 分别用辗转相除法和更相减损术求168与93的最大公约数. 辗转相除法：168=93×1+75， 93=75×1+18， 75=18×4+3， 18=3×6+0.更相减损术:168-93=75，
93-75=18，
75-18=57，
57-18=39，
39-18=21，
21-18=3，
18-3=15，
15-3=12，
12-3=9，
9-3=6，
6-3=3. 例3 求325，130，270三个数的最大公约数. 因为325=130×2+65，130=65×2，所以325与130的最大公约数是65. 因为270=65×4+10，65=10×6+5，10=5×2+0，所以65与270最大公约数是5. 故325，130，270三个数的最大公约数是5.练习3 求319，377，116三个数的最大公约数. 1.辗转相除法，就是对于给定的两个正整数，用较大的数除以较小的数，若余数不为零，则将余数和较小的数构成新的一对数，继续上面的除法，直到大数被小数除尽为止，这时的较小的数即为原来两个数的最大公约数. 小结作业 2. 更相减损术，就是对于给定的两个正整数，用较大的数减去较小的数，然后将差和较小的数构成新的一对数，继续上面的减法，直到差和较小的数相等，此时相等的两数即为原来两个数的最大公约数.比较辗转相除法与更相减损术的区别 1.都是求最大公约数的方法，计算上辗转相除法以除法为主，更相减损术以减法为主，计算次数上辗转相除法计算次数相对较少，特别当两个数字大小区别较大时计算次数的区别较明显.
2.从结果体现形式来看，辗转相除法体现结果是以相除余数为0则得到，而更相减损术则以减数与差相等而得到.作业：同步作业本P15—P16