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

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,算法案例,1.,多项式求值的秦九韶方法,如果给定一个多项式,(3.4.1),其中 现在的问题是，给定一个,x,的值，要求多项式函数 的值。对于这个问题，一种看起来很“自然”的方法是直接逐项求和。如果用 表示,x,的,k,次,幂,，表示式,(3.4.1),右端前,k+l,项的部分和，即,由于,x,的,k,次幂实际上等于其次幂再乘上,x,，,而前,k+1,项的部分和等于前,k,项的部分和再加上第,k+l,项，因此，逐项求和的方法可以归结为如下的递推关系：,(3.4.2),作为递推公式,(3.4.2),的初值为,:,(3.4.3),这样，就可以利用初值,(3.4.3),，对于,k=1,，,2,，,直到,n,，,反复利用公式（,3.4.2),进行计算，最后就可以得到。其算法描述如下,:,(1),逐项法多项式求值。,输入：存放 的系数数组,A(0,：,n,）；,自变量,x,值。其中,输出：值,P,PROCEDURE CPOLY（A，n，x，P）,FOR i=2 TO n DO,OUTPUT P,RETURN,在这个算法中，为了计算一个,x,点处的函数,共需要作,2n-1,次乘法和,n,次加法。还能不能减少乘法的次数呢？我们可以将式,(3.4.1),的右端按降幂次序重新排列，并将它表述成如下嵌套形式,这样，就可以利用式,(3.4.4),的特殊结构，从里往外一层一层地进行计算，即按如下递推关系进行计算：,最后可得结果,(3.4.4),（,3.4.5,）,这种多项式求值的方法是由我国宋代的一位数学家秦九韶最先提出的，我们称之为秦九韶方法，在有的书上也叫霍纳,(Horner),方法。其算法描述如下,:,算法,3.2,多项式求值的秦九韶方法,输入：存放 的系数数组,A(0,：,n),；,自变量,x,值。其中 。,输出：值,P,。,PROCEDURE CHORNER（A,n,x,P）,FOR i=n-1 TO 0 BY -1 DO,OUTPUT P,RETURN,由秦九韶算法可以看出，多项式函数的求值只要用一个很简单的循环就能完成，并且在这个循环中只需要作,n,次乘法和,n,次加法就够了。它在实际使用中是一个很有效的方法。,例,.,中国剩余定理（孙子定理）若,k2,，且,m,1,，,m,2,，,m,k,是两两互素的,k,个正整数，令,M=m,1,m,2,m,k,=m,1,M,1,=m,2,M,2,=,m,k,M,k,。,则同余式组：,x,1,=b,1,(modm,1,),，,x,2,=b,2,(modm,2,),，,x,k,=,b,k,(modm,k,),其正整数解是：,Xb,1,M,1,M,1,+b,2,M,2,M,2,+,b,k,M,k,M,k,(modM,),其中,M,i,是满足同余式：,M,i,M,i,1(mod m,i,),（,i=1,，,2k,）,用孙子定理解同余式组：,x,i,=,b,i,(modm,i,),（,i=1,，,2k,）,的算法步骤如下：,2.,对半法查找,(,二分法,),算法,对,这种算法的实质是在一个有限且有序的对象中，通过每次缩减一半查找范围而达到迅速确定目的一个有效算法。因此有着很广泛的应用。例如，在数学中有很多方程是写不出根的解析表达式的，但是根的存在范围比较容易确定，那么如何才能找到它的根的一个足够准确的近似值呢？这时对半查找算法就可以大显身手了。,由初等函数,f(x)=0,构成的方程，如果有,f(a)f(b)0,，,则可以肯定方程,f(x)=0,在（,a,b,）,至少有一个实数根。,选择（,a,b,）,的中点,c,，若,f(c)=0,，,则根就是,x=c,。若,f(c)0,，,则用,c,值取代相应的,a,或,b,（,取代原则是：保证有,f(a)f(b)a b c 10,，,abc=30723,，且,a b+c,，,试确定,a,、,b,、,c,的值。,分析问题,解决这个问题应当从,abc=30723,入手。把,30723,三个整数相乘的积，只能有有限种情况，我们可以把这些情况一一罗列出来，然后分析哪一种情况是符合条件的。从而找到答案。,(,在列举所有情况时，注意三个因子都大于,10,，这可以减少列举的工作量,),。,把,30723,分解为,3,个大于,10,的因子的乘积只有,5,种情况,1119147(,三个因子的和是,177),1121133(,三个因子的和是,165),194957(,三个因子的和是,101),114957(,三个因子的和是,117),192177(,三个因子的和是,117),在这,5,种情况中考察，符合,ab+c,而且最大的数小于,100,的，只有最后一种情况，即,a=77,，,b=21,，,c=19,。,计算算法,设计穷举算法的关键是如何列举所有可能的情况，绝对不能遗漏，最好不要重复。在列举时注意变量的范围，可以减少工作量。,我们可以从最小的变量,c,入手，让它从,10,开始变化。但变化的范围到哪里为止呢？粗略估算一下，三个数相乘是,30723,，最小的,c,不超过它的立方根。我们可以用平方根做近似替代，不必作太多推算。,当,c,值产生之后，就可以处理变量,b,。,因为它不小于,c,，,让它从,c,开始，也让它变化到,30723,的平方根。,有了,c,和,b,的值之后，就要判断他们是否都是,30723,的因子。如果是，计算出第三个因子,a,，,然后进行判断：,a,是否大于,b+c,并且,a100,。,满足条件就是解答了。,例题,(,钱币问题,),在日程生活中常常需要用一些较小面额的钱币去组合出一定的币值。现有面值为,1,元、,2,元和,5,元的钞票,(,假设每种钞票的数量都足够多,),，从这些钞票中取出,30,张使其总面值为,100,元，问有多少种取法？每种取法的各种面值的钞票各为多少张？,分析问题,显然列出一条算式来解决钱币问题是有困难的。既然解析法很难用上，我们尝试通过列举所有可能的情况,(,穷举,),，从中判断出合符条件的解答。,当钞票数量比较多，总币值比较大时，人工列举所有钞票组合,(,穷举,),就很麻烦，这时需要使用计算机来帮我们穷举。但使用计算机来穷举，必须清楚地说出穷举的每一个步骤，并通过程序设计语言转化为计算机能后执行的过程，才能解决问题。,钱币问题有,3,种面额的钞票，钞票的总张数是,30,张，又应当如何穷举呢？经分析可以知道：当有两种面额的钞票数目确定了之后，可以从总张数为,30,确定第三种钞票的张数，然后由总面额是否,100,元而判断这个组合是否合乎要求。此外，先确定面额大的钞票可以使穷举的次数少些。,设计算法,用,ONE,、,TWO,、,FIVE,分别记录,1,元、,2,元、,5,元钞票的张数。变量,ANSWER,记录符合条件的解的数目。穷举的过程如下：,让,ANSWER=0,，,FIVE=0,；,TWO=0,让,ONE=30,TWO,FIVE,；,检查,5FIVE2TWOONE,是否等于,100,，若是，,则得到一组解，这时让,ANSWER,增加,1,。并且输出解答,如果,TWO30,，,那么让,TWO,增加,1,，转步骤；,如果,FIVE20,，,那么让,FIVE,增加,1,，转步骤,结束,可把这些步骤用框图表示如,图,4-7,：,Click to display,汉诺,(Hanoi),塔问题是一个著名的应用递归算法解决的问题。,问题,4-17,：,传说在古代印度的贝拿勒斯神庙里安放了一块黄铜板，板上插了三根宝石柱，在其中一根宝石柱自上而下由小到大地叠放着,64,个大小不等的金盘。一名僧人把这些金盘从一根宝石柱移到另外一根上。僧人在移动金盘时遵守下面,3,条规则：,一次只能移动一个金盘。,每个金盘只能由一根宝石柱移到另外一根宝石柱。,任何时候都不能把大的金盘放在小的金盘上。,神化说，如果僧人把,64,个金盘完全地从一根宝石柱移到了另外一根上，世界的末日就要到了。当然，神化只能当故事听，世界不可以因为个别人的活动而导致末日。不过，如果能够计算出僧人按规则搬完,64,个金盘，地球能否继续存在也的确是个问题！因为即使僧人的动作十分敏捷，每秒都能移动一个金盘，那也得要几亿年！,分析问题,要模拟金盘的移动过程是比较困难的，但如果用递归的思想来进行,(,压缩规模，把问题解决在最简单的情况,),，则问题可以解决。,我们把,3,根宝石柱分别命名为,A,、,B,、,C,。,最初有,N,个金盘放在,A,，,需要把它们全部按规则移动到,B,。,当,N=1,时，直接把金盘从,A,搬到,B,就可以了，,1,次成功。,当,N2,，,那么需要利用,C,柱来过渡。按照递归的思想，我们假设已经找到一种把,N,1,个金盘从一根柱搬到另外一根柱的方法，然后看看如何通过它来实现搬动,N,个金盘。我们只要把,N,1,个金盘从,A,搬到,C,，,然后把最大的金盘从,A,搬到,B,，,最后把,C,上的,N,1,个金盘搬到,B,就可以了。靠递归的思想，我们轻而易举地完成了整个搬动。,设计算法,我们定义一个过程,Hanoi(N,，,A,，,B,，,C),，,表示有,N,个金盘需要从,A,柱搬到,B,柱,(,以,C,柱为过渡,),。那么完成它只需,3,步：,Hanoi(N,1,，,A,，,C,，,B),它的意思是把,A,柱上的,N,1,个金盘搬到,C,柱，,AB,它的意思是把一个,(,最大的,),金盘从,A,柱搬到,B,柱，,Hanoi(N,，,C,，,B,，,A),它的意思是把,C,柱上的,N,1,个金盘搬到,B,柱。,