4算法案例 人教版必修三第一章算法初步课件大全VIP免费

四 . 算法案例1.1. 多项式求值的秦九韶方法如果给定一个多项式如果给定一个多项式 , , (3. 4.1)(3. 4.1)其中 现在的问题是，给定一个其中 现在的问题是，给定一个 xx 的值，的值，要求多项式函数 的值。对于这个问题，一种要求多项式函数 的值。对于这个问题，一种看起来很“自然”的方法是直接逐项求和。如果用 看起来很“自然”的方法是直接逐项求和。如果用 表示 表示 xx 的的 kk 次次幂幂， 表示式， 表示式 (3. 4.1)(3. 4.1) 右端前右端前 k k +l+l 项的部分和，即项的部分和，即 nnnxaxaxaaxP22101n  xPnktkukkxtkk2210kxaxaxaau 由于由于 xx 的的 kk 次幂实际上等于其次幂再乘上次幂实际上等于其次幂再乘上 xx ，，而前而前 k+1k+1 项的部分和等于前项的部分和等于前 kk 项的部分和再项的部分和再加上第加上第 k +lk +l 项，因此，逐项求和的方法可以项，因此，逐项求和的方法可以归结为如下的递推关系：归结为如下的递推关系：kk1kk1kktauuxttn,,2,1k(3.4.2)作为递推公式 (3.4.2) 的初值为 :000au1t(3.4.3) 这样，就可以利用初值这样，就可以利用初值 (3.4.3)(3.4.3) ，对于，对于 k=1k=1 ，，22 ，…直到，…直到 nn ，反复利用公式（，反复利用公式（ 3.4.2)3.4.2) 进行进行计算，最后就可以得到。其算法描述如下计算，最后就可以得到。其算法描述如下 ::(1) 逐项法多项式求值。 输入：存放的系数数组 A(0 ： n）； xPn自变量 x 值。其中1n  输出：值 P xPn PROCEDURE PROCEDURE CPOLYCPOLY （（ AA ，， nn ，， xx ，， PP ））FOR i=2 TO n DOFOR i=2 TO n DOOUTPUT POUTPUT PRETURNRETURN  xt;x1A0Ap tiAPP;xtt 在这个算法中，为了计算一个在这个算法中，为了计算一个 xx 点处的函数点处的函数 ,, 共需要作共需要作2n-12n-1 次乘法和次乘法和 nn 次加法。还能不能减少乘法的次数呢？次加法。还能不能减少乘法的次数呢？我们可以将式我们可以将式 (3. 4. 1)(3. 4. 1) 的右端按降幂次序重新排列，并的右端按降幂次序重新排列，并将它表述成如下嵌套形式将它表述成如下嵌套形式 012n1nnnaxaxaxaxaxP这样，就可以利用式这样，就可以利用式 (3.4.4)(3.4.4)...