《131辗转相除法(欧几里得算法).ppt》由会员分享，可在线阅读，更多相关《131辗转相除法(欧几里得算法).ppt（20页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、1.3算算 法法 案案 例例辗转相除法（欧几里得算法）辗转相除法（欧几里得算法）与更相减损术与更相减损术3 59 15 问题问题11：在小学，我们已经学过求最大公约数的知识，在小学，我们已经学过求最大公约数的知识，你能求出你能求出1818与与3030的的最大公约数最大公约数吗？吗？创设情景，揭示课题创设情景，揭示课题 18 30231818和和3030的最大公约数的最大公约数是是2 23=6.3=6.先用两个数公有的先用两个数公有的质因数质因数连续去除连续去除,一一直除到所得的商是直除到所得的商是互质数为止互质数为止,然后把然后把所有的除数连乘起所有的除数连乘起来来.练习练习1、求两个正整数的
2、最大公约数、求两个正整数的最大公约数（1）求）求25和和35的最大公约数的最大公约数（2）求）求49和和63的最大公约数的最大公约数2、求求204与与85的最大公约数的最大公约数 25（1） 5535749（2） 77639所以，所以，25和和35的最大公约数为的最大公约数为5所以，所以，49和和63的最大公约数为的最大公约数为7v分析：分析：204与与85两数都比较大，而且没有明显的公约数，两数都比较大，而且没有明显的公约数，如能把它们都变小一点，根据已有的知识即可求出最大公如能把它们都变小一点，根据已有的知识即可求出最大公约数约数辗转相除法（欧几里得算法）辗转相除法（欧几里得算法）用辗转相
3、除法求用辗转相除法求8251和和6105的最大公约数的最大公约数第一步第一步 用两数中较大的数除以较小的数，求得商和余数用两数中较大的数除以较小的数，求得商和余数8251=61051+2146结论：结论： 8251和和6105的公约数就是的公约数就是6105和和2146的公约数，的公约数，求求8251和和6105的最大公约数，只要求出的最大公约数，只要求出6105和和2146的公的公约数就可以了。约数就可以了。第二步第二步 对对6105和和2146重复第一步的做法重复第一步的做法6105=21462+1813同理同理6105和和2146的最大公约数也是的最大公约数也是2146和和1813的最大
4、的最大公约数公约数。 完整的过程完整的过程8251=61051+2146 6105=21462+1813 2146=18131+3331813=3335+148333=1482+37148=374+0例例2 用辗转相除法求用辗转相除法求225和和135的最大公约数的最大公约数225=1351+90135=901+4590=452显然显然37是是148和和37的最大公约的最大公约数，也数，也就是就是8251和和6105的最的最大公约数大公约数 显然显然45是是90和和45的最大公约数，也的最大公约数，也就是就是225和和135的最大公约数的最大公约数 练习练习1：利用辗转相除法求两数：利用辗转相
5、除法求两数4081与与20723的的最大公约数最大公约数. v20723=40815+318;v4081=31812+265;v318=2651+53;v265=535+0.(53)(53)利用辗转相除法求最大公约数的步骤如下：利用辗转相除法求最大公约数的步骤如下： 第一步：用较大的数第一步：用较大的数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
6、除以余数除以余数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 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 即为所求的最大即为所求的最大公约数。公约数。思考思
7、考1：从上面的步骤中可以得出辗转相除法算法步骤为：从上面的步骤中可以得出辗转相除法算法步骤为： S1：给定两个正整数：给定两个正整数m,nS2：用大数除以小数，计算：用大数除以小数，计算m除以除以n所得的余数；所得的余数；S3：除数变成被除数，余数变成除数，即：除数变成被除数，余数变成除数，即 m=n , n=rS4：重复：重复S2,直到余数为直到余数为0，即，即 若若r=0，则，则m, n 的最大公约数为的最大公约数为m，否则返回，否则返回S2 辗转相除法是一个反复执行直到余数等于辗转相除法是一个反复执行直到余数等于0停止的步骤，这实际上是停止的步骤，这实际上是一个一个循环结构循环结构。82
8、51=61051+2146 6105=21462+1813 2146=18131+3331813=3335+148333=1482+37148=374+0m = n q r用程序框图表示出右边的过程用程序框图表示出右边的过程r=m MOD nm = nn = rr=0?是是否否r=m MOD nm = nn = rr=0?是是否否开始开始 输入两个正数输入两个正数m,n 输出输出m,n结束结束INPUT m,nDO r=m MOD nm=nn=rLOOP UNTIL r=0PRINT mEND思考思考:你能用你能用当型循环结构当型循环结构构造算法，构造算法，求两个正整数的最大公约数吗求两个正整
9、数的最大公约数吗?写出算写出算法步骤、程序框图和程序法步骤、程序框图和程序。 输入两个正数输入两个正数m,n否否开始开始r=m MOD nr0?输出输出n结束结束m=nn=r是是INPUT m,nr=m MOD nWHILE r0 m=nn=rr=m MOD n WENDPRINT nEND九章算术九章算术更相减损术更相减损术 算理算理：可半者半之，不可半者，副置分母、子之数，以少减可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也，以等数约之。多，更相减损，求其等也，以等数约之。第一步：第一步：任意给定两个正整数；判断他们是否都是偶数。任意给定两个正整数；判断他们是否都是偶
10、数。若是，则用若是，则用2约简；若不是则执行第二步。约简；若不是则执行第二步。第二步第二步：以较大的数减较小的数，接着把所得的差与较小的以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止，则这个等数或这个数与约简的数的乘积数和差相等为止，则这个等数或这个数与约简的数的乘积就是所求的最大公约数。就是所求的最大公约数。例例3 用更相减损术求用更相减损术求98与与63的最大公约数的最大公约数解：由于解：由于63不是偶数，把不是偶数，把98和和63以大数减小数，并辗转相减以大数减小数，并辗转相减
11、 9863356335283528728721217141477所以，所以，98和和63的最大公约数等于的最大公约数等于7 练习练习2：用更相减损术求两个正数用更相减损术求两个正数84与与72的最大公约数。的最大公约数。 (12)思考：思考：你能根据更相减损术设计程序，求两个正整数的最大你能根据更相减损术设计程序，求两个正整数的最大公约数吗？公约数吗？S1:给定两个正整数给定两个正整数 m,n不妨设不妨设mn;S2：若：若m,n都是偶数，则不断用都是偶数，则不断用2约简，使它们不同时是偶数，约约简，使它们不同时是偶数，约简后的两个数仍记为简后的两个数仍记为m,n;S3：d=m-n;S4:判断判
12、断“dn”是否成立。若是，则将是否成立。若是，则将n,d中的较大者记为中的较大者记为m，较，较小者记为小者记为n，返回，返回s3;否则，否则，2kd(k时约简整数的时约简整数的2的个数的个数)为所求为所求的最大公约数。的最大公约数。开始开始输输m,n(mn)K=0M,n为偶数为偶数?K=k+1M=m/2N=n/2D=m-nDn?Dn?否否M=nN=dD=m-nM=d是是输出输出2k *d结束结束是是否否否否是是INPUT “m,n=“;m,nIF mn THEN a=m m=n n=aEND IFK=0WHILE m MOD 2=0 AND n MOD 2=0 m=m/2 n=n/2 k=k+
13、1WEND d=m- nWhile dn IF dn then m=d ELSE m=n n=d End if d=m-nWend d=2k*dPRINT dEnd 练习：练习：分别用辗转相除法和分别用辗转相除法和更相减损术求更相减损术求204204与与8585的最大公约数。的最大公约数。 解：解：204 85 2 3485 34 2 1734 17 2 204 85 119119 85 3485 34 5151 34 1734 17 17回顾反思回顾反思 ：辗转相除法与更相减损术的比较辗转相除法与更相减损术的比较: : （1 1）都是求最大公约数的方法，计算上辗转相除法以）都是求最大公约数的
14、方法，计算上辗转相除法以除除法法为主，更相减损术以为主，更相减损术以减法减法为主为主; ;计算次数上辗转相除法计算次计算次数上辗转相除法计算次数相对较少，特别当两个数字大小区别较大时计算次数的区别数相对较少，特别当两个数字大小区别较大时计算次数的区别较明显。较明显。（2 2）从结果体现形式来看，辗转相除法体现结果是以相）从结果体现形式来看，辗转相除法体现结果是以相除余数为除余数为0 0则得到，而更相减损术则以减数与差相等而得到则得到，而更相减损术则以减数与差相等而得到. . （3 3）辗转相除法是当大数被小数除尽时，结束除法运算，辗转相除法是当大数被小数除尽时，结束除法运算，较小的数就是最大公约数更相减损术是当大数减去小数的差较小的数就是最大公约数更相减损术是当大数减去小数的差等于小数时减法停止较小的数就是最大公约数等于小数时减法停止较小的数就是最大公约数 求三个以上求三个以上(含三个数含三个数)的数的最大公约数时，可依的数的最大公约数时，可依次通过求两个数的最大公约数与第三数的最大公约数来求得次通过求两个数的最大公约数与第三数的最大公约数来求得