高二数学必修3nbsp辗转相除法与更相减损术1

《高二数学必修3nbsp辗转相除法与更相减损术1》由会员分享，可在线阅读，更多相关《高二数学必修3nbsp辗转相除法与更相减损术1（25页珍藏版）》请在装配图网上搜索。

1、1.3算法案例算法案例 第一课时第一课时 1.1.研究一个实际问题的算法，主要从研究一个实际问题的算法，主要从算法步骤、程序框图和编写程序三方面算法步骤、程序框图和编写程序三方面展开展开.在程序框图中算法的基本逻辑结构在程序框图中算法的基本逻辑结构有哪几种？在程序设计中基本的算法语有哪几种？在程序设计中基本的算法语句有哪几种？句有哪几种？2.“2.“求两个正整数的最大公约数求两个正整数的最大公约数”是数学中的一个基础性问题，它有各种是数学中的一个基础性问题，它有各种解决办法，我们以此为案例，对该问题解决办法，我们以此为案例，对该问题的算法作一些探究的算法作一些探究.（一）（一）:辗转相除法辗转

2、相除法问题问题1:1:1818与与3030的最大公约数是多少？你的最大公约数是多少？你是怎样得到的？是怎样得到的？先用两个数公有的质因数连续去除，先用两个数公有的质因数连续去除，一直除到所得的商是互质数为止，然一直除到所得的商是互质数为止，然后把所有的除数连乘起来即为最大公后把所有的除数连乘起来即为最大公约数约数.问题问题2 2:对于对于82518251与与61056105这两个数，由于这两个数，由于其公有的质因数较大，利用上述方法求其公有的质因数较大，利用上述方法求最大公约数就比较困难最大公约数就比较困难.注意到注意到8251=61058251=61051+21461+2146，那么，那么8

3、2518251与与61056105这两个数的公约数和这两个数的公约数和61056105与与21462146的公约的公约数有什么关系？数有什么关系？问题问题3 3:又又6105=21466105=21462+18132+1813，同理，同理，61056105与与21462146的公约数和的公约数和21462146与与18131813的公的公约数相等约数相等.重复上述操作，你能得到重复上述操作，你能得到82518251与与61056105这两个数的最大公约数吗？这两个数的最大公约数吗？21462146=181318131+1+333333，148148=37374+0.4+0.333333=148

4、1482+2+3737，18131813=3333335+5+148148，8251=8251=610561051+1+21462146，61056105=214621462+2+18131813，辗转相除法是一个反复执行直到余数等于辗转相除法是一个反复执行直到余数等于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

5、=0?是否问题问题5 5:上述求两个正整数的最大公约数上述求两个正整数的最大公约数的方法称为的方法称为辗转相除法辗转相除法或或欧几里得算法欧几里得算法.一般地，用辗转相除法求两个正整数一般地，用辗转相除法求两个正整数m m，n n的最大公约数，可以用什么逻辑结构来的最大公约数，可以用什么逻辑结构来构造算法？其算法步骤如何设计？构造算法？其算法步骤如何设计？第一步，给定两个正整数第一步，给定两个正整数m m，n(mn(mn).n).第二步，计算第二步，计算m m除以除以n n所得的余数所得的余数r.r.第三步，第三步，m=nm=n，n=r.n=r.第四步，若第四步，若r=0r=0，则，则m m，

6、n n的最大公约数等的最大公约数等 于于m m；否则，返回第二步；否则，返回第二步.问题问题5 5:该算法的程序框图如何表示？该算法的程序框图如何表示？开始开始输入输入m，n求求m除以除以n的余数的余数rm=nn=rr=0？是是输出输出m结束结束否否问题问题6 6:该程序框图对应的程序如何表述？该程序框图对应的程序如何表述？INPUT mINPUT m，n nDODOr=m MODnr=m MODnm=nm=nn=rn=rLOOP UNTILLOOP UNTIL r=0r=0PRINT mPRINT mENDEND开始开始输入输入m，n求求m除以除以n的余数的余数rm=nn=rr=0？是是输出

7、输出m结束结束否否问题问题7 7:如果用当型循环结构构造算法，如果用当型循环结构构造算法，则用辗转相除法求两个正整数则用辗转相除法求两个正整数m m，n n的最的最大公约数的程序框图和程序分别如何表大公约数的程序框图和程序分别如何表示？示？开始开始输入输入m，n求求m除以除以n的余数的余数rm=nn0？否否输出输出m结束结束是是n=rINPUT mINPUT m，n nWHILEWHILE n n0 0r=m MODnr=m MODnm=nm=nn=rn=rWENDWENDPRINT mPRINT mENDEND题组训练题组训练1 1：利用辗转相除法求两数：利用辗转相除法求两数40814081

8、与与2072320723的最大公约数的最大公约数.(53)(53)20723=40815+318;4081=31812+265;318=2651+53;265=535+0.（二）（二）:更相减损术更相减损术 问题问题1 1:设两个正整数设两个正整数m mn n，若，若m-n=km-n=k，则，则m m与与n n的最大公约数和的最大公约数和n n与与k k的最大公约数的最大公约数相等相等.反复利用这个原理，可求得反复利用这个原理，可求得9898与与6363的最大公约数为多少？的最大公约数为多少？98-63=3598-63=35，14-7=7.14-7=7.21-7=1421-7=14，28-7=

9、2128-7=21，35-28=735-28=7，63-35=2863-35=28，问题问题2 2:上述求两个正整数的最大公约数上述求两个正整数的最大公约数的方法称为的方法称为更相减损术更相减损术.一般地，用更相一般地，用更相减损术求两个正整数减损术求两个正整数m m，n n的最大公约数，的最大公约数，可以用什么逻辑结构来构造算法？其算可以用什么逻辑结构来构造算法？其算法步骤如何设计？法步骤如何设计？第一步，给定两个正整数第一步，给定两个正整数m m，n(mn).n(mn).第二步，计算第二步，计算m-nm-n所得的差所得的差k.k.第三步，比较第三步，比较n n与与k k的大小，其中大者用的

10、大小，其中大者用m m表表 示，小者用示，小者用n n表示表示.第四步，若第四步，若m=nm=n，则，则m m，n n的最大公约数等于的最大公约数等于 m m；否则，返回第二步；否则，返回第二步.问题问题3 3:该算法的程序框图如何表示？该算法的程序框图如何表示？开始开始输入输入m，nnk？m=n是是输出输出m结束结束mn？k=m-n是是否否n=km=k否否思考思考4:4:该程序框图对应的程序如何表述？该程序框图对应的程序如何表述？INPUT mINPUT m，n nWHILE WHILE m mn nk=mk=m-n-nIF nIF nk THENk THENm=nm=nn=kn=kELSE

11、ELSEm=km=kEND IFEND IFWENDWENDPRINT mPRINT mENDEND开始开始输入输入m，nnk？m=n是是输出输出m结束结束mn？k=m-n是是否否n=km=k否否“更相减损术更相减损术”在中国古代数学专著在中国古代数学专著九章算术九章算术中记述为：中记述为：可半者半之，不可半者，副置分母、子可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也，之数，以少减多，更相减损，求其等也，以等数约之以等数约之.INPUT “m,n=“;m,nIF mn THEN a=m m=n n=aEND IFK=0WHILE m MOD 2=0 AND n MOD

12、2=0 m=m/2 n=n/2 k=k+1WEND d=m-nWhile dn IF dn then m=d ELSE m=n n=d End if d=m-nWend d=2k*dPRINT dEnd 理论迁移理论迁移 例例1 1 分别用辗转相除法和更相减损分别用辗转相除法和更相减损术求术求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

13、，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=65130=652 2，所以所以325325与与130130的最大公约数是的最大公约数是65.65.因为因为270=65270=654+104+10，65=1065=106+56

14、+5，10=510=52 2，所以所以6565与与270270最大公约数是最大公约数是5.5.故故325325，130130，270270三个数的最大公约三个数的最大公约数是数是5.5.1.1.辗转相除法，就是对于给定的两个正整辗转相除法，就是对于给定的两个正整数，用较大的数除以较小的数，若余数不为数，用较大的数除以较小的数，若余数不为零，则将余数和较小的数构成新的一对数，零，则将余数和较小的数构成新的一对数，继续上面的除法，直到大数被小数除尽为止，继续上面的除法，直到大数被小数除尽为止，这时的较小的数即为原来两个数的最大公约这时的较小的数即为原来两个数的最大公约数数.小结作业小结作业 2.2

15、.更相减损术，就是对于给定的两个正更相减损术，就是对于给定的两个正整数，用较大的数减去较小的数，然后将差整数，用较大的数减去较小的数，然后将差和较小的数构成新的一对数，继续上面的减和较小的数构成新的一对数，继续上面的减法，直到差和较小的数相等，此时相等的两法，直到差和较小的数相等，此时相等的两数即为原来两个数的最大公约数数即为原来两个数的最大公约数.比较辗转相除法与更相减损术的区别比较辗转相除法与更相减损术的区别（1 1）都是求最大公约数的方法，计算上辗转相除）都是求最大公约数的方法，计算上辗转相除法以除法为主，更相减损术以减法为主，计算次数法以除法为主，更相减损术以减法为主，计算次数上辗转相除法计算次数相对较少，特别当两个数字上辗转相除法计算次数相对较少，特别当两个数字大小区别较大时计算次数的区别较明显。大小区别较大时计算次数的区别较明显。（2 2）从结果体现形式来看，辗转相除法体现结果）从结果体现形式来看，辗转相除法体现结果是以相除余数为是以相除余数为0 0则得到，而更相减损术则以减数与则得到，而更相减损术则以减数与差相等而得到差相等而得到小结小结作业：作业：P45P45练习：练习：1.1.P48P48习题习题1.3A1.3A组：组：1.1.