《1.3.1算法案例辗转相除法与更相减损术》由会员分享，可在线阅读，更多相关《1.3.1算法案例辗转相除法与更相减损术（22页珍藏版）》请在金锄头文库上搜索。
1、1.3.1 算法案例算法案例(一一)辗转辗转相除法与更相减损术相除法与更相减损术必修必修 第一章第一章 算法初步算法初步咸丰一中 杨金煜3 53 59 159 15 问题问题11：在小学，我们已经学过求最大公约数的知在小学，我们已经学过求最大公约数的知识，你能求出识，你能求出1818与与3030的最大公约数吗？的最大公约数吗？创设情景，揭示课题创设情景，揭示课题18 3018 302 23 31818和和3030的最大公约的最大公约数是数是2 23=6.3=6.方法：方法：先用两个数公有的先用两个数公有的质质因数因数连续去除连续去除, ,一直除到所得一直除到所得的商是互质数为止的商是互质数为止
2、, ,然后把所然后把所有的除数连乘起来有的除数连乘起来. .练习练习1 1( (1)1)求求2525和和3535的最大公约数的最大公约数,(2),(2)求求4949和和6363的最大公约数的最大公约数. .2525（1 1）5 55 535357 74949（2 2）7 77 763639 9所以，所以，2525和和3535的最大公约数为的最大公约数为5 5所以，所以，4949和和6363的最大公约数为的最大公约数为7 7创设情景，揭示课题创设情景，揭示课题 问题问题2:2:我们都是利用找公约数的方法来求最我们都是利用找公约数的方法来求最大公约数，如果公约数比较大而且根据我们的大公约数，如果公
3、约数比较大而且根据我们的观察又不能得到一些公约数，我们又应该怎样观察又不能得到一些公约数，我们又应该怎样求它们的最大公约数？比如求求它们的最大公约数？比如求82518251与与61056105的最的最大公约数大公约数? ? 思路思路1 1：试值？！：试值？！何时结束？有何好的方法？何时结束？有何好的方法？案例一：案例一：辗转相除法（辗转相除法（欧几里得算法欧几里得算法）观察用辗转相除法求观察用辗转相除法求82518251和和61056105的最大公约数的过程的最大公约数的过程 第一步第一步 用两数中较大的数除以较小的数，求得商和余数用两数中较大的数除以较小的数，求得商和余数8251=61051
4、+21468251=61051+2146结论：结论： 82518251和和61056105的公约数就是的公约数就是61056105和和21462146的的公约数，求公约数，求82518251和和61056105的最大公约数，只要求的最大公约数，只要求出出61056105和和21462146的公约数就可以了的公约数就可以了. .第二步第二步 对对61056105和和21462146重复第一步的做法重复第一步的做法6105=21462+18136105=21462+1813同理同理61056105和和21462146的最大公约数也是的最大公约数也是21462146和和18131813的的最大公约数
5、最大公约数. . 完整的过程完整的过程8251=61051+2146 6105=21462+1813 2146=18131+3331813=3335+148333=1482+37148=374+0例如，用辗转相除法求例如，用辗转相除法求225225和和135135的最大公约数的最大公约数225=1351+90135=901+4590=452显然显然3737是是148148和和3737的最大公约的最大公约数，也就是数，也就是82518251和和61056105的最大的最大公约数公约数 显然显然4545是是9090和和4545的最大公约数，也就是的最大公约数，也就是225225和和135135的最
6、大公约数的最大公约数 思考：从上面的两个例子可思考：从上面的两个例子可以看出计算的规律是什么？以看出计算的规律是什么？ S1S1：用大数除以小数：用大数除以小数S2S2：除数变成被除数，余数变成除数：除数变成被除数，余数变成除数S3S3：重复：重复S1S1，直到余数为，直到余数为0 0问题提出：问题提出：你能把辗转相除法编成一个计算你能把辗转相除法编成一个计算机程序吗？机程序吗？算法分析：从上面对辗转相除法的认识中可以算法分析：从上面对辗转相除法的认识中可以看出，辗转相除法中包含重复操作的步骤，因看出，辗转相除法中包含重复操作的步骤，因此可以用循环结构来构造算法。此可以用循环结构来构造算法。算
7、法步骤：算法步骤：第一步，给定两个正整数第一步，给定两个正整数m m ， n(mn(mn)n)。第二步，计算第二步，计算m m除以除以n n所得的余数所得的余数r r。第三步，第三步，m=n m=n ， n=r n=r 。第四步，若第四步，若r=0r=0，则，则m , nm , n的最大公约数等于的最大公约数等于m m ；否则，返回第二步。否则，返回第二步。否否思考：思考：画出辗转相除法的程序框图并设计其程序画出辗转相除法的程序框图并设计其程序开始开始输入两个正数整输入两个正数整m,nm,nr=m MOD nr=m MOD nr=0?r=0?输出输出m m结束结束m=nm=nn=rn=r是是I
8、NPUT INPUT m,nm,nDODOr=m MOD nr=m MOD nm=nm=nn=rn=rLOOP UNTIL r=0LOOP UNTIL r=0PRINT mPRINT mENDEND思考：你能用当型循环结构构造算法，求思考：你能用当型循环结构构造算法，求两个正整数的最大公约数吗？试写出算法两个正整数的最大公约数吗？试写出算法步骤、程序框图和程序。步骤、程序框图和程序。分析：在使用当型循环结构时，因为在输入两个正分析：在使用当型循环结构时，因为在输入两个正数后，直接进入判断数后，直接进入判断r0, r0, 这里没有一个最初的这里没有一个最初的r r值，值，因而在设计过程中，可先令
9、因而在设计过程中，可先令r=1r=1。算法步骤：算法步骤：第一步，给定两个正整数第一步，给定两个正整数m m ，n(mn(mn)n)。第二步第二步, ,令令r=1.r=1.第三步，若第三步，若rr，则执行第四步；否则，则执行第四步；否则，m m，n n的最的最大公约数等于大公约数等于m,m,结束算法结束算法. .第四步，计算第四步，计算m m除以除以n n所得的余数所得的余数r r。第五步，第五步，m=nm=n，n=r,n=r,返回第三步返回第三步. .开始开始输入输入m,nr=1r0?输出输出m结束结束n=r求求m除以除以n的余数的余数rm=n是是否否程序框图如下：程序框图如下：程序如下：程
10、序如下：INPUTm,nr=1WHILEr0r=mMODnm=nn=rWENDPRINTmEND知识探究（二）知识探究（二）: :更相减损术更相减损术 1:1:设两个正整数设两个正整数m m n n，若，若m-nm-n=d=d，则，则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-3
11、5=2863-35=28，九章算术九章算术更相减损术更相减损术 算理：算理：可半者半之，不可半者，副置分可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求母、子之数，以少减多，更相减损，求其等也，以等数约之其等也，以等数约之. .算法分析：算法分析：第一步、第一步、任意给定两个正整数，判断他们是否都是任意给定两个正整数，判断他们是否都是偶数，若是，用偶数，若是，用2 2约简；若不是，执行第二步。约简；若不是，执行第二步。第二步、第二步、以较大的数减较小的数，接着把所得的差以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，与较小的数比较，并以大数减小数
12、。继续这个操作，直到所得的减数和差相等为止，则这个等数就是所直到所得的减数和差相等为止，则这个等数就是所求的最大公约数求的最大公约数. .例例2 2、用更相减损术求、用更相减损术求9898与与6363的最大公约数的最大公约数（自己按照步骤求解）（自己按照步骤求解）解：由于解：由于6363不是偶数，把不是偶数，把9898和和6363以大数减小数，并辗转相减。以大数减小数，并辗转相减。= 7所以，所以，9898和和6363的最大公约数等于的最大公约数等于7 7。（98，63）=（63，35）98-63=3598-63=35 63-35=2863-35=28=（35，28）35-28=735-28=
13、7=（28，7）28-7=2128-7=21=（21，7）21-7=1421-7=14=（14，7）14-7=714-7=7=（7，7）练习：用更相减损术求下列两数的最大公约数：（1）（225，135） （2）（98，196）（3）（72，168） （4）（153，119）45982417思考：更相减损直到何时结束？运用的是哪种算法结构？思考：更相减损直到何时结束？运用的是哪种算法结构？更相减损是一个反复执行直到减数等于差时停止的步骤，这实际也是一个循环结构 2:2:上述求两个正整数的最大公约数的方法称为更相减损术上述求两个正整数的最大公约数的方法称为更相减损术. .一一般地，用更相减损术求两
14、个正整数般地，用更相减损术求两个正整数m m，n n的最大公约数，可以的最大公约数，可以用什么逻辑结构来构造算法？其算法步骤如何设计？用什么逻辑结构来构造算法？其算法步骤如何设计？第一步，给定两个正整数第一步，给定两个正整数m m，n(mn(mn).n). 第三步，计算第三步，计算m-nm-n所得的差所得的差d. d. 第四步，判断第四步，判断“d d不等于不等于n n”是否成立，若是，则是否成立，若是，则将将n n，d d中大者用中大者用m m表示，小者用表示，小者用n n表示，返回第三表示，返回第三步；否则，步；否则，2k*2k*d(kd(k是约简整数是约简整数2 2的个数的个数) ) 为
15、所求为所求的最大公约数。的最大公约数。第二步，若第二步，若m m、n n都是偶数，则不断用都是偶数，则不断用2 2约简，使约简，使他们不同时是偶数，约简的两个数仍记为他们不同时是偶数，约简的两个数仍记为m m，n n。讨论：你能根据更相减损术的算法步骤画出其程序框图并写出程序语句吗?其算法步骤也可以这样设计其算法步骤也可以这样设计第一步，给定两个正整数第一步，给定两个正整数m m，n(mn(mn).n). 第二步，计算第二步，计算m-nm-n所得的差所得的差d. d. 第三步，比较第三步，比较n n与与d d的大小，其中大者用的大小，其中大者用m m表表 示，小者用示，小者用n n表示表示.
16、. 第四步，若第四步，若m=nm=n，则，则m m，n n的最大公约数等于的最大公约数等于 m m；否则，返回第二步；否则，返回第二步. . 其程序框图和程序语句如下： INPUT INPUT “m,nm,n=”;=”;m,nm,nIF mn THENIF mn THEN a=m a=m m=n m=n n=a n=aEND IFEND IF d= d=m-nm-nWHILE dnWHILE dn IF dn THEN IF dn THEN m=d m=d ELSE ELSE m=n m=n n=d n=dEND IFEND IF d= d=m-nm-nWENDWENDPRINT dPRINT
17、 dENDENDm思考：辗转相除法与更相减损术有什么区别思考：辗转相除法与更相减损术有什么区别和联系？和联系？区别：区别：n计算上辗转相除法以除法为主，更相减损术以减法计算上辗转相除法以除法为主，更相减损术以减法为住；为住；n在计算次数上，辗转相除法计算次数相对较少，特在计算次数上，辗转相除法计算次数相对较少，特别当两个数大小差别较大时计算次数的区别较明显；别当两个数大小差别较大时计算次数的区别较明显；n从结果输出的时候看，辗转相除法当余数为从结果输出的时候看，辗转相除法当余数为0 0时输出时输出除数，更相减损术当差和减数相等时输出差。除数，更相减损术当差和减数相等时输出差。联系：联系：都是求
18、最大公约数的方法。因为做一次除法与做都是求最大公约数的方法。因为做一次除法与做若干次减法效果相同，商就是减法的次数，余数就若干次减法效果相同，商就是减法的次数，余数就是最后的差，由此可知二者是完全统一的！是最后的差，由此可知二者是完全统一的！练习：1，下列说法中正确的是（ ）A 辗转相除法是中国古代数学中的算法B 更相减损术与辗转相除法的算理完全不同C 辗转相除法与更相减损术相比较，用辗转相除法求最大公约数最优越D 辗转相除法与更相减损术，在设计程序时，都要用到循环结构。D 2，4830与3289的最大公约数为_3，用更相减损术求87与27的最大公约数时，反复相减，直至求出最大公约数，需要进行
19、减法运算的次数是_4，用辗转相除法求87与27的最大公约数，需要进行除法运算的次数是_5，46，115，276的最大公约数是_238323 n6，下面是求115与276的最大公约数的程序，把程序补充完整。a=115b=276DO r=_ a=b b=rLOOP UNTIL r=_PRINT aENDa MOD b0小结：辗转相除法与更相减损术的比较小结：辗转相除法与更相减损术的比较: : （1 1）都是求最大公约数的方法，计算上辗）都是求最大公约数的方法，计算上辗转相除法以转相除法以除法为主除法为主，更相减损术以，更相减损术以减法为主减法为主; ;计算次数上辗转相除法计算次数相对较少，特计算次数上辗转相除法计算次数相对较少，特别当两个数字大小区别较大时计算次数的区别别当两个数字大小区别较大时计算次数的区别较明显较明显. .（2 2）从结果体现形式来看，辗转相除法体）从结果体现形式来看，辗转相除法体现结果是以现结果是以相除余数为相除余数为0 0则得到，而更相减损术则得到，而更相减损术则以则以减数与差相等减数与差相等而得到而得到. .
