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

《2012高一数学 算法案例课件 新人教A版必修3.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、四.算法案例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，…

2、直到n，反复利用公式（3.4.2)进行计算，最后就可以得到。其算法描述如下:(1)逐项法多项式求值。输入：存放的系数数组A(0：n）；自变量x值。其中输出：值PPROCEDURECPOLY（A，n，x，P）FORi=2TOnDOOUTPUTPRETURN在这个算法中，为了计算一个x点处的函数,共需要作2n-1次乘法和n次加法。还能不能减少乘法的次数呢？我们可以将式(3.4.1)的右端按降幂次序重新排列，并将它表述成如下嵌套形式这样，就可以利用式(3.4.4)的特殊结构，从里往外一层一层地进行计算，即按如下

3、递推关系进行计算：最后可得结果(3.4.4)（3.4.5）这种多项式求值的方法是由我国宋代的一位数学家秦九韶最先提出的，我们称之为秦九韶方法，在有的书上也叫霍纳(Horner)方法。其算法描述如下:算法3.2多项式求值的秦九韶方法．输入：存放的系数数组A(0：n)；自变量x值。其中。输出：值P。PROCEDURECHORNER（A,n,x,P）FORi=n-1TO0BY-1DOOUTPUTPRETURN由秦九韶算法可以看出，多项式函数的求值只要用一个很简单的循环就能完成，并且在这个循环中只需要作n次乘法和

4、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(modmi)（i=1，2…k）∴用孙子定理解同余式组：xi=bi(modmi)（i=1，2…k）的算法步骤如下：

5、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或f(c)

6、>0，则用c值取代相应的a或b（取代原则是：保证有f(a)f(b)<0），这样（a,b）的长度就只有原来的一半，我们可以更小的范围找到根。当有根的区间的长度足够小（通常是小于预先指定的误差），这时区间内任意两点的距离都小于区间的长度，所以区间内的任意一点都可以用来当方程根的近似值。这个就是对半求根法参考算法：第一步确定有解区间第二步取的中点第三步计算函数f(x)在中点处的函数值。第四步判断函数值是否为0。（1）如果为0，就是方程的解，问题就得到了解决。（2）如果函数值不为0，则分下列两种情形：①若，则确定

7、新的有解区间为；②若，则确定新的有解区间为第五步判断新的有解区间的长度是否小于精确度：（1）如果新的有解区间长度大于精确度，则在新的有解区间的基础上重复上述步骤；（2）如果新的有解区间长度小于或等于精确度，则取新的有解区间的中点为方程的近似解。对半求根的过程可以用如下框图表示（图4-1）用流程图表示如下：例（对半法求方程解）：方程x-3sinx=0有一个根，试把它求出来，要求准确到0.0001。例闰年问题：输入年份y，判断该年份是否为闰年并输出结果。设y为年份，按照历法的规定，如果y为闰年，那么或者y能

8、被4整除但不能被100整除，或者y能被400整除。可以用选择结构将上述算法表示如下：若y不能被4整除，则输出“y不是闰年”；若y能被4整除，则判断y是否被100整除，则：（2）若y能被100整除，则判断y是否能被400整除，则：（1）若y不能被100整除，则输出“y是闰年”①若y能被400整除，则输出“y是闰年”；②若y不能被400整除，则输出“y不是闰年”。这个算法的流程图如下图4-3：小球运动问题问题：小球从10米高处自由