《有关辗转相除法和更相减损术的问题【医学技术】》由会员分享，可在线阅读，更多相关《有关辗转相除法和更相减损术的问题【医学技术】（17页珍藏版）》请在金锄头文库上搜索。
1、有关辗转相除法和更相减损术的问题1医疗技能探究一, ,辗转相除法思考思考1:在小学中我们是如何求出两个正整数的最大公约数的在小学中我们是如何求出两个正整数的最大公约数的呢呢?算法案例算法案例之求最大公约数之求最大公约数求以下几组正整数的最大公约数。(注：若整数m和n满足n整除m，则（m,n）=n。用（m,n）来表示m和n的最大公约数。)（1）（18，30） （2）（24，16）（3）（63，63） （4）（72，8） （5）（301，133 ）解：2 1 8 2 4 用公有质因数2除， 3 9 1 2 用公有质因数3除， 3 4 3和4互质不除了。 得：18和24最大公约数是：236 例、求1
2、8与24的最大公约数：6；8；63；8；7；短除法短除法想一想，如何求8251与6105的最大公约数？ 2医疗技能 思考思考2:2:对于对于82518251与与61056105这两个数，它们这两个数，它们的最大公的最大公约数是多少？你是怎样得到的？约数是多少？你是怎样得到的？ 由于它们公有的质因数较大，利用上述方法求最由于它们公有的质因数较大，利用上述方法求最大公约数就比较困难大公约数就比较困难. .有没有其它的方法可以较简单有没有其它的方法可以较简单的找出它们的最大公约数呢？的找出它们的最大公约数呢？3医疗技能 思考思考3 3：注意到：注意到8251=61058251=61051+21461
3、+2146，那么，那么82518251与与61056105这两个数的公约数和这两个数的公约数和61056105与与21462146的公约数有什么的公约数有什么关系？关系？ 我们发现我们发现6105=21466105=21462+18132+1813，同理，同理，61056105与与21462146的公约数和的公约数和21462146与与18131813的公约数相等的公约数相等. . 思考思考4 4：重复上述操作，你能得到：重复上述操作，你能得到82518251与与61056105这这两个数的最大公约数吗？两个数的最大公约数吗？2146=18132146=18131+3331+333，148=3
4、7148=374+0.4+0.333=148333=1482+372+37，1813=3331813=3335+1485+148，8251=61058251=61051+21461+2146，6105=21466105=21462+18132+1813，定义定义:所谓的辗转相除法,就是对于给定的两个数,用较大的数除以较小的数,若余数不为零,则将余数和较小的数构成新的数对,继续上面的除法, 直到大数被小数除尽,则这是较小的数就是原来两个数的最大公约数4医疗技能辗转相除法求两个数的最大公约数，其算法可以描述如下：辗转相除法是一个反复执行直到余数等于0停止的步骤，这实际上是一个循环结构 思考思考4
5、4：辗转相除直到何时结束？：辗转相除直到何时结束？主要运用的是哪种算法结构？主要运用的是哪种算法结构？如此循环，直到得到结果。 输入两个正整数m和n； 求余数r：计算m除以n，将所得余数存放到变量r中；更新被除数和余数：m=n，n=r。判断余数r r是否为0：若余数为0则输出结果，否则转向第步继续循环执行。5医疗技能第一步，给定两个正整数第一步，给定两个正整数m m，n(mn).n(mn).第二步，计算第二步，计算m m除以除以n n所得的余数所得的余数r. r. 第三步，第三步，m=nm=n，n=r.n=r. 第四步，若第四步，若r=0r=0，则，则m m，n n的最大公约数等于的最大公约数
6、等于m m；否则，返回第二步否则，返回第二步. . 思考思考5:5:你能把辗转相除法编成一个计算机程序吗？你能把辗转相除法编成一个计算机程序吗？6医疗技能程序框图程序框图开始开始输入输入m m，n n求求m m除以除以n n的余数的余数r rm=nm=nn=rn=rr=0r=0？是是输出输出m m结束结束否否INPUT mINPUT m，n nDODOr=m MOD nr=m MOD nm=nm=nn=rn=rLOOP UNTIL r=0LOOP UNTIL r=0PRINT mPRINT mENDEND7医疗技能 思考思考6:6:如果用当型循环结构构造算法，则用辗如果用当型循环结构构造算法，
7、则用辗转相除法求两个正整数转相除法求两个正整数m m、n n的最大公约数的程序框的最大公约数的程序框图和程序分别如何表示？图和程序分别如何表示？8医疗技能开始开始输入输入m m，n n求求m m除以除以n n的余数的余数r rm=nm=nr0r0？否否输出输出m m结束结束是是n=rn=rINPUT mINPUT m，n nWHILE r0WHILE r0r=m MOD nr=m MOD nm=nm=nn=rn=rWENDWENDPRINT mPRINT mENDEND9医疗技能练习：用辗转相除法求下列两数的最大公约数：（1）（225，135） （2）（98，196）（3）（72，168） （
8、4）（153，119）4598241710医疗技能二、更相减损术二、更相减损术 九章算术九章算术是中国古代的数学专著，其中的是中国古代的数学专著，其中的“更相减损术更相减损术”也可以用来求两个数的最大公约数，也可以用来求两个数的最大公约数，即即“可半者半之，不可半者，副置分母、子之数，可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也以少减多，更相减损，求其等也.以等数约之以等数约之.”意思是：意思是： 第一步：任意给定两个正整数，判断它们是否都第一步：任意给定两个正整数，判断它们是否都是偶数是偶数. 若是，用若是，用2约简；若不是，执行第二步约简；若不是，执行第二步. 第二
9、步：以较大的数减去较小的数，接着把差第二步：以较大的数减去较小的数，接着把差与较小的数比较，并以大数减小数与较小的数比较，并以大数减小数.继续这个操作，继续这个操作，直到所得的数相等为止，则这个等数或这个数与约直到所得的数相等为止，则这个等数或这个数与约简的数的乘积就是所求的最大公约数简的数的乘积就是所求的最大公约数.11医疗技能例例1 1：用更相减损术求：用更相减损术求9898与与6363的最大公约数的最大公约数. .98-63=3598-63=35，14-7=7.14-7=7.21-7=1421-7=14，28-7=2128-7=21，35-28=735-28=7，63-35=2863-3
10、5=28，因为因为63不是偶数，所以不是偶数，所以所以最大公约数是所以最大公约数是7.12医疗技能 例例2 2 分别用辗转相除法和更相减损术求分别用辗转相除法和更相减损术求168168与与9393的最大公约数的最大公约数. . 168=93168=931+751+75， 93=7593=751+181+18， 75=1875=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
11、=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.13医疗技能 例例4 4 求求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与与2702
12、70最大公约数是最大公约数是5. 5. 故故325325，130130，270270三个数的最大公约数是三个数的最大公约数是5.5.14医疗技能 练习练习: :用更相减损术求两个正整数用更相减损术求两个正整数m m，n n的最大公的最大公约数，可以用什么逻辑结构来构造算法？其算法步骤约数，可以用什么逻辑结构来构造算法？其算法步骤如何设计？如何设计？ 第一步，给定两个正整数第一步，给定两个正整数m m，n(mn).n(mn). 第二步，计算第二步，计算m-nm-n所得的差所得的差k. k. 第三步，比较第三步，比较n n与与k k的大小，其中大者用的大小，其中大者用m m表示，表示，小者用小者用
13、n n表示表示. . 第四步，若第四步，若m=nm=n，则，则m m，n n的最大公约数等于的最大公约数等于m m；否则，返回第二步否则，返回第二步. . 讨论讨论: :该算法的程序框图如何表示？该算法的程序框图如何表示？15医疗技能开始开始输入输入m m，n nnknk？m=nm=n是是输出输出m m结束结束mnmn？k=m-nk=m-n是是否否n=kn=km=km=k否否 讨论讨论: :该程该程序框图对应的程序框图对应的程序如何表述？序如何表述？16医疗技能INPUT mINPUT m，n nWHILE mWHILE mn nk=m-nk=m-nIF nk THENIF nk THENm=nm=nn=kn=kELSEELSEm=km=kEND IFEND IFWENDWENDPRINT mPRINT mENDEND开始开始输入输入m m，n nnknk？m=nm=n是是输出输出m m结束结束mnmn？k=m-nk=m-n是是否否n=kn=km=km=k否否17医疗技能
