高一数学 算法案例课件 新人教A版必修3 课件VIP专享VIP免费

四.算法案例1.1.多项式求值的秦九韶方法如果给定一个多项式如果给定一个多项式,,(3.4.1)(3.4.1)其中现在的问题是，给定一个其中现在的问题是，给定一个xx的值，的值，要求多项式函数的值。对于这个问题，一种要求多项式函数的值。对于这个问题，一种看起来很“自然”的方法是直接逐项求和。如果用看起来很“自然”的方法是直接逐项求和。如果用表示表示xx的的kk次次幂幂，表示式，表示式(3.4.1)(3.4.1)右端前右端前kk+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xPnPROCEDUREPROCEDURECPOLYCPOLY（（AA，，nn，，xx，，PP））FORi=2TOnDOFORi=2TOnDOOUTPUTPOUTPUTPRETURNRETURNxt;x1A0AptiAPP;xtt在这个算法中，为了计算一个在这个算法中，为了计算一个xx点处的函数点处的函数,,共需要作共需要作2n-12n-1次乘法和次乘法和nn次加法。还能不能减少乘法的次数呢？次加法。还能不能减少乘法的次数呢？我们可以将式我们可以将式(3.4.1)(3.4.1)的右端按降幂次序重新排列，并的右端按降幂次序重新排列，并将它表述成如下嵌套形式将它表述成如下嵌套形式012n1nnnaxaxaxaxaxP这样，就可以利用式这样，就可以利用式(3.4.4)(3.4.4)的特殊结构，从里往外一的特殊结构，从里往外一层一层地进行计算，即按如下递推关系进行计算：层一层地进行计算，即按如下递推关系进行计算：k1kknnaxuuau0,1,,1nk最后可得结果最后可得结果(3.4.4)(3.4.4)（（3.4.3.4.55））0nuxP这种多项式求值的方法是由我国宋代的一位这种多项式求值的方法是由我国宋代的一位数学家秦九韶最先提出的，我们称之为秦九数学家秦九韶最先提出的，我们称之为秦九韶方法，在有的书上也叫霍纳韶方法，在有的书上也叫霍纳(Horner)(Horner)方方法。其算法描述如下法。其算法描述如下::算法算法3.23.2多项式求值的秦九韶方法．多项式求值的秦九韶方法．输入：存放的系数数组输入：存放的系数数组A(0A(0：：n)n)；；自变量自变量xx值。其中值。其中。。输出：值输出：值PP。。xPnxPn1nPROCEDUREPROCEDURECHORNERCHORNER（（A,n,x,PA,n,x,P））FORi=n-1TO0BY-1DOFORi=n-1TO0BY-1DOOUTPUTPOUTPUTPRETURNRETURNnAPiAxPP由秦九韶算法可以看出，多项式函数的求由秦九韶算法可以看出，多项式函数的求值只要用一个很简单的循环就能完成，并值只要用一个很简单的循环就能完成，并且在这个循环中只需要作且在这个循环中只需要作nn次乘法和次乘法和nn次次加法就够了。它在实际使用中是一个很有加法就够了。它在实际使用中是一个很有效的方法。效的方法。例.中国剩余定理（孙子定理）若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(modmi)（i=1，2…k）∴用孙子定理解同余式组：xi=bi(modmi)（i=1，2…k）的算法步骤如下：kiiii'iii'i'iiikiiMbaxMM,...,k)(imMMMkimMMmM1i0)(moda.31)(mod1.2)...,,1(.1数解是：...