单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,2019-7-19,谢谢观赏,*,一位美国的幼儿园老师为了教育孩子火海逃生，引导学生做了一个非,非常有趣的游戏“火海逃生”。老师将许多乒乓球放进瓶子，只露出,系着的棉线。花瓶代表大楼，细细的瓶颈是惟一的出口，七只乒乓球则,是楼里的居民，要求当大楼突然起火时，全体居民能在短时间里安全逃,离。七名学生兴奋地上场了，他们各执一根棉线，报警器一响，都以最,快的反应拉扯绳子，可一个“人”也没能脱离火海，原来，七只乒乓球都,卡在了瓶口。又开始了第二次实验？,火海逃生,这几个学生面面相觑，只见其中一个小声跟同伴们商量了几句，这,回大家没有各顾各地拉绳子，而是,由左到右依次,地拉。果然，报警,器的尾音还没结束，七位“居民”已离开了出口，转移到了安全地带。,运筹帷幄，决胜千里,1,谢谢观赏,2019-7-19,一位美国的幼儿园老师为了教育孩子火海逃生，引导学生做,算法案例,之求最大公约数,求以下几组正整数的最大公约数。,(注：若整数,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,最大公约数是：,2,3,6,想一想，如何求,8251,与,6105,的最大公约数？,例、求18与24的最大公约数：,6；,8；,63；,8；,7；,短除法,2,谢谢观赏,2019-7-19,算法案例之求最大公约数求以下几组正整数的最大公约数。解：2,开始,i=m+1,输入：,m,n,m MOD i=0,且,n MOD i=0?,i=i-1,输出：,i,结束,Y,N,mn?,t=m,m=n,n=t,N,Y,穷举法（也叫枚举法）,步骤：,从两个数中较小数开始,由大到小列举，直到找到公,约数立即中断列举，得到的,公约数便是最大公约数。,穷举法,3,谢谢观赏,2019-7-19,开始i=m+1输入：m,nm MOD i=0且n MOD,定理：已知,m,n,r,为正整数，若,m=nq+r,（0rn）（,即,r=m MOD n）,则,（,m,n）=(n,r),。,辗转相除法,分析：,m=nq+r ,r=m-nq,例1、求8251和6105的最大公约数。,148=37 4,=37,8251=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）,解：,4,谢谢观赏,2019-7-19,定理：已知m,n,r为正整数，若m=nq+r（0ra THEN,t=a,a=b,b=t,END IF,a=a-b,LOOP UNTIL a=b,PRINT a*2i,END,开始,输入：,a,b,输出：,a2,i,结束,a=b?,a=a/2,b=b/2,Y,a=a-b,t=a,a=b,b=t,ba?,a MOD 2=0,且,b MOD 2=0?,Y,N,N,N,Y,i=0,i=i+1,14,谢谢观赏,2019-7-19,程序：开始输入：a,b输出：a2i结束a=b?a=a/2,辗转相除法与更相减损术的区别：,小 结,（,1,）都是求最大公约数的方法，计算上辗转相除法以除法,为主，更相减损术以减法为主，计算次数上辗转相除法计算,次数相对较少，特别当两个数字大小区别较大时计算次数的,区别较明显。,（,2,）从结果体现形式来看，辗转相除法体现结果是以相除,余数为,0,而得到，而更相减损术则以减数与差相等而得到的。,15,谢谢观赏,2019-7-19,辗转相除法与更相减损术的区别：小 结（1）都是求最大公约数,作业：,P38,习题：1.3 第一题,16,谢谢观赏,2019-7-19,作业：16谢谢观赏2019-7-19,再见,17,谢谢观赏,2019-7-19,再见17谢谢观赏2019-7-19,