131《算法案例——辗转相除法和更相减损术》（新人教A版必修3）课件.ppt

《131《算法案例——辗转相除法和更相减损术》（新人教A版必修3）课件.ppt》由会员分享，可在线阅读，更多相关《131《算法案例——辗转相除法和更相减损术》（新人教A版必修3）课件.ppt（27页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、v主讲老师 潘学国思考：思考：18与与30的最大公约数是多少？你是怎样得到的最大公约数是多少？你是怎样得到的？的？先用两个数公有的质因数连续去除，一直除到先用两个数公有的质因数连续去除，一直除到所得的商是互质数为止，然后把所有的除数连乘起所得的商是互质数为止，然后把所有的除数连乘起来即为最大公约数来即为最大公约数.1823091535318与与30的最大公约数的最大公约数是是23=6.短除法短除法快乐回顾快乐回顾 提出问题提出问题“求两个正整数的最大求两个正整数的最大公约数公约数”是数学中的一是数学中的一个基础性问题，它有多个基础性问题，它有多种解决办法，以前我们种解决办法，以前我们通常用短除

2、法。但是，通常用短除法。但是，当两个数公有的质因数当两个数公有的质因数较大时，使用上述方法较大时，使用上述方法就比较困难。下面我们就比较困难。下面我们介绍两种古老而有效的介绍两种古老而有效的方法。方法。思考：思考：对于对于8251与与6105这两个数，由于其公有的质这两个数，由于其公有的质因数较大，利用短除法求最大公约数就比较困难。因数较大，利用短除法求最大公约数就比较困难。那么，有其它解决的办法吗那么，有其它解决的办法吗?我们注意到我们注意到8251=61051+2146，故，故6105与与2146的公约数也是的公约数也是8251与与6105的公约数，反过来，的公约数，反过来，8251与与6

3、105的公的公约数也是约数也是6105与与2146的公约数，那么，它们的最大的公约数，那么，它们的最大公约数有什么关系呢？公约数有什么关系呢？相等相等.辗转相除法辗转相除法思考：思考：又又6105=21462+1813，同理，同理，6105与与2146的最大公约数和的最大公约数和2146与与1813的最大公约数相等。重的最大公约数相等。重复上述操作，你能得到复上述操作，你能得到8251与与6105这两个数的最大这两个数的最大公约数吗？公约数吗？2146=18131+333，148=374+0.333=1482+37，1813=3335+148，8251=61051+2146，6105=2146

4、2+1813，最大公约数是最大公约数是37.37.思考：思考：上述方法就是上述方法就是辗转相除法辗转相除法。那么，辗转相除。那么，辗转相除法的具体算法又是怎样操作的呢？法的具体算法又是怎样操作的呢？对于给定的两个正整数，用较大的数除以较小对于给定的两个正整数，用较大的数除以较小的数。若余数不为零，则将余数和较小的数构成新的数。若余数不为零，则将余数和较小的数构成新的一对数，继续上面的除法，直到大数被小数除尽，的一对数，继续上面的除法，直到大数被小数除尽，则这时较小的数就是原来两个数的最大公约数。这则这时较小的数就是原来两个数的最大公约数。这种算法是由欧几里得在公元前种算法是由欧几里得在公元前3

5、00300年左右首先提出年左右首先提出的，因而又叫的，因而又叫欧几里得算法欧几里得算法。练习：练习：1 1、用辗转相除法求用辗转相除法求225225和和135135的最大公约的最大公约数。数。225=1351+90135=901+4590=452+0225225和和135135的最大公约数是的最大公约数是4545.快乐练习快乐练习练习练习2 2：利用辗转相除法求两数利用辗转相除法求两数40814081与与2072320723的最大的最大公约数公约数.20723=40815+318;4081=31812+265;318=2651+53;265=535+0.40814081和和2072320723

6、的最大公约数是的最大公约数是5353.其中包含重复操作的步骤，其中包含重复操作的步骤，实际上是一个循环结构实际上是一个循环结构。8251=61051+2146 6105=21462+1813 2146=18131+3331813=3335+148333=1482+37148=374+0m=nqr用程序框图表示出右边的过程：用程序框图表示出右边的过程：r=m MOD nm=nn=rr=0?是是否否观察：观察：辗转相除法中的关键步骤是那种逻辑结构？辗转相除法中的关键步骤是那种逻辑结构？思考：思考：求两个正整数求两个正整数m，n的最大公约数，可以用循环的最大公约数，可以用循环结构来构造算法？其算法步

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

8、如该程序框图对应的程序如何表述？何表述？INPUT m，nDOr=m MOD nm=nn=rLOOP UNTIL r=0PRINT mEND开始开始输入入m，n求求m除以除以n的余数的余数rm=nn=rr=0？是是输出出m结束结束否否思考：思考：你用当型循环结构构造算法，求两个正整数的你用当型循环结构构造算法，求两个正整数的最大公约数吗？试写出算法步骤、程序框图和程序。最大公约数吗？试写出算法步骤、程序框图和程序。算法设计：算法设计：第一步，给定两个正整数第一步，给定两个正整数m m，n(mn).n(mn).第二步，若第二步，若n0n0，计算，计算m m除以除以n n所得的余数所得的余数r r

9、.m=nm=n，n=n=r.否则否则,m,m，n n的最大公约数等于的最大公约数等于m m。开始开始输入入m，n求求m除以除以n的余数的余数rm=nn0？否否输出输出m结束结束是是n=rINPUT m，nWHILE n0r=m MOD nm=nn=rWENDPRINT mEND “可半者半之，不可半者，副置分母、子之数，以少减多，可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也。以等数约之。更相减损，求其等也。以等数约之。”第一步，任意给定两个正整数，判断他们是否都是偶数。第一步，任意给定两个正整数，判断他们是否都是偶数。若是，则用若是，则用2 2约简；若不是，执行第二步。

10、约简；若不是，执行第二步。第二步，以较大的数减较小的数，接着把所得的差与较第二步，以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的小的数比较，并以大数减小数。继续这个操作，直到所得的数相等为止，则这个数（等数）或这个数与约简的数的乘积数相等为止，则这个数（等数）或这个数与约简的数的乘积就是所求的最大公约数。就是所求的最大公约数。九章算术九章算术是中国古代的数学专著，其中的是中国古代的数学专著，其中的“更相减损术更相减损术”也可以用来求两个数的最大公约数，即也可以用来求两个数的最大公约数，即 翻译为现代语言如下：翻译为现代语言如下：更相减损术更相减损术

11、例例1：用更相减损术求用更相减损术求98与与63的最大公约数。的最大公约数。98-63=35，14-7=7.21-7=14，28-7=21，35-28=7，63-35=28，最大公约数是最大公约数是7.思考：思考：把更相减损术与辗转相除法比较，你有什么发把更相减损术与辗转相除法比较，你有什么发现？你能根据更相减损术设计程序，求两个正整数的现？你能根据更相减损术设计程序，求两个正整数的最大公约数吗？最大公约数吗？第一步，给定两个正整数第一步，给定两个正整数m m，n(mn).n(mn).第二步，若第二步，若m m，n n都是偶数，则不断用都是偶数，则不断用2 2约简，使它约简，使它们不同时为偶数

12、，约简后的两个数仍记为们不同时为偶数，约简后的两个数仍记为m m，n.n.第三步，第三步，d=m-n.d=m-n.第四步，判断第四步，判断“dndn”是否成立。若是，则将是否成立。若是，则将n n，d d中较大者记为中较大者记为m m，较小者记为，较小者记为n n，返回第三步，否，返回第三步，否则，则，2k2k*d d（k k为约简整数的为约简整数的2 2的个数）为所求的最的个数）为所求的最大公约数。大公约数。算法设计：算法设计：INPUT “m，n=”；m，nk=0WHILE m MOD 2=0 AND n MOD 2=0 m=m/2 n=n/2 k=k+1WEND d=m-nWHILE d

13、n IF dn THEN m=d ELSE m=n n=d End IF d=m-nWEND d=2k*dPRINT dEND 程序：程序：例例2 2：分别用辗转相除法和更相减损术求分别用辗转相除法和更相减损术求168168与与9393的最大公约数的最大公约数.辗转相除法：辗转相除法：168=931+75，93=751+18，75=184+3，18=36+0.典例剖析典例剖析 例例2 2：分别用辗转相除法和更相减损术求分别用辗转相除法和更相减损术求168168与与9393的最大公约数的最大公约数.典例剖析典例剖析更相减损术更相减损术:168-93=75，93-75=18，75-18=57，57

14、-18=39，39-18=21，21-18=3，18-3=15，15-3=12，12-3=9，9-3=6，6-3=3.例例3 3：求求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三个数

15、的最大公约数是三个数的最大公约数是5.5.课时小结课时小结:1、辗转相除法，就是对于给定的两个正整数，、辗转相除法，就是对于给定的两个正整数，用较大的数除以较小的数，若余数不为零，则将用较大的数除以较小的数，若余数不为零，则将余数和较小的数构成新的一对数，继续上面的除余数和较小的数构成新的一对数，继续上面的除法，直到大数被小数除尽为止，这时的较小的数法，直到大数被小数除尽为止，这时的较小的数即为原来两个数的最大公约数即为原来两个数的最大公约数.2、更相减损术，就是对于给定的两个正整数，、更相减损术，就是对于给定的两个正整数，用较大的数减去较小的数，然后将差和较小的数用较大的数减去较小的数，然后

16、将差和较小的数构成新的一对数，继续上面的减法，直到差和较构成新的一对数，继续上面的减法，直到差和较小的数相等，此时相等的两数即为原来两个数的小的数相等，此时相等的两数即为原来两个数的最大公约数最大公约数.课时小结课时小结:比较辗转相除法与更相减损术的区别比较辗转相除法与更相减损术的区别（1 1）都是求最大公约数的方法，计算上辗转相除）都是求最大公约数的方法，计算上辗转相除法以除法为主，更相减损术以减法为主，计算次数法以除法为主，更相减损术以减法为主，计算次数上辗转相除法计算次数相对较少，特别当两个数字上辗转相除法计算次数相对较少，特别当两个数字大小区别较大时计算次数的区别较明显。大小区别较大时计算次数的区别较明显。（2 2）从结果体现形式来看，辗转相除法体现结果）从结果体现形式来看，辗转相除法体现结果是以相除余数为是以相除余数为0 0则得到，而更相减损术则以减数与则得到，而更相减损术则以减数与差相等而得到。差相等而得到。1：P45 练习练习12：P48 A组组 13：资料：资料作业布置作业布置