1、算法案例-辗转相除法名师课件2 韩信是秦末汉初的著名军事家韩信是秦末汉初的著名军事家.据说有一次汉高祖刘邦在据说有一次汉高祖刘邦在卫士的簇拥下来到练兵场卫士的簇拥下来到练兵场,刘邦问韩信有什么方法刘邦问韩信有什么方法,不要逐个不要逐个报数报数,就能知道场上的士兵的人数就能知道场上的士兵的人数,韩信先令士兵排成韩信先令士兵排成3列纵队列纵队,结果有结果有2人多余人多余,接着下令排成接着下令排成5列纵队列纵队,结果又多出结果又多出3人人,随后他随后他又下令改为又下令改为7列纵队列纵队,这次又剩下这次又剩下2人无法成整行人无法成整行.在场的人都在场的人都哈哈大笑哈哈大笑,以为韩信不能清点出准确的人数
2、以为韩信不能清点出准确的人数,不料笑声刚落不料笑声刚落,韩韩信高声报告共有士兵信高声报告共有士兵2333人人.众人听了一楞众人听了一楞,不知道韩信用什么不知道韩信用什么方法这么快就能得到正确的结果的方法这么快就能得到正确的结果的.今天今天,我们将以这些古典案例的思想我们将以这些古典案例的思想,设计出适宜计算机的设计出适宜计算机的运行程序运行程序,提高我们对基本算法结构和算法语句在实际中的运提高我们对基本算法结构和算法语句在实际中的运用能力用能力.复习引入问题1:在小学中我们是如何求出两个正整数的最大公约数的呢?例例1 1：求：求2424与与3030的最大公约数。的最大公约数。解：解：2 3 0
3、 2 4 用公有质因数用公有质因数2除，除，3 15 1 2 用公有质因数用公有质因数3除，除，5 4 5和和4互质不除了。互质不除了。得：得：18和和24最大公约数是：最大公约数是：236 问题2:如果公约数比较大而且根据我们的观察又不能得到一些公约数，我们又应该怎样求它们的最大公约数？比如求8251与6105的最大公约数?新课讲解定义：所谓辗转相除法，就是对于给定的两个数，用较大的数除以较小的数。若余数不为零，则将余数和较小的数构成新的一对数，继续上面的除法，直到大数被小数除尽，则这时较小的数就是原来两个数的最大公约数。用于求两个正整数的最大公约数理论基础：理论基础：已知已知m,n,rm,
4、n,r为正整数，若为正整数，若m=nq+rm=nq+r（0rn0rn).第二步：计算第二步：计算m除以除以n所得的余数所得的余数r.第三步：第三步：m=n,n=r.第四步：若第四步：若r0,则则m,n的最大公约数等于的最大公约数等于m；否则转到第二步否则转到第二步.第五步：输出最大公约数第五步：输出最大公约数m.程序框图程序框图如右图示：如右图示：程序程序如下：如下：INPUT “m,n=“;m,nDO r=m MOD n m=n n=rLOOP UNTIL r=0PRINT mEND开始开始输入输入m,n r=m MOD n m=nr=0?是是否否 n=r 输出输出m结束结束新课讲解开始开始
5、输入输入m，n求求m除以除以n的余数的余数rm=nn0？否否输出输出m结束结束是是n=rINPUT mINPUT m，n nWHILE nWHILE n0 0r=m MOD nr=m MOD nm=nm=nn=rn=rWENDWENDPRINT mPRINT mENDEND用当型循环结构构造算法用当型循环结构构造算法:新课讲解九章算术九章算术更相减损术更相减损术 算理：算理：可半者半之，不可半者，副置分母、子可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也，以等之数，以少减多，更相减损，求其等也，以等数约之。数约之。原理原理：第一步：第一步：任意给定两个正整数；判断他们是否
6、都是任意给定两个正整数；判断他们是否都是偶数。若是，则用偶数。若是，则用2约简；若不是则执行第二步。约简；若不是则执行第二步。第二步：第二步：以较大的数减较小的数，接着把所得的差以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止，则这个等数就是所直到所得的减数和差相等为止，则这个等数就是所求的最大公约数。求的最大公约数。新课讲解例例如用更相减损术求如用更相减损术求9898与与6363的最大公约数的最大公约数解：由于解：由于6363不是偶数，把不是偶数，把9898和和6363以大数减小数，以大
7、数减小数，并辗转相减并辗转相减 989863633535636335352828353528287 728287 7212121217 7212114147 77 7所以，所以，9898和和6363的最大公约数等于的最大公约数等于7 7 新课讲解（1 1）都是求最大公约数的方法，计算上辗转相除）都是求最大公约数的方法，计算上辗转相除法以除法为主，更相减损术以减法为主，计算次数法以除法为主，更相减损术以减法为主，计算次数上辗转相除法计算次数相对较少，特别当两个数字上辗转相除法计算次数相对较少，特别当两个数字大小区别较大时计算次数的区别较明显。大小区别较大时计算次数的区别较明显。新课讲解辗转相除法
8、与更相减损术的区别（2 2）从结果体现形式来看，辗转相除法体现结果）从结果体现形式来看，辗转相除法体现结果是以相除余数为是以相除余数为0 0则得到，而更相减损术则以减数则得到，而更相减损术则以减数与差相等而得到与差相等而得到例1、用辗转相除法求225和135的最大公约数225=1351+90135=901+4590=452思考：思考：从上面的例子中可以看出计算的规律是什么？从上面的例子中可以看出计算的规律是什么？用大数除以小数用大数除以小数 除数变成被除数，余数变成除数除数变成被除数，余数变成除数重复第一步，直到余数为重复第一步，直到余数为0 0例题讲解例2、用辗转相除法求324、243、13
9、5的最大公约数.思路分析：思路分析：求三个数的最大公约数可以先求出两求三个数的最大公约数可以先求出两个数的最大公约数，第三个数与前两个数的最大个数的最大公约数，第三个数与前两个数的最大公约数的最大公约数即为所求。公约数的最大公约数即为所求。.27135243324.2713581,022754,2715481,54181135.812433240381243811243324的最大公约数为、所以，三个数的最大公约数为与则又的最大公约数为与则例题讲解例题讲解例例3、用辗转相除法求、用辗转相除法求612与与468的最大公约数，的最大公约数，并用更相减损术检验所得结果并用更相减损术检验所得结果用更相
10、减损术检验：用更相减损术检验：612和和468为偶数为偶数，两次用两次用2约简得约简得153和和117，15311736，1173681，813645，45369，36927，27918，1899，所以所以612和和468的最大公约数为的最大公约数为92236.用辗转相除法：用辗转相除法：6124681144，468144336，144364，即即612和和468的最大公约数是的最大公约数是36.解：解：方法归纳(1)利用辗转相除法求给定的两个数的最大公约数利用辗转相除法求给定的两个数的最大公约数，即利即利用带余除法用带余除法，用数对中较大的数除以较小的数用数对中较大的数除以较小的数，若余数若
11、余数不为零不为零，则将余数和较小的数构成新的数对则将余数和较小的数构成新的数对，再利用带再利用带余除法余除法，直到大数被小数除尽直到大数被小数除尽，则这时的较小数就是原则这时的较小数就是原来两个数的最大公约数来两个数的最大公约数(2)利用更相减损术求两个正整数的最大公约数的一般步利用更相减损术求两个正整数的最大公约数的一般步骤是：首先判断两个正整数是否都是偶数若是骤是：首先判断两个正整数是否都是偶数若是，用用2约简约简，也可以不除以也可以不除以2，直接求最大公约数直接求最大公约数，这样不影，这样不影响最后结果响最后结果求最大公约数常用的两种方法巩固练习1、(1)1 624与与899的最大公约数是的最大公约数是_(2)用辗转相除法求用辗转相除法求80和和36的最大公约数，并用更相减损术检的最大公约数，并用更相减损术检验所得结果验所得结果巩固练习1、(1)1 624与与899的最大公约数是的最大公约数是_(2)用辗转相除法求用辗转相除法求80和和36的最大公约数，并用更相减损术检的最大公约数，并用更相减损术检验所得结果验所得结果 辗转相除法 用辗转相除法求最大公约数课堂小结 作 业思考：思考：你能根据辗转相除法的算法步骤你能根据辗转相除法的算法步骤画出它的程序框图以及相应的程序语句画出它的程序框图以及相应的程序语句吗吗?P45 练习练习1 P48 习题习题1.3 A组组1
