资源描述
-辗转相除法和更相减损术思考思考1:在小学中我们是如何求出两个正整在小学中我们是如何求出两个正整数数m,n的最大公约数的最大公约数（m,n）的呢的呢?求以下几组正整数的最大公约数。（1）（18，30）（2）（24，16）（3）（63，63）（4）（72，8）解：2 1 8 2 4 用公有质因数2除，3 9 1 2 用公有质因数3除，3 4 3和4互质不除了。得：18和24最大公约数是：236 例1、求18与24的最大公约数：6；8；63；8；短除法短除法用（用（m,n）来表示）来表示m和和n的最大公约数。的最大公约数。探究一：辗转相除法思考思考2:当两个数的公约数较大时当两个数的公约数较大时,我们怎样去求我们怎样去求两个数的最大公约数呢两个数的最大公约数呢?想一想，如何求8251与6105的最大公约数？例1、求8251和6105的最大公约数。148=37 4=378251=61051+2146 （8251，6105）=（6105，2146）6105=2146 2+1813=（2146，1813）2146=1813 1+333=（1813，333）1813=333 5+148=（333，148）333=148 2+37=（148，37）解：定义定义:辗转相除法辗转相除法,就是对于给定的两个正整数就是对于给定的两个正整数,用较用较大的数除以较小的数大的数除以较小的数,若余数不为零若余数不为零,则将余数和除则将余数和除数成新的数对数成新的数对,继续上面的除法继续上面的除法,直到大数被小数除直到大数被小数除尽尽,则这时较小的数就是原来两个数的最大公约数则这时较小的数就是原来两个数的最大公约数.已 知 m,n 为正整数,r为整数，若m=nq+r（0rn）（即r=m MOD n）,则（m,n）=(n,r)。辗转相除法的理论基础辗转相除法的理论基础:练习：用辗转相除法求下列两数的最大公约数：思考思考3 3：辗转相除直到何时结束？主要运用的是哪种：辗转相除直到何时结束？主要运用的是哪种算法结构？算法结构？辗转相除法是一个反复执行直到余数等于0停止的步骤，这实际上是一个循环结构，并且循环结束条件是余数为0（301，133）辗转相除法求两个数的最大公约数，其算法可以描述如下：如此循环，直到得到结果。输入两个正整数m和n；求余数r：计算m除以n，将所得余数记为变量r；更新被除数和余数：m=n，n=r。判断余数r r是否为0：若余数为0则输出结果，否则转向第步继续循环执行。思考思考4 4：你能根据辗转相除法的算法步骤画出它的：你能根据辗转相除法的算法步骤画出它的程序框图以及相应的程序语句吗程序框图以及相应的程序语句吗?开始开始输入：输入：m,n输出：输出：m结束结束r=0?m=nNYr=mMODnn=r程序：程序：INPUT“m，n=”;m,nDO r=m MOD nm=nn=rLOOP UNTIL r=0PRINT mEND探究二,更相减损术“可半者半之可半者半之,不可半者不可半者,副置分母、副置分母、子之数，以少减多，更相减损，求其等也，以等子之数，以少减多，更相减损，求其等也，以等数约之数约之。”“更相减损术更相减损术”（也是求两个正整数的最大公约数的算法）（也是求两个正整数的最大公约数的算法）步骤：步骤：第一步：任意给定两个正整数；判断他们是否都是偶数。第一步：任意给定两个正整数；判断他们是否都是偶数。若是，则用若是，则用2约简；若不是则执行第二步。约简；若不是则执行第二步。第二步：以较大的数减较小的数，接着把所得的差与第二步：以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止，则这个等数与约简数的积就是所得的减数和差相等为止，则这个等数与约简数的积就是所求的最大公约数。求的最大公约数。例例2 2、用更相减损术求、用更相减损术求98与与63的最大公约数的最大公约数（自己按照步骤求解）（自己按照步骤求解）解：由于解：由于63不是偶数，把不是偶数，把98和和63以大数减小数，并更相相减以大数减小数，并更相相减。=7所以，所以，98和和63的最大公约数等于的最大公约数等于7。（98，63）=（63，35）98-63=3563-35=28=（35，28）35-28=7=（28，7）28-7=21=（21，7）21-7=14=（14，7）14-7=7=（7，7）理论基础：理论基础：m,n,rm,n,r为正整数，若为正整数，若m-n=rm-n=r，则（，则（m,nm,n）=(n,r)=(n,r)。练习：用更相减损术求下列两数的最大公约数：思考思考5 5：更相减损直到何时结束？运用的是哪种算法结构？：更相减损直到何时结束？运用的是哪种算法结构？更相减损是一个反复执行直到减数等于差时停止的步骤。这实际也是一个循环结构，循环结束条件是减数和差相等。（301，133）思考：辗转相除法与更相减损术有什么区别和联系？区别：区别：l l计算上辗转相除法以除法为主，更相减损计算上辗转相除法以除法为主，更相减损术以减法为主，辗转相除法比更相减损术术以减法为主，辗转相除法比更相减损术减小得更快；减小得更快；联系：联系：都是求最大公约数的方法。都是逐渐地把求两个数的最大公因数转化为求较小的两个数的最大公因数。都是一个不断的递归过程练习：1，下列说法中正确的是（）A 辗转相除法是中国古代数学中的算法B 更相减损术与辗转相除法的算理完全不同C 辗转相除法与更相减损术相比较，用辗转相除法求最大公约数更优越。D 辗转相除法与更相减损术，在设计程序时，都要用到循环结构。l l2，下面是求115与276的最大公约数的程序，把程序补充完整。a=115b=276DO r=_ a=b b=rLOOP UNTIL r=_PRINT aEND作业l l习题1l l思考：4.辗转相除法的程序框图及程序辗转相除法的程序框图及程序:INPUT m,nIF mn THEN x=n n=m m=xEND IFr=m MOD nWHILE r0 m=nn=rr=m MOD n WENDPRINT nEND否否开始开始 输入两个正数输入两个正数m,nmn?n=n-mYNINPUT m,nWHILE mn IF mn THEN m=m-n ELSE n=n-m END IFWENDPRINT mEND
展开阅读全文