辗转相除法教学教材

1、第一页，共19页。知识探究（一）知识探究（一）:辗转辗转(zhnzhun)相除法相除法思考思考(sko)1:18(sko)1:18与与3030的最大公约数是多的最大公约数是多少？你是怎样得到的？少？你是怎样得到的？ 先用两个数公有的质因数连续去除先用两个数公有的质因数连续去除(q ch)(q ch)，一直除到所得的商是互质，一直除到所得的商是互质数为止，然后把所有的除数连乘起来即数为止，然后把所有的除数连乘起来即为最大公约数为最大公约数. . 第二页，共19页。思考思考2:2:对于对于82518251与与61056105这两个数，由于其公这两个数，由于其公有的质因数较大，利用上述方法求最大公约

2、有的质因数较大，利用上述方法求最大公约数就比较困难数就比较困难. .注意注意(zh y)(zh y)到到8251=61058251=61051+21461+2146，那么，那么82518251与与61056105这两这两个数的公约数和个数的公约数和61056105与与21462146的公约数有什么的公约数有什么关系？关系？ 第三页，共19页。思考思考3:3:又又6105=21466105=21462+18132+1813，同理，同理，61056105与与21462146的公约数和的公约数和21462146与与18131813的公约的公约数相等数相等(xingdng).(xingdng).重复上

3、述操作，你能重复上述操作，你能得到得到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，第四页，共19页。 辗转相除法是一个反复辗转相除法是一个反复(fnf)(fnf)执行直到余数等于执行直到余数等于0 0停止的步骤，这实停止的步骤，

4、这实际上是一个循环结构。际上是一个循环结构。8251=61051+2146 6105=21462+1813 2146=18131+3331813=3335+148333=1482+37148=374+0m = n q r用程序框图表示用程序框图表示(biosh)出右边的过出右边的过程程r=m MOD nm = nn = rr=0?是否第五页，共19页。思考思考5:5:上述求两个正整数的最大公约数的方上述求两个正整数的最大公约数的方法称为辗转相除法或欧几里得算法法称为辗转相除法或欧几里得算法(sun (sun f).f).一般地，用辗转相除法求两个正整数一般地，用辗转相除法求两个正整数m m，n

5、 n的最大公约数，可以用什么逻辑结构来构的最大公约数，可以用什么逻辑结构来构造算法造算法(sun f)(sun f)？其算法？其算法(sun f)(sun f)步骤如步骤如何设计？何设计？ 第一步，给定第一步，给定( (i dni dn) )两个正整数两个正整数m m，n(mn).n(mn).第二步，计算第二步，计算(j sun)m(j sun)m除以除以n n所得的所得的余数余数r. r. 第三步，第三步，m=nm=n，n=r.n=r.第四步，若第四步，若r=0r=0，则，则m m，n n的最大公约数等的最大公约数等 于于m m；否则，返回第二步；否则，返回第二步. . 第六页，共19页。思

6、考思考6:6:该算法该算法(sun f)(sun f)的程序框图如何的程序框图如何表示？表示？开始开始输入输入m，n求求m除以除以n的余数的余数rm=nn=rr=0？是是输出输出m结束结束否否第七页，共19页。思考思考7:7:该程序框图对应该程序框图对应(duyng)(duyng)的程序的程序如何表述？如何表述？INPUT mINPUT m，n nDODOr=m MODnr=m MODnm=nm=nn=rn=rLOOP UNTIL r=0LOOP UNTIL r=0PRINT mPRINT mENDEND开始开始输入输入m，n求求m除以除以n的余数的余数rm=nn=rr=0？是是输出输出m结束

7、结束否否第八页，共19页。思考思考8:8:如果用当型循环结构构造如果用当型循环结构构造(guzo)(guzo)算法，则用辗转相除法求两个正整数算法，则用辗转相除法求两个正整数m m，n n的最大公约数的程序框图和程序分别如何的最大公约数的程序框图和程序分别如何表示？表示？第九页，共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第十页，共19页。练习练习(

8、linx)1(linx)1：利用辗转相除法求两数：利用辗转相除法求两数40814081与与2072320723的最大公约数的最大公约数. . (53)(53)20723=40815+318;4081=31812+265;318=2651+53;265=535+0.第十一页，共19页。更相减损更相减损(jin sn)术术“更相减损术更相减损术”（也是求两个（也是求两个(lin )正整数的最大公约数的算法）正整数的最大公约数的算法）步骤：步骤：第一步：任意给定两个第一步：任意给定两个(lin )(lin )正整数；判断他们是否都是偶数。正整数；判断他们是否都是偶数。若是，则用若是，则用2 2约简；

9、若不是则执行第二步。约简；若不是则执行第二步。第二步：以较大的数减较小的数，接着把所得的差与较第二步：以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止，则这个等数或这个数与约简的得的减数和差相等为止，则这个等数或这个数与约简的数的乘积就是所求的最大公约数。数的乘积就是所求的最大公约数。第十二页，共19页。例、用更相减损例、用更相减损(jin sn)(jin sn)术求术求9898与与6363的最大公约数的最大公约数（自己按照步骤求解）（自己按照步骤求解）解：由于解：由于6363不是偶数不

10、是偶数(u sh)(u sh)，把，把9898和和6363以大数减小数，并辗转相减。以大数减小数，并辗转相减。所以所以(suy)(suy)，9898和和6363的最大公约数等于的最大公约数等于7 7。98-63=35 63-35=2835-28=728-7=2121-7=1414-7=7第十三页，共19页。更相减损是一个反复执行直到减数等于差时停止(tngzh)的步骤，这实际也是一个循环结构 思考：更相减损直到何时(h sh)结束？运用的是哪种算法结构？第十四页，共19页。程序(chngx)：INPUT “a,b”;a,bi=0WHILE a MOD 2=0 AND b MOD 2=0 a=a

11、/2 b=b/2 i=i+1 WEND DOIF ba THENt=aa=bb=tEND IFa=a-bLOOP UNTIL a=bPRINT a*2iEND开始开始输入：输入：a,b输出：输出：a2i结束结束a=b?a=a/2,b=b/2Ya=a-bt=a,a=b,b=tba?a MOD 2=0且且b MOD 2=0?YNNNYi=0i=i+1第十五页，共19页。 例2 分别用辗转相除法(chf)和更相减损术求168与93的最大公约数. 辗转辗转(zhnzhun)(zhnzhun)相除法：相除法：168=93168=931+751+75， 93=7593=751+181+18， 75=187

12、5=184+34+3， 18=318=36.6.第十六页，共19页。更相减损更相减损(jin sn)(jin sn)术术: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， 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.第十七页，共19页。例例3 3：用辗转：用辗转(zhnzhun)(zhnzhun)相除法和更相减损相除法和更相减损术求术求210210与与714714的最大公约数的最大公约数. .第十八页，共19页。比较辗转相除法与更相减损比较辗转相除法与更相减损(jin sn)(jin sn)术的区别术的区别（1 1）都是求最大公约数的方法，计算上辗转相除）都是求最大公约数的方法，计算上辗转相除法以除法为主，更相减损法以除法为主，更相减损(jin sn)(jin sn)术以减法为主，术以减法为主，计算次数上辗转相除法计算次数相对较少，特别当计算次数上辗