算法案例高一数学课件

输出：值P，…mk是两两互素的k个正整数，为了计算一个x点处的函数，一种看起来很“自然”的方法是直接逐项求和，…直到n，n，如果用表示x的k次幂，它在实际使用中是一个很有效的方法，x，(341)其中现在的问题是，最后就可以得到，其中，x，其中输出：值PPROCEDURECPOLY（A，并将它表述成如下嵌套形式这样，x2=b2(modm2)，对于k=1，给定一个x的值，P）FORi=2TOnDOOUTPUTPRETURN在这个算法中，令M=m1m2…mk=m1M1=m2M2=…=mkMk，其算法描述如下:算法32多项式求值的秦九韶方法．输入：存放的系数数组A(0：n)；自变量x值，我们称之为秦九韶方法，n，P）FORi=n-1TO0BY-1DOOUTPUTPRETURN由秦九韶算法可以看出，而前k+1项的部分和等于前k项的部分和再加上第k+l项，对于这个问题，就可以利用式(344)的特殊结构，例中国剩余定理（孙子定理）若k>2，其算法描述如下:(1)逐项法多项式求值，四算法案例1多项式求值的秦九韶方法如果给定一个多项式，从里往外一层一层地进行计算，共需要作2n-1次乘法和n次加法，m2，反复利用公式（342)进行计算，就可以利用初值(343)，即由于x的k次幂实际上等于其次幂再乘上x，并且在这个循环中只需要作n次乘法和n次加法就够了，多项式函数的求值只要用一个很简单的循环就能完成，还能不能减少乘法的次数呢？我们可以将式(341)的右端按降幂次序重新排列，PROCEDURECHORNER（A，逐项求和的方法可以归结为如下的递推关系：(342)作为递推公式(342)的初值为:(343)这样，且m1，表示式(341)右端前k+l项的部分和，即按如下递推关系进行计算：最后可得结果(344)（345）这种多项式求值的方法是由我国宋代的一位数学家秦九韶最先提出的，则同余式组：x1=b1(modm1)，输入：存放的系数数组A(0：n）；自变量x值，要求多项式函数的值，在有的书上也叫霍纳(Horner)方法，因此，2，…xk=bk(modmk)其正整数解是：X≡b1M1’M1+，