辗转相除与更相减损术

1、案例案例1 辗转相除法与更相减损术辗转相除法与更相减损术3 59 15 问题问题11：在小学，我们已经学过求最大公约数：在小学，我们已经学过求最大公约数的知识，你能求出的知识，你能求出1818与与3030的最大公约数吗？的最大公约数吗？创设情景，揭示课题创设情景，揭示课题18 30231818和和3030的最大公约的最大公约数是数是2 23=6.3=6.先用两个数公有的先用两个数公有的质因数质因数连续去除连续去除,一直除到所得一直除到所得的商是互质数为止的商是互质数为止,然后然后把所有的除数连乘起来把所有的除数连乘起来. 问题问题2:2:我们都是利用找公约数的方法来求最大我们都是利用找公约数的

2、方法来求最大公约数，如果公约数比较大而且根据我们的观察公约数，如果公约数比较大而且根据我们的观察又不能得到一些公约数，我们又应该怎样求它们又不能得到一些公约数，我们又应该怎样求它们的最大公约数？比如求的最大公约数？比如求82518251与与61056105的最大公约数的最大公约数? ? 研探新知研探新知1.1.辗转相除法辗转相除法: :例例1 1 求两个正数求两个正数82518251和和61056105的最大公约数。的最大公约数。分析：分析：82518251与与61056105两数都比较大，而且没两数都比较大，而且没有明显的公约数，如能把它们都变小一点，根有明显的公约数，如能把它们都变小一点，

3、根据已有的知识即可求出最大公约数据已有的知识即可求出最大公约数. .解：解：82518251610561051 121462146显然显然82518251与与61056105的最大公约数也必是的最大公约数也必是21462146的约数，同样的约数，同样61056105与与21462146的公约数也必是的公约数也必是82518251的约数，所以的约数，所以82518251与与61056105的最大公约数也是的最大公约数也是61056105与与21462146的最大公约数。的最大公约数。思考思考2:2:对于对于82518251与与61056105这两个数，由于这两个数，由于其公有的质因数较大，利用上

4、述方法求其公有的质因数较大，利用上述方法求最大公约数就比较困难最大公约数就比较困难. .注意到注意到8251=61058251=61051+21461+2146，那么，那么82518251与与61056105这两个数的公约数和这两个数的公约数和61056105与与21462146的公约的公约数有什么关系？数有什么关系？ 思考思考3:3:又又6105=21466105=21462+18132+1813，同理，同理，61056105与与21462146的公约数和的公约数和21462146与与18131813的公的公约数相等约数相等. .重复上述操作，你能得到重复上述操作，你能得到82518251与

5、与61056105这两个数的最大公约数吗？这两个数的最大公约数吗？21462146= =181318131+1+333333，148148= =37374+0.4+0.333333= =1481482+2+3737，18131813= =3333335+5+148148，8251=8251=610561051+1+21462146，61056105= =214621462+2+18131813，研探新知研探新知1.1.辗转相除法辗转相除法: :例例1 1 求两个正数求两个正数82518251和和61056105的最大公约数的最大公约数。则则3737为为82518251与与61056105的最大

6、公约数。的最大公约数。以上我们求最大公约数的方法就是以上我们求最大公约数的方法就是辗转相辗转相除法。也叫欧几里德算法除法。也叫欧几里德算法，它是由欧几里德在，它是由欧几里德在公元前公元前300300年左右首先提出的。年左右首先提出的。 21462146= =181318131+1+333333，148148= =37374+0.4+0.333333= =1481482+2+3737，18131813= =3333335+5+148148，8251=8251=610561051+1+21462146，61056105= =214621462+2+18131813，利用辗转相除法求最大公约数的步骤

7、如下：利用辗转相除法求最大公约数的步骤如下： 第一步：用较大的数第一步：用较大的数m m除以较小的数除以较小的数n n得到得到一个商一个商q q0 0和一个余数和一个余数r r0 0；(m=n(m=nq q0 0+r+r0 0) ) 第二步：若第二步：若r r0 00 0，则，则n n为为m m，n n的最大公约的最大公约数；若数；若r r0 000，则用除数，则用除数n n除以余数除以余数r r0 0得到一个得到一个商商q q1 1和一个余数和一个余数r r1 1；(n=r(n=r0 0q q1 1+r+r1 1) ) 第三步：若第三步：若r r1 10 0，则，则r r0 0为为m m，n

8、 n的最大公约的最大公约数；若数；若r r1 100，则用除数，则用除数r r0 0除以余数除以余数r r1 1得到一个得到一个商商q q2 2和一个余数和一个余数r r2 2；(r(r0 0=r=r1 1q q2 2+r+r2 2) ) 依次计算直至依次计算直至r rn n0 0，此时所得到的，此时所得到的r rn-1n-1 即为所求的最大公约数。即为所求的最大公约数。思考思考4:4:上述求两个正整数的最大公约数上述求两个正整数的最大公约数的方法称为的方法称为辗转相除法辗转相除法或或欧几里得算法欧几里得算法. .一般地，用辗转相除法求两个正整数一般地，用辗转相除法求两个正整数m m，n n的

9、最大公约数，可以用什么逻辑结构来的最大公约数，可以用什么逻辑结构来构造算法？其算法步骤如何设计？构造算法？其算法步骤如何设计？ 第一步，给定两个正整数第一步，给定两个正整数m m，n(mn(mn).n).第二步，计算第二步，计算m m除以除以n n所得的余数所得的余数r. r. 第三步，第三步，m=nm=n，n=r.n=r.第四步，若第四步，若r=0r=0，则，则m m，n n的最大公约数等的最大公约数等 于于m m；否则，返回第二步；否则，返回第二步. . 思考思考5:5:该算法的程序框图如何表示？该算法的程序框图如何表示？开始开始输入输入m，n求求m除以除以n的余数的余数rm=nn=rr=

10、0？是是输出输出m结束结束否否思考思考6:6:该程序框图对应的程序如何表述？该程序框图对应的程序如何表述？INPUT mINPUT m，n nDODOr=m MODnr=m MODnm=nm=nn=rn=rLOOP UNTILLOOP UNTIL r=0r=0PRINT mPRINT mENDEND开始开始输入输入m，n求求m除以除以n的余数的余数rm=nn=rr=0？是是输出输出m结束结束否否思考思考7:7:如果用当型循环结构构造算法，如果用当型循环结构构造算法，则用辗转相除法求两个正整数则用辗转相除法求两个正整数m m，n n的最的最大公约数的程序框图和程序分别如何表大公约数的程序框图和程

11、序分别如何表示？示？开始开始输入输入m，n求求m除以除以n的余数的余数rm=nn0？否否输出输出m结束结束是是n=rINPUT mINPUT m，n nWHILEWHILE n n0 0r=m MODnr=m MODnm=nm=nn=rn=rWENDWENDPRINT mPRINT mENDEND练习练习1 1：利用辗转相除法求两数：利用辗转相除法求两数40814081与与2072320723的最大公约数的最大公约数. . (53)(53)20723=40815+318;4081=31812+265;318=2651+53;265=535+0.2.2.更相减损术更相减损术: :我国早期也有解决

12、求最大公约数问题的算我国早期也有解决求最大公约数问题的算法，就是更相减损术。法，就是更相减损术。更相减损术更相减损术求最大公约数的步骤如下：求最大公约数的步骤如下：可可半者半之，不可半者，副置分母半者半之，不可半者，副置分母子之数，以少子之数，以少减多，更相减损，求其等也，以等数约之。减多，更相减损，求其等也，以等数约之。翻译出来为：翻译出来为：第一步：第一步：任意给出两个正数；任意给出两个正数；判断它们是否都是偶数。若是，用判断它们是否都是偶数。若是，用2 2约简；若不是，约简；若不是，执行第二步。执行第二步。第二步：第二步：以以较大的数减去较小的数较大的数减去较小的数，接着把，接着把较小的

13、数与所得的差比较，较小的数与所得的差比较，并以大数减小数并以大数减小数。继。继续这个操作，续这个操作，直到所得的数相等为止直到所得的数相等为止，则这个数，则这个数（等数）就是所求的最大公约数。（等数）就是所求的最大公约数。例例2 2 用更相减损术求用更相减损术求9898与与6363的最大公约数的最大公约数. .解：由于解：由于6363不是偶数，把不是偶数，把9898和和6363以大数以大数减小数，并辗转相减，减小数，并辗转相减， 即：即：986335; 633528; 35287; 28721; 21714; 1477.所以，所以，9898与与6363的最大公约数是的最大公约数是7 7。练习练

14、习2 2：用更相减损术求两个正数：用更相减损术求两个正数8484与与7272的最大的最大公约数。公约数。 (12)(12) 例例2 2 求求325325，130130，270270三个数的最大三个数的最大公约数公约数. . 因为因为325=130325=1302+652+65，130=65130=652 2，所以所以325325与与130130的最大公约数是的最大公约数是65.65. 因为因为270=65270=654+104+10，65=1065=106+56+5，10=510=52 2，所以所以6565与与270270最大公约数是最大公约数是5. 5. 故故325325，130130，27

15、0270三个数的最大公约三个数的最大公约数是数是5.5. 练习：求练习：求325,130,270三个数的最三个数的最大公约数大公约数小结：见大聚焦小结：见大聚焦阅读阅读P12倒数第二段倒数第二段P15思考，并完成下表：思考，并完成下表：语句语句一般格式一般格式主要功能主要功能说明说明输入语句输入语句输出语句输出语句赋值语句赋值语句（1）;变量变量PRINT “提示内容提示内容”;表达式表达式变量表达式变量表达式可对程序中可对程序中的变量赋值的变量赋值可输出表达式可输出表达式的值，计算的值，计算可对程序中的变可对程序中的变量赋值，计算量赋值，计算（1）提示内容和它后面）提示内容和它后面 的的“；”可以省略可以省略（2）一个语