《辗转相除法学习.pptx》由会员分享，可在线阅读，更多相关《辗转相除法学习.pptx（19页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、知识探究（一）:辗转相除法思考1:1:1818与3030的最大公约数是多少？你是怎样得到的？先用两个数公有的质因数连续去除，先用两个数公有的质因数连续去除，一直除到所得的商是互质数为止，然一直除到所得的商是互质数为止，然后把所有的除数连乘起来即为最大公后把所有的除数连乘起来即为最大公约数约数.第1页/共19页思考2:2:对于82518251与61056105这两个数，由于其公有的质因数较大，利用上述方法求最大公约数就比较困难.注意到8251=61051+21468251=61051+2146，那么82518251与61056105这两个数的公约数和61056105与21462146的公约数有什
2、么关系？第2页/共19页思考3:3:又6105=21462+18136105=21462+1813，同理，61056105与21462146的公约数和21462146与18131813的公约数相等.重复上述操作，你能得到82518251与61056105这两个数的最大公约数吗？21462146=181318131+1+333333，148148=37374+0.4+0.333333=1481482+2+3737，18131813=3333335+5+148148，8251=8251=610561051+1+21462146，61056105=214621462+2+18131813，第3页/共
3、19页 辗转相除法是一个反复执行直到余数等于0停止的步骤，这实际上是一个循环结构。8251=61051+2146 6105=21462+1813 2146=18131+3331813=3335+148333=1482+37148=374+0m=n q r用程序框图表示出右边的过程r=m MOD nm=nn=rr=0?是否第4页/共19页思考5:5:上述求两个正整数的最大公约数的方法称为辗转相除法或欧几里得算法.一般地，用辗转相除法求两个正整数m m，n n的最大公约数，可以用什么逻辑结构来构造算法？其算法步骤如何设计？第一步，给定两个正整数第一步，给定两个正整数m m，n(mn(mn).n).
4、第二步，计算第二步，计算m m除以除以n n所得的余数所得的余数r.r.第三步，第三步，m=nm=n，n=r.n=r.第四步，若第四步，若r=0r=0，则，则m m，n n的最大公约数等的最大公约数等 于于m m；否则，返回第二步；否则，返回第二步.第5页/共19页思考6:6:该算法的程序框图如何表示？开始输入m，n求m除以n的余数rm=nn=rr=0？是输出m结束否第6页/共19页思考7:7:该程序框图对应的程序如何表述？INPUT mINPUT m，n nDODOr=m MODnr=m MODnm=nm=nn=rn=rLOOP UNTIL r=0LOOP UNTIL r=0PRINT mP
5、RINT mENDEND开始输入m，n求m除以n的余数rm=nn=rr=0？是输出m结束否第7页/共19页思考8:8:如果用当型循环结构构造算法，则用辗转相除法求两个正整数m m，n n的最大公约数的程序框图和程序分别如何表示？第8页/共19页开始输入m，n求m除以n的余数rm=nr0？否输出m结束是n=rINPUT mINPUT m，n nWHILE rWHILE r0 0r=m MOD nr=m MOD nm=nm=nn=rn=rWENDWENDPRINT mPRINT mENDEND第9页/共19页练习练习1 1：利用辗转相除法求两数：利用辗转相除法求两数40814081与与207232
6、0723的最大公约数的最大公约数.(53)(53)20723=40815+318;4081=31812+265;318=2651+53;265=535+0.第10页/共19页更相减损术“更相减损术”（也是求两个正整数的最大公约数的算法）步骤：第一步：任意给定两个正整数；判断他们是否都是偶数。若是，则用2约简；若不是则执行第二步。第二步：以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止，则这个等数或这个数与约简的数的乘积就是所求的最大公约数。第11页/共19页例、用更相减损术求98与63的最大公约数（自己按照步骤求解）解：由于63不是偶
7、数，把98和63以大数减小数，并辗转相减。所以，98和63的最大公约数等于7。98-63=3563-35=2835-28=728-7=2121-7=1414-7=7第12页/共19页更相减损是一个反复执行直到减数等于差时停止的步骤，这实际也是一个循环结构 思考：更相减损直到何时结束？运用的是哪种算法结构？第13页/共19页程序：INPUT“a,b”;a,bi=0WHILE a MOD 2=0 AND b MOD 2=0 a=a/2 b=b/2 i=i+1 WEND DOIF ba THENt=aa=bb=tEND IFa=a-bLOOP UNTIL a=bPRINT a*2iEND开始输入：a
8、,b输出：a2i结束a=b?a=a/2,b=b/2Ya=a-bt=a,a=b,b=tba?aMOD2=0且bMOD2=0?YNNNYi=0i=i+1第14页/共19页 例2 2 分别用辗转相除法和更相减损术求168168与9393的最大公约数.辗转相除法：168=931+75168=931+75，93=751+1893=751+18，75=184+375=184+3，18=36.18=36.第15页/共19页更相减损术:168-93=75:168-93=75，93-75=1893-75=18，75-18=5775-18=57，57-18=3957-18=39，39-18=2139-18=21，
9、21-18=321-18=3，18-3=1518-3=15，15-3=1215-3=12，12-3=912-3=9，9-3=69-3=6，6-3=3.6-3=3.第16页/共19页例例3 3：用辗转相除法和更相减损术求：用辗转相除法和更相减损术求210210与与714714的最大公约数的最大公约数.第17页/共19页比较辗转相除法与更相减损术的区别比较辗转相除法与更相减损术的区别（1 1）都是求最大公约数的方法，计算上辗转相除）都是求最大公约数的方法，计算上辗转相除法以除法为主，更相减损术以减法为主，计算次数法以除法为主，更相减损术以减法为主，计算次数上辗转相除法计算次数相对较少，特别当两个数字上辗转相除法计算次数相对较少，特别当两个数字大小区别较大时计算次数的区别较明显。大小区别较大时计算次数的区别较明显。（2 2）从结果体现形式来看，辗转相除法体现结果）从结果体现形式来看，辗转相除法体现结果是以相除余数为是以相除余数为0 0则得到，而更相减损术则以减数与则得到，而更相减损术则以减数与差相等而得到差相等而得到小结小结第18页/共19页感谢您的观看！第19页/共19页