高中数学 13算法案例课件(3) 新人教A版必修3 课件.ppt

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