辗转相除法与更相减损术.ppt

1 算 法 案 例23 学习目标学习目标 1.通过辗转相除法与更相减损术的学习通过辗转相除法与更相减损术的学习,进一步体会算法思进一步体会算法思想想 2.通过古代著名的算法通过古代著名的算法,理解掌握辗转相除法与更相减损术理解掌握辗转相除法与更相减损术算法的含义算法的含义;了解其计算过程了解其计算过程;了解其算法程序框图和程序了解其算法程序框图和程序41.1.回顾算法的三种表述：回顾算法的三种表述：自然语言自然语言程序框图程序框图程序语言程序语言（三种逻辑结构）（三种逻辑结构）（五种基本语句）（五种基本语句）2.2.思考：思考：小学学过的求两个数最大公约数的方法？小学学过的求两个数最大公约数的方法？先用两个公有的质因数连续去除，一直除到所得的商是互为先用两个公有的质因数连续去除，一直除到所得的商是互为质数为止，然后把所有的除数连乘起来质数为止，然后把所有的除数连乘起来.复复 习习52525（1 1）5 55 535357 7所以，所以，2525和和3535的的最大公约数为最大公约数为5 54949（2 2）7 77 763639 9所以，所以，4949和和6363的的最大公约数为最大公约数为7 72 2、除了用这种方法外还有没有其它方法？、除了用这种方法外还有没有其它方法？算出算出82518251和和61056105的最大公约数的最大公约数.1 1、求两个正整数的最大公约数、求两个正整数的最大公约数（1 1）求）求2525和和3535的最大公约数的最大公约数 （2 2）求）求4949和和6363的最大公约数的最大公约数61 1、辗转相除法（欧几里得算法）、辗转相除法（欧几里得算法）所谓辗转相除法所谓辗转相除法,就是对于给定的两个数就是对于给定的两个数,用较大的数除以较用较大的数除以较小的数小的数.若余数不为零若余数不为零,则将余数和较小的数构成新的一对数则将余数和较小的数构成新的一对数,继续继续上面的除法上面的除法,直到大数被小数除尽直到大数被小数除尽,则这时较小的数就是原来两个则这时较小的数就是原来两个数的最大公约数数的最大公约数.例例1.用辗转相除法求用辗转相除法求98与与63的最大公约数的最大公约数.98=1633563=1 352835=1 28728=4 70所以，所以，98与与63的最大公约数为的最大公约数为7 7新新 课课7辗转相除法的原理：辗转相除法的原理：如果如果q q和和r r是是m m除以除以n n的商及余数的商及余数,即即 m m=n nq+q+r r,则则gcd(m,ngcd(m,n)=)=gcd(n,rgcd(n,r).).证明证明:设设 a=a=gcd(m,n),bgcd(m,n),b=gcd(n,rgcd(n,r)则有则有a|a|m m 及及a|a|n n,因此因此a|(m-nqa|(m-nq),),即即 a|ra|r及及a|na|n,所以所以a|ba|b又又 b|b|r r及及b|b|n n,所以所以b|(nq+rb|(nq+r),),即即b|mb|m及及b|nb|n,所以所以b|ab|a因为因为a|ba|b并且并且b|ab|a,所以所以a=ba=b,即即gcd(m,ngcd(m,n)=)=gcd(n,rgcd(n,r).).如计算如计算 gcd(546,429)gcd(546,429)546=1 546=1429+117,429+117,429=3 429=3117+78,117+78,117=1 117=178+39,78+39,78=2 78=23939882518251=610561051+1+21462146 61056105=214621462+2+18131813 21462146=181318131+1+33333318131813=3333335+5+148148333333=1481482+2+3737148148=37374 4所以所以3737是是82518251和和61056105的的最大公约数最大公约数 求求82518251和和61056105的最大公约数的最大公约数.P P4545)练习练习1(1)1(1)用辗转相除法用辗转相除法求求225225和和135135的最大公约数的最大公约数225225=1351351+1+9090135135=90901+1+45459090=45452 2所以所以4545是是225225和和135135的最大公约数的最大公约数 思考：从上面的两个例子可思考：从上面的两个例子可以看出计算的规律是什么？以看出计算的规律是什么？S1S1：用大数除以小数：用大数除以小数S2S2：除数变成被除数，余数变成除数：除数变成被除数，余数变成除数S3S3：重复：重复S1S1，直到余数为，直到余数为0 09 辗转相除法是一个反复执行直到余数等于辗转相除法是一个反复执行直到余数等于0 0停止的步骤停止的步骤,这实际上是一个这实际上是一个循环结构循环结构m=m=n nq qr r算法步骤算法步骤第一步：输入两个正整数第一步：输入两个正整数m,n(mm,n(mn).n).第二步：计算第二步：计算m m除以除以n n所得的余数所得的余数r.r.第三步：第三步：m=m=n,nn,n=r.=r.第四步：若第四步：若r r0,0,则则m,nm,n的最大公约数等于的最大公约数等于m;m;否则转到第二步否则转到第二步.第五步：输出最大公约数第五步：输出最大公约数m.m.10程序框图程序框图程程 序序r=m MOD nr=m MOD nm=nm=n是是否否n=rn=r开始开始输入输入m,nm,nr=0?r=0?输出输出m m结束结束直到型循环结构直到型循环结构INPUT“m,n=“;m,nDOLOOP UNTIL r=m MOD nm=nn=rr=0PRINT mEND11程序框图程序框图程程 序序当型循环结构当型循环结构INPUT“m,n=“;m,nWHILE WEND r=m MOD nm=nn=rr0PRINT mENDr=1求求m m除以除以n n的余数的余数r rm=nm=n是是否否n=rn=r开始开始输入输入m,nm,nr0?r0?输出输出m m结束结束r=1r=1122 2、更相减损术、更相减损术 算理算理：所谓更相减损术所谓更相减损术,就是对于给定的两个数就是对于给定的两个数,用较大用较大的数减去较小的数的数减去较小的数,然后将差和较小的数构成新的一对数然后将差和较小的数构成新的一对数,再再用较大的数减去较小的数用较大的数减去较小的数,反复执行此步骤直到差数和较小反复执行此步骤直到差数和较小的数相等的数相等,此时相等的两数便为原来两个数的最大公约数此时相等的两数便为原来两个数的最大公约数.第一步：任意给定两个正整数第一步：任意给定两个正整数;判断他们是否都是偶数判断他们是否都是偶数.若是若是,则用则用2 2约简约简;若不是则执行第二步若不是则执行第二步.第二步：以较大的数减较小的数第二步：以较大的数减较小的数,接着把所得的差与较小的数接着把所得的差与较小的数比较比较,并以大数减小数并以大数减小数.继续这个操作继续这个操作,直到所得的减数和差相直到所得的减数和差相等为止等为止,则这个等数就是所求的最大公约数则这个等数就是所求的最大公约数.算理：可半者半之算理：可半者半之,不可半者不可半者,副置分母、子之数副置分母、子之数,以少减以少减多多,更相减损更相减损,求其等也求其等也,以等数约之以等数约之.13例例3 3 用更相减损术求用更相减损术求9898与与6363的最大公约数的最大公约数解：由于解：由于6363不是偶数，把不是偶数，把9898和和6363以大数减小数，并辗转相减以大数减小数，并辗转相减 989863633535636335352828353528287 728287 7212121217 7212114147 77 7所以，所以，9898和和6363的最大公约数等于的最大公约数等于7 7 98=6313563=3512835=2817 辗转相除法与更相减损术的区别辗转相除法与更相减损术的区别(1)(1)都是求最大公约数的方法都是求最大公约数的方法,计算上辗转相除法以除法为主计算上辗转相除法以除法为主,更更相减损术以减法为主相减损术以减法为主,计算次数上辗转相除法计算次数相对较少计算次数上辗转相除法计算次数相对较少,特别当两个数字大小区别较大时计算次数的区别较明显特别当两个数字大小区别较大时计算次数的区别较明显.(2)(2)从结果体现形式来看从结果体现形式来看,辗转相除法体现结果是以相除余数为辗转相除法体现结果是以相除余数为0 0则得到则得到,而更相减损术则以减数与差相等而得到而更相减损术则以减数与差相等而得到14用更相减损术求两个整用更相减损术求两个整数数m，n的最大公约数的最大公约数INPUT“m,n=”;m,nWHILE mn IF mn THEN m=m-n ELSE n=n-m END IFWENDPRINT nEND程程 序序程序框图程序框图输入输入m,n开始开始mn？mn？m=m-nn=n-m输出输出n结束结束NYYN算法步骤算法步骤(1)输入两个整数输入两个整数m，n(2)若若mn,转到转到(3),否则转到否则转到(4)(3)若若mn,则则m=m-n,否则否则n=n-m,转到转到(2)(4)输出最大公约数输出最大公约数n