资源预览内容
第1页 / 共16页
第2页 / 共16页
第3页 / 共16页
第4页 / 共16页
第5页 / 共16页
第6页 / 共16页
第7页 / 共16页
第8页 / 共16页
第9页 / 共16页
第10页 / 共16页
亲,该文档总共16页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
一位美国的幼儿园老师为了教育孩子火海逃生,引导学生做了一个非 非常有趣的游戏“火海逃生”。老师将许多乒乓球放进瓶子,只露出 系着的棉线。花瓶代表大楼,细细的瓶颈是惟一的出口,七只乒乓球则 是楼里的居民,要求当大楼突然起火时,全体居民能在短时间里安全逃 离。七名学生兴奋地上场了,他们各执一根棉线,报警器一响,都以最 快的反应拉扯绳子,可一个“人”也没能脱离火海,原来,七只乒乓球都 卡在了瓶口。又开始了第二次实验?,火海逃生,这几个学生面面相觑,只见其中一个小声跟同伴们商量了几句,这 回大家没有各顾各地拉绳子,而是由左到右依次地拉。果然,报警 器的尾音还没结束,七位“居民”已离开了出口,转移到了安全地带。,运筹帷幄,决胜千里,算法案例之求最大公约数,求以下几组正整数的最大公约数。 (注:若整数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 ),想一想,如何求8251与6105的最大公约数?,例、求18与24的最大公约数:,6;,8;,63;,8;,7;,短除法,穷举法(也叫枚举法) 步骤: 从两个数中较小数开始 由大到小列举,直到找到公 约数立即中断列举,得到的 公约数便是最大公约数 。,穷举法,定理: 已知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),解:,练习:用辗转相除法求下列两数的最大公约数: (1)(225,135) (2)(98,196) (3)(72,168) (4)(153,119),45,98,24,17,8251和6105的最大公约数,解: 8251=61051+2146 6105=2146 2+1813 2146=1813 1+333 1813=333 5+148 333=148 2+37 148=37 4,(8251,6105) =(6105,2146) =(2146,1813) =(1813,333) =(333,148) =(148,37) =37,关系式m=np+r中m,n,r得取值变化情况,8251,6105,2146,6105,2146,2146,1813,1813,333,1813,333,148,148,333,37,148,37,0,辗转相除法求两个数的最大公约数,其算法可以描述如下:,辗转相除法是一个反复执行直到余数等于0停止的步骤, 这实际上是一个循环结构,思考:辗转相除直到何时结束?主要运用的是哪种算法结构?,如此循环,直到得到结果。, 输入两个正整数m和n;, 求余数r:计算m除以n,将所得余数存放到变量r中;,更新被除数和余数:m=n,n=r。,判断余数r是否为0:若余数为0则输出结果,否则转 向第步继续循环执行。,程序: INPUT “m,n=”;m,n DO r=m MOD n m=n n=r LOOP UNTIL r=0 PRINT m END,更相减损术,同理:a,b,c为正整数,若a-b=c,则(a,b)=(b,c)。,“更相减损术”(也是求两个正整数的最大公约数的算法) 步骤:,第一步:任意给定两个正整数;判断他们是否都是偶数。 若是,则用2约简;若不是则执行第二步。,第二步:以较大的数减较小的数,接着把所得的差与较 小的数比较,并以大数减小数。继续这个操作,直到所 得的减数和差相等为止,则这个等数就是所求的最大公 约数。,例、用更相减损术求98与63的最大公约数 (自己按照步骤求解),解:由于63不是偶数,把98和63以大数减小数,并辗转相减。,= 7,所以,98和63的最大公约数等于7。,(98,63) =(63,35),98-63=35,63-35=28,=(35,28),35-28=7,=(28,7),28-7=21,=(21,7),21-7=14,=(14,7),14-7=7,=(7,7),练习:用更相减损术求下列两数的最大公约数: (1)(225,135) (2)(98,196) (3)(72,168) (4)(153,119),45,98,24,17,例 用更相减损术求98与63的最大公约数,解:由于63不是偶数,把98和63以大数减小数, 并辗转相减 98-63=35 63-35=28 35-28=7 28-7=21 21-7=14 14-7=7 所以,98和63的最大公约数等于7。,(98,63) =(63,35) =(35,28) =(28,7) =(21,7) =(14,7) =(7,7) =7,关系式a-b=c中a,b,c得取值变化情况,更相减损是一个反复执行直到减数等于差时停止的步骤, 这实际也是一个循环结构,思考:更相减损直到何时结束?运用的是哪种算法结构?,程序: INPUT “a,b”;a,b i=0 WHILE a MOD 2=0 AND b MOD 2=0 a=a/2 b=b/2 i=i+1 WEND DO IF ba THEN t=a a=b b=t END IF a=a-b LOOP UNTIL a=b PRINT a*2i END,辗转相除法与更相减损术的区别:,小 结,(1)都是求最大公约数的方法,计算上辗转相除法以除法 为主,更相减损术以减法为主,计算次数上辗转相除法计算 次数相对较少,特别当两个数字大小区别较大时计算次数的 区别较明显。,(2)从结果体现形式来看,辗转相除法体现结果是以相除 余数为0而得到,而更相减损术则以减数与差相等而得到的。,作业: P38 习题:1.3 第一题,
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号