高中数学人教版新课标A必修3第一章 算法初步1.3 算法与案例图片课件ppt

这是一份高中数学人教版新课标A必修3第一章 算法初步1.3 算法与案例图片课件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值。其中输出： 值PPROCEDURE CPOLY（A，n，x，P）FOR i=2 TO n DOOUTPUT PRETURN在这个算法中，为了计算一个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 PRETURN由秦九韶算法可以看出，多项式函数的求值只要用一个很简单的循环就能完成，并且在这个循环中只需要作n次乘法和n次加法就够了。它在实际使用中是一个很有效的方法。例. 中国剩余定理（孙子定理）若k>2，且m1，m2，…mk是两两互素的k个正整数，令M= m1m2…mk=m1M1=m2M2=…=mkMk。 则同余式组：x1=b1(modm1)，x2=b2(modm2)，…xk=bk(modmk) 其正整数解是：X≡b1M1’M1+b2M2’M2+…+bkMk’Mk(modM) 其中Mi’是满足同余式： Mi’Mi≡1(mod mi) （i = 1，2…k） ∴用孙子定理解同余式组： xi=bi(modmi) （ i = 1，2…k ）的算法步骤如下：2.对半法查找(二分法)算法对这种算法的实质是在一个有限且有序的对象中，通过每次缩减一半查找范围而达到迅速确定目的一个有效算法。因此有着很广泛的应用。例如，在数学中有很多方程是写不出根的解析表达式的，但是根的存在范围比较容易确定，那么如何才能找到它的根的一个足够准确的近似值呢？这时对半查找算法就可以大显身手了。由初等函数f(x)=0构成的方程，如果有f(a)f(b) b > c > 10，a×b×c==30723，且a > b+c，试确定a、b、c的值。分析问题解决这个问题应当从a×b×c==30723入手。把30723三个整数相乘的积，只能有有限种情况，我们可以把这些情况一一罗列出来，然后分析哪一种情况是符合条件的。从而找到答案。(在列举所有情况时，注意三个因子都大于10，这可以减少列举的工作量)。把30723分解为3个大于10的因子的乘积只有5种情况①11×19×147(三个因子的和是177)②11×21×133(三个因子的和是165)③19×49×57 (三个因子的和是101)④11×49×57 (三个因子的和是117)⑤19×21×77 (三个因子的和是117)在这5种情况中考察，符合a>b+c而且最大的数小于100的，只有最后一种情况，即a=77，b=21，c=19。计算算法设计穷举算法的关键是如何列举所有可能的情况，绝对不能遗漏，最好不要重复。在列举时注意变量的范围，可以减少工作量。我们可以从最小的变量c入手，让它从10开始变化。但变化的范围到哪里为止呢？粗略估算一下，三个数相乘是30723，最小的c不超过它的立方根。我们可以用平方根做近似替代，不必作太多推算。当c值产生之后，就可以处理变量b。因为它不小于c，让它从c开始，也让它变化到30723的平方根。有了c和b的值之后，就要判断他们是否都是30723的因子。如果是，计算出第三个因子a，然后进行判断：a是否大于b+c并且a