辗转相除法与更相减损术 新人教必修PPT学习教案

1、会计学1 辗转相除法与更相减损术辗转相除法与更相减损术 新人教必修新人教必修 第1页/共19页 知识探究（一）知识探究（一）: :辗转相除法辗转相除法 思考思考1:181:18与与3030的最大公约数是多少？你的最大公约数是多少？你 是怎样得到的？是怎样得到的？ 先用两个数公有的质因数连续去先用两个数公有的质因数连续去 除，一直除到所得的商是互质数为止除，一直除到所得的商是互质数为止 ，然后把所有的除数连乘起来即为最，然后把所有的除数连乘起来即为最 大公约数大公约数. . 第2页/共19页 思考思考2:2:对于对于82518251与与61056105这两个数，由于这两个数，由于 其公有的质因数

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

3、到重复上述操作，你能得到 82518251与与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， 第4页/共19页 思考思考4:4:上述求两个正整数的最大公约数上述求两个正整数的最大公约数 的方法称为辗转相除法或欧几里得算法的方法称为辗转相除

4、法或欧几里得算法 . .一般地，用辗转相除法求两个正整数一般地，用辗转相除法求两个正整数m m ，n n的最大公约数，可以用什么逻辑结的最大公约数，可以用什么逻辑结 构来构造算法？其算法步骤如何设计？构来构造算法？其算法步骤如何设计？ 第一步，给定两个正整数第一步，给定两个正整数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页/共19页 思考

5、思考5:5:该算法的程序框图如何表示？该算法的程序框图如何表示？ 开始开始 输入输入m，n 求求m除以除以n的余数的余数r m=n n=r r=0？ 是是 输出输出m 结束结束 否否 第6页/共19页 思考思考6:6:该程序框图对应的程序如何表述该程序框图对应的程序如何表述 ？ INPUT mINPUT m，n n DODO r=m MODnr=m MODn m=nm=n n=rn=r LOOP UNTIL r=0LOOP UNTIL r=0 PRINT mPRINT m ENDEND 开始开始 输入输入m，n 求求m除以除以n的余数的余数r m=n n=r r=0？ 是是 输出输出m 结束结

6、束 否否 第7页/共19页 思考思考7:7:如果用当型循环结构构造算如果用当型循环结构构造算 法，则用辗转相除法求两个正整数法，则用辗转相除法求两个正整数 m m，n n的最大公约数的程序框图和程的最大公约数的程序框图和程 序分别如何表示？序分别如何表示？ 第8页/共19页 开始开始 输入输入m，n 求求m除以除以n的余数的余数r m = n n 0 ？否 否 输出输出m 结束结束 是是 n=r INPUT mINPUT m，n n WHILE nWHILE n0 0 r=m MODnr=m MODn m=nm=n n=rn=r WENDWEND PRINT mPRINT m ENDEND 第

7、9页/共19页 知识探究（二）知识探究（二）: :更相减损术更相减损术 思考思考1:1:设两个正整数设两个正整数m mn n，若，若m-n=km-n=k，则，则 m m与与n n的最大公约数和的最大公约数和n n与与k k的最大公约数的最大公约数 相等相等. .反复利用这个原理，可求得反复利用这个原理，可求得9898与与 6363的最大公约数为多少？的最大公约数为多少？ 98-63=3598-63=35， 14-7=7.14-7=7. 21-7=1421-7=14， 28-7=2128-7=21， 35-28=735-28=7， 63-35=2863-35=28， 第10页/共19页 思考思考

8、2:2:上述求两个正整数的最大公约数上述求两个正整数的最大公约数 的方法称为更相减损术的方法称为更相减损术. .一般地，用更一般地，用更 相减损术求两个正整数相减损术求两个正整数m m，n n的最大公约的最大公约 数，可以用什么逻辑结构来构造算法？数，可以用什么逻辑结构来构造算法？ 其算法步骤如何设计？其算法步骤如何设计？ 第一步，给定两个正整数第一步，给定两个正整数m m，n(mn).n(mn). 第二步，计算第二步，计算m-nm-n所得的差所得的差k. k. 第三步，比较第三步，比较n n与与k k的大小，其中大者用的大小，其中大者用m m表表 示，小者用示，小者用n n表示表示. . 第

9、四步，若第四步，若m=nm=n，则，则m m，n n的最大公约数等于的最大公约数等于 m m；否则，返回第二步；否则，返回第二步. . 第11页/共19页 思考思考3:3:该算法的程序框图如何表示？该算法的程序框图如何表示？ 开始开始 输入输入m，n nk？ m=n 是是 输出输出m 结束结束 mn？ k=m- - n 是是 否否 n=k m=k 否否 第12页/共19页 思考思考4:4:该程序框图对应的程序如何表述该程序框图对应的程序如何表述 ？ INPUT mINPUT m，n n WHILE WHILE m mn n k=m-nk=m-n IF nIF nk THENk THEN m=n

10、m=n n=kn=k ELSEELSEm=k m=k END IFEND IF WENDWEND PRINT mPRINT m ENDEND 开始开始 输入输入m，n nk？ m=n 是是 输 出输 出 m 结束结束 mn？ k=m- - n 是是 否否 n=k m=k 否否 第13页/共19页 “更相减损术更相减损术”在中国古代数学专著在中国古代数学专著 九章算术九章算术中记述为：中记述为： 可可 半者半之，不可半者，副置分母、子之半者半之，不可半者，副置分母、子之 数，以少减多，更相减损，求其等也，数，以少减多，更相减损，求其等也， 以等数约之以等数约之. . 第14页/共19页 理论迁移

11、理论迁移 例例1 1 分别用辗转相除法和更相减损分别用辗转相除法和更相减损 术求术求168168与与9393的最大公约数的最大公约数. . 辗转相除法：辗转相除法：168=93168=931+751+75， 93=7593=751+181+18， 75=1875=184+34+3， 18=318=36.6. 第15页/共19页 更相减损术更相减损术:168-93=75:168-93=75， 93-75=1893-75=18， 75-18=5775-18=57， 57-18=3957-18=39， 39-18=2139-18=21， 21-18=321-18=3， 18-3=1518-3=15，

12、 15-3=1215-3=12， 12-3=912-3=9， 9-3=69-3=6， 6-3=3.6-3=3. 第16页/共19页 例例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，270270三个数的最大公三个数的最大公 约数是约数是5.5. 第17页/共19页 1. 1.辗转相除法，就是对于给定的两个正辗转相除法，就是对于给定的两个正 整数，用较大的数除以较小的数，若余数不整数，用较大的数除以较小的数，若余数不 为零，则将余数和较小的数构成新的一对数为零，则将余数和较小的数构成新的一对数 ，继续上面的除法，直到大数被小数除尽为，继续上面的除法，直到大数被小数除尽为 止，这时的较小的数即为原来两个数的最大止，这时的较小的数即为原来两个数的最大 公约数公约数. . 小结作业