《1.4算法案例》课件1.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,数学,必修,3,(,苏教版,),第,1,章算法初步,1,4,算法案例,情景切入,韩信是秦末汉初的著名军事家据说有一次汉高祖刘邦在卫士的簇拥下来到练兵场，刘邦问韩信有什么方法，不要逐个报数，就能知道场上的士兵的人数,韩信先令士兵排成,3,列纵队，结果有,2,人多余；接着立即下令将队形成为,5,列纵队，这一改，又多出,3,人；随后他又下令改为,7,列纵队，这次又剩下,2,人无法成整行,在场的人都哈哈大笑，以为韩信不能清点出准确的人数，不料笑声刚落，韩信高声报告共有士兵,2 333,人众人听了一愣，不知道韩信用什么方法这么快就能得出正确的结果的同学们，你知道吗？,1,理解辗转相除法与更相减损术求最大公约数的方法,2,理解中国剩余定理在数学中的应用,3,理解二分法求方程的近似解的算法,1,孙子剩余定理即,_,，在近代数学和电子计算机程序设计中有着广泛的应用,2,公元前,3,世纪，欧几里得在,原本,中介绍的求两个正整数的最大公约数的方法，称为,_,3,63,与,231,的最大公约数是,_,中国剩余定理,欧几里得辗转相除法,21,一、中国剩余定理,中国剩余定理，也称为孙子剩余定理该定理在近代数学和电子计算机程序设计中有着广泛的应用,(,1,),剩余问题,在整数除法里，一个数分别除以几个数，得到整数商后，均有剩余；已知各除数及其对应的余数，从而要求出适合条件的这个被除数的问题，叫做剩余问题,(,2,),两个性质,性质,1,：几个数相加，如果只有一个加数不能被数,a,整除，而其他加数均能被数,a,整除，那么它们的和就不能被数,a,整除,如：,10,能被,5,整除，,15,能被,5,整除，但,7,不能被,5,整除，所以,(,10,15,7,),不能被,5,整除,性质,2,：二数不能整除，若被除数扩大,(,或缩小,),了几倍，而除数不变，则其余数也同时扩大,(,或缩小,),相同的倍数,(,余数必小于除数,),如：,227,3,1,(,224,),7,12,14,(,4,),要余,2,，则,2227,6,2,；,(,229,),7,28,19,7,(,2,),(,要余,5,，则,2257,15,5,),(,3,),中国剩余定理,中国数学史书上记载：在两千多年前的我国古代算书,孙子算经,中，有这样一个问题,(,称为,“,物不知数,”,问题,),及其解法：,今有物不知其数，三三数之剩二；五五数之剩三；七七数之剩二问物几何？,答曰：二十三,术曰：,“,三三数之剩二，置一百四十；五五数之剩三，置六十三；七七数之剩二，置三十并之，得二百三十三，以二百一十减之即得,”,“,术,”,即解法书中还介绍了上述问题中余数为一的一般解法：凡三三数之剩一，则置七十；五五数之剩一，则置二十一；七七数之剩一，则置十五；一百六以上，以一百五减之即得,在明朝程大位著,算术统宗,一书中，把上述问题的基本解法，用诗句概括为：,三人同行七十稀，五树梅花廿一枝，七子团圆正半月，除百减五便得知,依定理译成算式为：,702,213,152,233,，,233,1052,23,.,这就是享誉中外的,“,中国剩余定理,”,(,4,),“,物不知数,”,问题的算法分析与算法的流程图与伪代码表示，请直接参见教材相关部分,1,辗转相除法,公元前,3,世纪欧几里得在,原本,中提出的：,“,设有不相等的二数，从大数中连续减去小数直到余数小于小数，再从小数中连续减去余数直到小于余数，这样一直下去，若余数总是量不尽其前一个数，直到最后的余数为一个单位，则该二数互质,”,二、求两个正整数的最大公约数的算法,辗转相除法就是把给定的两个数，用较大的数除以较小的数，若余数不为零，则将余数和较小的数，继续上面的除法，直到余数为零，此时的除数就是所求的最大公约数,从算法思想我们可以看出，辗转相除法的基本步骤是用较大的数,(,用,a,表示,),除以较小的数,(,用,b,表示,),，得到：,a,nb,r,(,0,r,b,),由于这是一个反复执行的步骤，且执行的次数由余数,r,是否等于,0,决定，所以我们可以把它看作一个循环体，用循环结构就可以实现其算法,2,更相减损术,用更相减损术求两个正整数的最大公约数的过程与算法设计：对于给定的两个正整数，用较大的数减去较小的数，接着将得到的差与较小的数比较，用这两个数中的较大的数减去较小的数，继续上述的操作,(,大数减小数,),，直到产生一对相等的数为止，那么这个数,(,等数,),就是所求的最大公约数这是因为每次操作后所得的两数与前两数具有相同的最大公约数，而两数的值逐渐减小，经过有限步操作后一定可得相等的两数,要,点导,航,3,“,更相减损术,”,与,“,辗转相除法,”,的异同点,“,更相减损术,”,与,“,辗转相除法,”,这两种算法分别来源于东西方古代数学名著，但二者的算理确是相似的，有异曲同工之妙主要区别在于辗转相除法进行的是除法运算，即辗转相除；而更相减损术进行的是减法运算，即辗转相减，但实质都是一个不断的递归过程,辗转相除法的理论依据是：由,a,nb,r,(,a,b,),r,a,nb,得,a,，,b,与,b,，,r,有相同的公约数；更相减损术的理论依据是：由,a,b,r,(,a,b,),a,b,r,得,a,，,b,与,b,，,r,要,点导,航,有相同的公约数所以，它们有相同的理论依据，只不过一个用除法，另一个用减法罢了,三、二分法,分析：,例,1,我国,算经十书,之一,孙子算经,中有这样一个问题：,“,今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二问物几何？,”,你能用程序解决这个问题吗？,这个问题的通用解法称为,“,孙子剩余定理,”,或,“,中国剩余定理,”,著名的,“,韩信点兵问题,”,即为此例的应用,因此，可以让,m,从,2,开始检验，若三个条件中有任何一个不成立，则,m,递增,1,，一直到,m,同时满足三个条件为止,解析：,流程图如下图所示：,伪代码如下：,m,2,While,mod,(,m,，,3,),2,or,mod,(,m,，,5,),3,or,mod,(,m,，,7,),2,m,m,1,End,While,Print,m,典,例剖,析,变式训练,1,有一堆桃子不知数目，猴子第一天吃掉一半，觉得不过瘾，又多吃了一个，第二天照此办法，吃掉剩下桃子的一半另加一个，天天如此，到第十天早上剩下一个桃子，问这堆桃子有多少个？,第十天桃子数：,S,10,1,(,个,),；,第九天桃子数：,S,9,(,1,1,),2,4,(,个,),；,第八天桃子数：,S,8,(,1,4,),2,10,(,个,),；,第一天桃子数：,S,1,(,S,2,1,),2,(,个,),所以递推关系是,S,10,1,，,S,n,(,S,n,1,1,),2,，,n,1,，,2,，,，,9,.,故可用循环结构设计算法,解析：,流程图如右上图所示,答案：,典,例剖,析,例,2,写出求两个正整数,a,，,b,(,a,b,),的最大公约数的一个算法，并画出流程图，写出相应的伪代码,利用辗转相除法，求出数列,a,，,b,，,r,1,，,r,2,，,，,r,n,，,0,，这列数从第三项开始每项都是前两项相除,(,小的除大的,),所得的余数，余数,0,的前一个,r,n,即为,a,和,b,的最大公约数,分析：,典,例剖,析,算法如下：,S,1,输入两个正整数,a,，,b,(,a,b,),；,S,2,r,a,b,的余数；,S,3,a,b,，,b,r,；,S,4,如果,r,0,，转,S,2,；,S,5,输出最大公约数,b,.,解析：,伪代码如下：,Read,a,，,b,While,mod,(,a,，,b,),0,r,mod,(,a,，,b,),a,b,b,r,End,While,Print,b,流程图如下图所示：,典,例剖,析,规律总结：,辗转相除法是解决求最大公约数的通法，也是解决求两个正整数最小公倍数的通法，可以输入不同的,a,、,b,值，先求两数的最大公约数,变式训练,2,下述伪代码输出的结果是,_,a,375,b,85,While,Mod,(,a,，,b,),0,r,Mod,(,a,，,b,),a,b,b,r,End,While,Print,b,伪代码是求,375,和,85,的最大公约数,375,854,35,，,85,352,15,，,35,152,5,，,15,53,0,，,375,与,85,的最大公约数是,5,.,解析：,5,答案：,典,例剖,析,例,3,现有长度为,360,cm,和,780,cm,两种规格的钢筋若干，要焊接一批正方体模型，问怎样才能保证正方体体积最大且不浪费？编写算法流程图，并写出相应的伪代码,正方体的所有棱长都相等，故必须将钢筋剪裁成长度相等的钢筋条，又必须不浪费，这就说明必须剪后无剩余，于是为了保证正方体的体积最大，剪的钢筋的最大长度为,360,cm,和,780,cm,的最大公约数，可用更相减损术求最大公约数,分析：,典,例剖,析,根据更相减损术求,780,和,360,的最大公约数的步骤如下：,780,360,420,，,420,360,60,，,360,60,300,，,300,60,240,，,240,60,180,，,180,60,120,，,120,60,60,，,60,60,0,.,解析：,典,例剖,析,则60,即为,360,和,780,的最大公约数,流程图如下图所示：,典,例剖,析,伪代码如下：,Read,a,，,b,While,a,b,r,a,b,If,b,r,Then,a,b,b,r,Else,a,r,End,If,End,While,Print,b,典,例剖,析,(,1,),更相减损术的基本步骤是用较大的数,(,用,a,表示,),减去较小的数,(,用,b,表示,),，每次操作后所得的两数与前两数具有相同的最大公约数，而两数的值逐渐减小，经过有限步操作后，总能得到相等的两个数，即求得两数的最大公约数,规律总结：,典,例剖,析,(,2,),辗转相除法进行的是除法运算，执行次数由余数是否为,0,决定，更相减损术进行的是减法运算，执行次数由差数与较小的数是否相等决定，二者实质都是一个不断递归的过程，是一个反复执行的步骤，因而用循环结构就可实现其算法,典,例剖,析,3,运行下面的伪代码，当输入,78,和,36,时，输出的结果是,_,变式训练,Read,a,，,b,While,a,b,If,a,b,Then,a,a,b,Else,b,b,a,End,If,End,While,Print,a,典,例剖,析,伪代码是求,78,与,36,的最大公约数,(,78,，,36,),(,42,，,36,),(,6,，,36,),(,6,，,30,),(,6,，,24,),(,6,，,18,),(,612,),(,6,，,6,),，所以,78,和,36,的最大公约数为,6,.,解析：,6,答案：,典,例剖,析,例,4,已知函数,f,(,x,),x,2,5,，写出求方程,f,(,x,),0,在,2,，,3,上的近似解,(,精确到,0,.,001,),的算法伪代码，并画出流程图,由题目可获取以下主要信息：,(,1,),已知函数,f,(,x,),x,2,5,；,(,2,),求方程,f,(,x,),0,在,2,，,3,上的近似解；,分析：,典,例剖,析,(,3,),精确到,0,.,001,.,解答本题可先回忆一下二分法求近似根的步骤，由步骤画出流程图，然后再写出算法的伪代码,流程图如下图所示解析：,典,例剖,析,典,例剖,析,x,1,2,x,2,3,Do,x,0,f,(,x,1,),x,5,f,(,x,0,),x,5,If,f,(,x,0,),0,Then,Exit,Do,If,f,(,x,1,),f,(,x,0,),0,Then,x,2,x,0,Else,伪代码为：,典,例剖,析,x,1,x,0,End,If,Until,|,x,1,x,2,|,0,.,001,End,Do,Print,x,0,针对这个类型的题目书写伪代码时一定要注意伪代码的具体格式，另外循环语句中一定包含有条件结构的语句求高次方程近似解时，一定要给出精确度,规律总结：,典,例剖,析,变式训练,4,写算法，用二分法求,log,2,30,的值,(,精确到,0,.,001,),并画出流程图，写出伪代码,典,例剖,析,设,log,2,30,m,，令,f,(,x,),log,2,30,x,，据估计,m,4,，,5,令,a,4,，,b,5,，其算法步骤可表示为：,第一步取,a,，,b,中点,m,0,(,a,b,),，将区间一分为二,第二步若,f,(,m,0,),0,，则,m,0,即为所求；否则，判断,m,在,m,0,的左侧还是右侧,若,f,(,a,),f,(,m,0,),0,，则,m,(,m,0,，,b,),，以,m,0,代替,a,；,若,f,(,a,),f,(,m,0,),0,，则,m,(,a,，,m,0,),，以,m,0,代替,b,.,第三步若,|,a,b,|,0,.,001,，计算终止，此时,m,m,0,，否则转第一步,解析：,典,例剖,析,流程图如下图所示,解析：,典,例剖,析,流程图如下图所示,解析：,a,4,b,5,Do,m,0,(,a,b,),f,(,a,),log,2,30,a,f,(,m,0,),log,2,30,m,0,If,f,(,m,0,),0,Then,Exit,Do,If,f,(,a,),f,(,m,0,),0,Then,b,m,0,Else,a,m,0,End,If,Until,|,a,b,|,0,.,001,End,Do,Print,m,0,