辗转相除法课件

关于辗转相除法第1页，讲稿共19页，2023年5月2日，星期三知识探究（一）:辗转相除法思考1:18与30的最大公约数是多少？你是怎样得到的？

先用两个数公有的质因数连续去除，一直除到所得的商是互质数为止，然后把所有的除数连乘起来即为最大公约数.第2页，讲稿共19页，2023年5月2日，星期三思考2:对于8251与6105这两个数，由于其公有的质因数较大，利用上述方法求最大公约数就比较困难.注意到8251=6105×1+2146，那么8251与6105这两个数的公约数和6105与2146的公约数有什么关系？第3页，讲稿共19页，2023年5月2日，星期三思考3:又6105=2146×2+1813，同理，6105与2146的公约数和2146与1813的公约数相等.重复上述操作，你能得到8251与6105这两个数的最大公约数吗？2146=1813×1+333，148=37×4+0.333=148×2+37，1813=333×5+148，8251=6105×1+2146，6105=2146×2+1813，第4页，讲稿共19页，2023年5月2日，星期三

辗转相除法是一个反复执行直到余数等于0停止的步骤，这实际上是一个循环结构。8251=6105×1+21466105=2146×2+18132146=1813×1+3331813=333×5+148333=148×2+37148=37×4+0m=n×q＋r用程序框图表示出右边的过程r=mMODnm=nn=rr=0?是否思考4：辗转相除法中的关键步骤是哪种逻辑结构？第5页，讲稿共19页，2023年5月2日，星期三思考5:上述求两个正整数的最大公约数的方法称为辗转相除法或欧几里得算法.一般地，用辗转相除法求两个正整数m，n的最大公约数，可以用什么逻辑结构来构造算法？其算法步骤如何设计？第一步，给定两个正整数m，n(m>n).第二步，计算m除以n所得的余数r.第三步，m=n，n=r.第四步，若r=0，则m，n的最大公约数等 于m；否则，返回第二步.

第6页，讲稿共19页，2023年5月2日，星期三思考6:该算法的程序框图如何表示？开始输入m，n求m除以n的余数rm=nn=rr=0？是输出m结束否第7页，讲稿共19页，2023年5月2日，星期三思考7:该程序框图对应的程序如何表述？INPUTm，nDOr=mMODnm=nn=rLOOPUNTILr=0PRINTmEND开始输入m，n求m除以n的余数rm=nn=rr=0？是输出m结束否第8页，讲稿共19页，2023年5月2日，星期三思考8:如果用当型循环结构构造算法，则用辗转相除法求两个正整数m，n的最大公约数的程序框图和程序分别如何表示？第9页，讲稿共19页，2023年5月2日，星期三开始输入m，n求m除以n的余数rm=nr>0？否输出m结束是n=rINPUTm，nWHILEr>0r=mMODnm=nn=rWENDPRINTmEND第10页，讲稿共19页，2023年5月2日，星期三练习1：利用辗转相除法求两数4081与20723的最大公约数.(53)20723=4081×5+318;4081=318×12+265;318=265×1+53;265=53×5+0.第11页，讲稿共19页，2023年5月2日，星期三更相减损术“更相减损术”（也是求两个正整数的最大公约数的算法）步骤：第一步：任意给定两个正整数；判断他们是否都是偶数。若是，则用2约简；若不是则执行第二步。第二步：以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止，则这个等数或这个数与约简的数的乘积就是所求的最大公约数。第12页，讲稿共19页，2023年5月2日，星期三例、用更相减损术求98与63的最大公约数（自己按照步骤求解）解：由于63不是偶数，把98和63以大数减小数，并辗转相减。所以，98和63的最大公约数等于7。98-63=35

63-35=2835-28=728-7=2121-7=1414-7=7第13页，讲稿共19页，2023年5月2日，星期三更相减损是一个反复执行直到减数等于差时停止的步骤，这实际也是一个循环结构

思考：更相减损直到何时结束？运用的是哪种算法结构？第14页，讲稿共19页，2023年5月2日，星期三程序：INPUT“a,b”;a,bi=0WHILEaMOD2=0ANDbMOD2=0a=a/2b=b/2i=i+1WENDDOIFb>aTHENt=aa=bb=tENDIFa=a-bLOOPUNTILa=bPRINTa*2^iEND开始输入：a,b输出：a×2i结束a=b?a=a/2,b=b/2Ya=a-bt=a,a=b,b=tb>a?aMOD2=0且bMOD2=0?YNNNYi=0i=i+1第15页，讲稿共19页，2023年5月2日，星期三

例2分别用辗转相除法和更相减损术求168与93的最大公约数.辗转相除法：168=93×1+75， 93=75×1+18， 75=18×4+3， 18=3×6.第16页，讲稿共19页，2023年5月2日，星期三更相减损术:168-93=75，

93-75=18，

75-18=57，

57-18=39，

39-18=21，

21-18=3，

18-3=15，

15-3=12，

12-3=9，