辗转相除法与更相减损术课件（曹国凤）

1、依兰县高级中学数学组依兰县高级中学数学组 曹国凤曹国凤【创设情境【创设情境】1.1.在初中，我们已经学过求最大公约数的知识，在初中，我们已经学过求最大公约数的知识，你能求出你能求出1818与与3030的公约数吗？的公约数吗？ 2.2.我们都是利用找公约数的方法来求最大公约数，我们都是利用找公约数的方法来求最大公约数，如果公约数比较大而且根据我们的观察又不能得到一如果公约数比较大而且根据我们的观察又不能得到一些公约数，我们又应该怎样求它们的最大公约数？比些公约数，我们又应该怎样求它们的最大公约数？比如求如求82518251与与61056105的最大公约数？这就是我们这一堂课的最大公约数？这就是我

2、们这一堂课所要探讨的内容。所要探讨的内容。 例例1 1 求两个正数求两个正数82518251和和61056105的最大公约数。的最大公约数。（分析：（分析：82518251与与61056105两数都比较大，而且没有明显的公约数，两数都比较大，而且没有明显的公约数，如能把它们都变小一点，根据已有的知识即可求出最大公约数）如能把它们都变小一点，根据已有的知识即可求出最大公约数）【探究新知【探究新知】解：解：82518251610561051 121462146显然显然82518251的最大公约数也必是的最大公约数也必是21462146的约数，的约数，同样同样61056105与与21462146的公

3、约数也必是的公约数也必是82518251的约数，的约数，所以所以82518251与与61056105的最大公约数也是的最大公约数也是61056105与与21462146的最大公约数。的最大公约数。61056105214621462 21813181321462146181318131 1333333181318133333335 51481483333331481482 2373714814837374 40 0则则3737为为82518251与与61056105的最大公约数。的最大公约数。以上求最大公约数的方法就是以上求最大公约数的方法就是辗转相除法辗转相除法。也叫。也叫欧几里德算法欧几里德

4、算法，它是由欧几里德在公元前它是由欧几里德在公元前300300年左右首先提出的。年左右首先提出的。利用辗转相除法求最大公约数的步骤如下：利用辗转相除法求最大公约数的步骤如下：第一步：用较大的数第一步：用较大的数m m除以较小的数除以较小的数n n得到一个商得到一个商q0q0和和 一个余数一个余数r0r0；第二步：若第二步：若r0r00 0，则，则n n为为m m，n n的最大公约数；若的最大公约数；若r00r00， 则用除数则用除数n n除以余数除以余数r0r0得到一个商得到一个商q1q1和一个余数和一个余数r1r1；第三步：若第三步：若r1r10 0，则，则r1r1为为m m，n n的最大公

5、约数；若的最大公约数；若r10r10， 则用除数则用除数r0r0除以余数除以余数r1r1得到一个商得到一个商q2q2和一个余数和一个余数r2r2； 依次计算直至依次计算直至rnrn0 0，此时所得到的，此时所得到的rnrn1 1即为所求的最大公约数。即为所求的最大公约数。练习：利用辗转相除法求两数练习：利用辗转相除法求两数40814081与与2072320723的最大公约数的最大公约数（答案：（答案：5353）算法分析算法分析从上面的例子可以看出，辗转相除法中包含重复操作的步骤，从上面的例子可以看出，辗转相除法中包含重复操作的步骤，因此可以用循环结构来构造算法。因此可以用循环结构来构造算法。算

6、法步骤如下：算法步骤如下：第一步，给定两个正整数第一步，给定两个正整数m,nm,n。第二步，计算第二步，计算m m 除以除以n n所得的余数所得的余数r r。第三步，第三步，m=n,nm=n,n=r=r。第四步，若第四步，若r=0r=0，则，则m,nm,n的最大公约数等于的最大公约数等于m m，否则，返回第二步。，否则，返回第二步。开始开始求求m m除以除以n n的余数的余数r r输出输出m m结束结束是r r0?0?m=nm=nn=r输入输入m,nm,n否程序框图程序框图INPUT m,nDO r=m MOD n m=n n=rLOOP UNTIL r=0 PRINT mEND程序程序: :

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

8、数第二步：以较大的数减去较小的数，接着把较小的数 与所得的差比较，并以大数减小数。与所得的差比较，并以大数减小数。 继续这个操作，直到所得的数相等为止，继续这个操作，直到所得的数相等为止，则这个数（等数）就是所求的最大公约数。则这个数（等数）就是所求的最大公约数。解：由于解：由于6363不是偶数，把不是偶数，把9898和和6363以大数减小数，并辗转相减，以大数减小数，并辗转相减，即：即：989863633535636335352828353528287 728287 7212121217 7141414147 77 7所以，所以，9898与与6363的最大公约数是的最大公约数是7 7。练习：

9、用更相减损术求两个正数练习：用更相减损术求两个正数8484与与7272的最大公约数。的最大公约数。（答案：（答案：1212）例例2 2 用更相减损术求用更相减损术求9898与与6363的最大公约数。的最大公约数。（2 2）从结果体现形式来看，辗转相除法体现结果是）从结果体现形式来看，辗转相除法体现结果是以相除余数为以相除余数为0 0则得到，而更相减损术则以减数与差相则得到，而更相减损术则以减数与差相等而得到等而得到比较辗转相除法与更相减损术的区别比较辗转相除法与更相减损术的区别（1 1）都是求最大公约数的方法，计算上辗转相除法以）都是求最大公约数的方法，计算上辗转相除法以除法为主，更相减损术以

10、减法为主，计算次数上辗转除法为主，更相减损术以减法为主，计算次数上辗转相除法计算次数相对较少，特别当两个数字大小区别相除法计算次数相对较少，特别当两个数字大小区别较大时计算次数的区别较明显。较大时计算次数的区别较明显。课堂练习课堂练习一一. .用辗转相除法求下列各组数的最大公约数，并编写程序。用辗转相除法求下列各组数的最大公约数，并编写程序。 （1 1）225225；135 135 （2 2）9898；196 196 （3 3）7272；168 168 （4 4）153153；119119二二. .思考：用求质因数的方法可否求上述思考：用求质因数的方法可否求上述4 4组数的最大公约数？组数的最大公约数？ 可否利用求质因数的算法设计出程序框图及程序？可否利用求质因数的算法设计出程序框图及程