《131辗转相除法与更相减损术》由会员分享，可在线阅读，更多相关《131辗转相除法与更相减损术（20页珍藏版）》请在金锄头文库上搜索。
1、1.3 1.3 算法案例算法案例 第一课时第一课时 1.1.求两个正整数的最大公约数求两个正整数的最大公约数. .（1 1）求）求2525和和3535的最大公约数；的最大公约数；（2 2）求）求1818和和3 30 0的最大公约数的最大公约数. .2.2.求求82518251和和61056105的最大公约数的最大公约数. . 25（1） 55357 所以，所以，2525和和3535的最大的最大公约数为公约数为5 5， 所以，所以，1818和和3 30 0的最的最大公约数为大公约数为2 23=63=6. .18（2） 29 3015335 第一步第一步 用两数中较大的数除以较小的数，求用两数中较
2、大的数除以较小的数，求得商和余数得商和余数 8251=61058251=61051+21461+2146。 结论：结论： 82518251和和61056105的公约数就是的公约数就是61056105和和21462146的公约数，求的公约数，求82518251和和61056105的最大公约数，只要求的最大公约数，只要求出出61056105和和21462146的公约数就可以了。的公约数就可以了。 第二步第二步 对对61056105和和21462146重复第一步的做法，重复第一步的做法，6105=21466105=21462+18132+1813。 同理同理61056105和和21462146的最大
3、公约数也是的最大公约数也是21462146和和18131813的最大公约数。的最大公约数。2.2.求求82518251和和61056105的最大公约数的最大公约数. . 完整的过程完整的过程8251=61051+2146 6105=21462+1813 2146=18131+3331813=3335+148333=1482+37148=374+0 显然显然37是是148和和37的最大公约数，也就的最大公约数，也就是是8251和和6105的最的最大公约数。大公约数。辗转相除法（欧几里得算法）辗转相除法（欧几里得算法）例例 用辗转相除法求用辗转相除法求225225和和135135的最大公约数的最大
4、公约数225=1351+90135=901+4590=452 显然显然4545是是9090和和4545的最大公约数，也就是的最大公约数，也就是225225和和135135的最大公约数的最大公约数 思考思考1 1：从上面的两个例子可以看出计算的：从上面的两个例子可以看出计算的规律是什么？规律是什么？ S S1 1：用第一个数除以第二个数：用第一个数除以第二个数。S S2 2：除数变成被除数，余数变成除数：除数变成被除数，余数变成除数S S3 3：重复：重复S S1 1，直到余数为，直到余数为0 0。个人简介 欧几里德(Euclid of Alexandria)，生活在亚历山大城的欧几里得（约前3
5、30约前275）是古希腊最享有盛名的数学家。以其所著的几何原本(简称原本）闻名于世。欧几里德辗转相除法辗转相除法 又叫欧几里德算法，又叫欧几里德算法，是由欧几里德在公元前是由欧几里德在公元前300300年左右年左右首先提出的，是一种古老而有效首先提出的，是一种古老而有效的算法。的算法。思考思考: :上述求两个正整数的最大公约数的上述求两个正整数的最大公约数的方法称为方法称为辗转相除法辗转相除法或或欧几里得算法欧几里得算法. .一一般地，用辗转相除法求两个正整数般地，用辗转相除法求两个正整数m m，n n的最大公约数，可以用什么逻辑结构来的最大公约数，可以用什么逻辑结构来构造算法？其算法步骤如何
6、设计？构造算法？其算法步骤如何设计？ 第一步，给定两个正整数第一步，给定两个正整数m m，n(mn(mn).n).第二步，计算第二步，计算m m除以除以n n所得的余数所得的余数r. r. 第三步，第三步，m=nm=n，n=r.n=r.第四步，若第四步，若r=0r=0，则，则m m，n n的最大公约数等的最大公约数等 于于m m；否则，返回第二步；否则，返回第二步. . 思考思考: :该算法的程序框图如何表示？该算法的程序框图如何表示？开始开始输入输入m，n求求m除以除以n的余数的余数rm=nn=rr=0？是是输出输出m结束结束否否思考思考: :该程序框图对应的程序如何表述？该程序框图对应的程
7、序如何表述？INPUT mINPUT m，n nDODOr=m r=m MODnMODnm=nm=nn=rn=rLOOP UNTILLOOP UNTIL r=0r=0PRINT mPRINT mENDEND开始开始输入输入m，n求求m除以除以n的余数的余数rm=nn=rr=0？是是输出输出m结束结束否否思考思考7:7:如果用当型循环结构构造算法，如果用当型循环结构构造算法，则用辗转相除法求两个正整数则用辗转相除法求两个正整数m m，n n的最的最大公约数的程序框图和程序分别如何表大公约数的程序框图和程序分别如何表示？示？开始开始输入输入m，n求求m除以除以n的余数的余数rm=nn0？否否输出输
8、出m结束结束是是n=rINPUT mINPUT m，n nWHILEWHILE n n0 0r=m r=m MODnMODnm=nm=nn=rn=rWENDWENDPRINT mPRINT mENDEND知识探究（二）知识探究（二）: :更相减损术更相减损术 思考思考1:1:设两个正整数设两个正整数m mn n，若，若m-nm-n=k=k，则，则m m与与n n的最大公约数和的最大公约数和n n与与k k的最大公约数相的最大公约数相等等. .反复利用这个原理，可求得反复利用这个原理，可求得9898与与6363的的最大公约数为多少？最大公约数为多少？98-63=3598-63=35，14-7=7
9、.14-7=7.21-7=1421-7=14，28-7=2128-7=21，35-28=735-28=7，63-35=2863-35=28，一般步骤一般步骤：首先两正首先两正数是否都数是否都是偶数是偶数思考思考: :上述求两个正整数的最大公约数的上述求两个正整数的最大公约数的方法称为方法称为更相减损术更相减损术. .一般地，用更相减一般地，用更相减损术求两个正整数损术求两个正整数m m，n n的最大公约数，的最大公约数，可以用什么逻辑结构来构造算法？其算可以用什么逻辑结构来构造算法？其算法步骤如何设计？法步骤如何设计？第一步，给定两个正整数第一步，给定两个正整数m m，n(mn(mn).n).
10、 第二步，计算第二步，计算m-nm-n所得的差所得的差k. k. 第三步，比较第三步，比较n n与与k k的大小，其中大者用的大小，其中大者用m m表表 示，小者用示，小者用n n表示表示. . 第四步，若第四步，若m=nm=n，则，则m m，n n的最大公约数等于的最大公约数等于 m m；否则，返回第二步；否则，返回第二步. . 思考思考: :该算法的程序框图如何表示？该算法的程序框图如何表示？开始开始输入输入m，nnk？m=n是是输出输出m结束结束mn？k=m- -n是是否否n=km=k否否思考思考: :该程序框图对应的程序如何表述？该程序框图对应的程序如何表述？INPUT mINPUT
11、m，n nWHILE WHILE m mn nk=k=m-nm-nIF nIF nk THENk THENm=nm=nn=kn=kELSEELSEm=km=kEND IFEND IFWENDWENDPRINT mPRINT mENDEND开始开始输入输入m，nnk？m=n是是输出输出m结束结束mn？k=m- -n是是否否n=km=k否否理论迁移理论迁移 例例1 1 分别用辗转相除法和更相减损分别用辗转相除法和更相减损术求术求168168与与9393的最大公约数的最大公约数. . 辗转相除法：辗转相除法：168=93168=931+751+75， 93=7593=751+181+18， 75=1
12、875=184+34+3， 18=318=36.6.更相减损术更相减损术: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. 例例2 2 求求325325，130130，270270三个数的最大三个数的最大公约数公约数. . 因为因为325=130325=1302+652+65，130=65
13、130=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三个数的最大公约三个数的最大公约数是数是5.5.用更相减损术求244与88的最小公倍数？（1 1）都是求最大公约数的方法，在计算上辗转）都是求最大公约数的方法，在计算上辗转相除法以相除法以除法除法为主，更相减损术以为主，更相减损术以减法减法为主；计为主；计算次数上辗转相除法计算次数相对较少，特别当算次数上辗转相除法计算次数相对较少，特别当两个数字大小区别较大时计算次数的区别较明显。两个数字大小区别较大时计算次数的区别较明显。（2 2）从结果体现形式来看，辗转相除法体现结）从结果体现形式来看，辗转相除法体现结果是以相除果是以相除余数为余数为0 0而得到，而更相减损术则以而得到，而更相减损术则以减数与差相等减数与差相等而得到。实质上都是不断而得到。实质上都是不断递归递归的过的过程，都要用程，都要用循环结构循环结构来实现。来实现。辗转相除法与更相减损术的异同：辗转相除法与更相减损术的异同：
