8辗转相除法与更相减损术(精)

1、辗转相除法与更相减损术复习回顾1研究一个实际问题的算法，主要从算法步骤、程序框和编写程序三方面展开在程序框图中算法的基本逻辑结 构有哪几种？在程序设计中基本的算法语句有哪几种?新课引入2“求两个正整数的最大公约数”是数学中的一个基础性 问题，它有各种解决办法，我们以此为案例，对该问题的 算法作一些探究.K创设情景，揭示课题H问题1：在小学，我们已经学过求最大公约数的知 识，你能求出18与30的最大公约数吗？先用两个数公有的质因数连 续去除，一直除到所得的商是 互质数为止，然后把所有的除 数连乘起来.ex：(1)求25和35的最大公约数( (2)求49和63的最大公约数K创设情景，揭示课题H问题

2、2:我们都是利用找公约数的方法来求最 大公约数，如果公约数比较大而且根据我们的 观察又不能得到一些公约数，我们又应该怎样 求它们的最大公约数？比如求8251与6105的最 大公约数？318和30的最大公约数是2X3=6.(1)52535(2)7496379思考2:对于8251与6105这两个数，由于其公有的质因数 较大，利用上述方法求最大公约数就比较困难了.注意到8251=6105X1+2146,8251与6105的公约数和6105与2146的公约数相同又6105=2146X2+1813,同理，6105与2146的公约数和2146与1813的公约数相等. 重复上述操作，你能得到8251与610

3、5这两个数的 最大公约数37148=37X4+0.8251=6105X1+2146,6105=2146X2+1813,2146=1813X1+333,1813=31813=333X5+148,333=14完整的过程例如，用辗转相除法求225和135的最大公约数8251=6105X1+214225=135X1+90/1813=333X5+148148=37X4+0显然45是90和45的最大公约数， 也思考：从上面的两个例子可以看出计算的规律是什么？用大显然37是148和37的最大公约数， 也就是除数变成被除数，余数变成除数S3：重复S1,直到余思埶援转相除法中的关键步骤是哪种逻解构2辗转相除法是

4、一个反复执行直到余数等于o停止的步骤, 这实际上是一个循环结构。8251=6105X1+2146/ /6105=2146X2+18132146=1813X1+3331813=333X5+148/ / 333=48 X2+3J148=37X4+0上述求两个正整数的最大公约数的方法称为 辗转相除法或欧几里得算法.可以用什么逻辑结构来构造算法？其算法步骤如何设计?第一步，给定两个正整数m, n (mn).第二步，计算m除以n所得的余数r.第三步，m=n, n=r.否则，返回第二步.一般地，的步,则m, n的最大公约数等于m；用程Hog4081=318X12+265;318=265X1+53;265=

5、53X5+0.匕述算法的程序框图如何表示?INPUT练习2072320723=4081 X5+31出m /结束知识探究（二）：更相减损术思考1:设两个正整数mn,若mn=k,则m与n的最大公约数 和n与k的最大公约数；相等.反复利用这个原理，可求得：98与63的最大公约数为798-63=35,63-35=28,35-28=7,28-7=21,21-7=14, 14-7=7.理论迁移例1求168与93的最大公约数.（要求：分别用辗转相除法和更相减损术） 辗转相除法：168=93X1+75,93=75X1+18,75=18X4+3,18=3X6+0 故最大公约数为312-3=9,9-3=6,这种求两个正整数的最大公约数的 方法称为更相减损术.總鬆93-75=18,756-3=3 理论迁移例2.求325, 130, 270三个数的最大公约数.所以325与130的最大公约数是65.又因为270=65X4+10, 65=10X6+5, 10=5X2+0,所以65与270最大公约数是5.故325, 130, 270三个数的最大公约数是5.课堂练习比 _1.用辗转相除法计算60与48的最大公约数时，需要做_ 次除法运算。2.分别用辗转相除法和更相减损术计算288与123的最大公 约数。|课堂小结1辗转程序程序m,“更相减损术”在中国古代数学专著九章算术中记述 为：可半