《2017-2018学年高中数学第1章算法初步1.4算法案例课件苏教版必修3》由会员分享，可在线阅读，更多相关《2017-2018学年高中数学第1章算法初步1.4算法案例课件苏教版必修3（27页珍藏版）》请在金锄头文库上搜索。
1、A1.4_算泉柳侧FR匹预5习窦HP英限一一春朱门月郎尽眼“引b新8莲膑一一皂斧朱关关坚区,入门答葛闰题1:如何求12与20的最大公约数?提示:短除法、一般情况下数字不应过大.问题2:若求6750与3492的最大公约数,上述方法还奏效吗?提示:数值很大时短除法不方便用.闰题3:对于问题1中12与20的最大公约数是4.若用20除以12余8,再用8去除12余4,再用4去除8余数为0,也可求得最大公约数为4.若对较大两数可否用此法求公约教:提示:可以.新知自解1.孙子问题(D问题名称:人们将“韩信点兵一一孙子问题“这种问题的通用解法称为“孙孔剩余定理“或“中国剩余定理“.(2)问题怡想:“孙子问题“
2、相当于求关于x,y,z的不人二3x十2定方程组1z一s)-+3的正整数解.z一7z十22-.欧几里得辑转相除法(D含义:公元前3世纪,欧几里得在原本第七篇中介绍了求两个正整数,5(a切的最大公约数的方法,这种方法称为“欧几里得辗转相除法“.(2)步骤:计算出a:5的余数r,若r一0,则5即为a,2的最大公约数:若7丿0,则把前面的除数?作为新的被除数,把余数7作沥新的除数,经绥运算,直到伟叙义0,此时的除数即为,0的最大公约数.3.两个常用函数(UMod(ae,分表示a除以5所得的余数.(C)Int(J表示不超过x的最大整数.归纳.升华.领愚1.由除法和减法的性质可知,对于任意两个正整数,辗转
3、相除法或更相减损术总可以在有限步之后完成,故总能用这两种方法求出任意两个正整数的最大公约数.2.辗转相除法的理论依据是:由a二n5+r3r一a一5得a5与5、7有相同的公约数.玟一丞肌群旁技沥芒颗加交有吴粟圭学朱所城鏖.矗5孙子制余定理的应用例1有3个连续的正整数,其中最小的能被15整除,中间的能被17整除,最大的皎被19整除,画当求滔足要求的一组三个连续正整数的流程图,并写出伪代码.思路点拨设这三个数分别为,办+l,办十2,则满足的条件是Mod15)一0且Mod(mz-+l17)一0且Mod(z十2,19)一0.四玟I牌殖忐精解详析流程图:伪代码:77-2WhileMod(oy15)一0orMIod(十117)天0“orMIod(十2,19)大0一十1EndWhikPrint74,办十1,加十2一点通解决此类问题的方法就是从一2开始,对每一个正整数逐一检验,当m满足所有已知条件时,结标循环,输出.题组集刍.1.如图所示的流程图,输出的结果是“解析:尘一10时,不满足条件,则m-10十7.办一17肖,Mod(3)一2相Mod(5)一2成立,故输出17.答秋:17
