数学必修三132《算法案例-秦九韶算法》

1、1.3 1.3 算法案例算法案例 第二课时第二课时 案例案例2 2秦九韶算法秦九韶算法问题提出问题提出教学设计教学设计问题问题1设计求多项式设计求多项式f(x)=2x5-5x4-4x3+3x2-6x+7当当x=5时的值的算法时的值的算法,并写出程序并写出程序.x=5f=2x5-5x4-4x3+3x2-6x+7PRINT fEND程序程序点评点评:上述算法一共做了上述算法一共做了15次乘法运算次乘法运算,5次次加法运算加法运算.优点是简单优点是简单,易懂易懂;缺点是计算效率不高缺点是计算效率不高. 这样计算上述多项式的值这样计算上述多项式的值,一共需要一共需要9次乘次乘法运算法运算,5次加法运算

2、次加法运算.问题问题2有没有更高效的算法有没有更高效的算法?分析分析:计算计算x的幂时的幂时,可以利用前面的计算结可以利用前面的计算结果果,以减少计算量以减少计算量,即先计算即先计算x2,然后依次计算然后依次计算222,(),()xx xxxxxxx的值的值.第二种做法与第一种做法相比第二种做法与第一种做法相比,乘法的运乘法的运算次数减少了算次数减少了,因而能提高运算效率因而能提高运算效率.而且对于而且对于计算机来说计算机来说,做一次乘法所需的运算时间比做一做一次乘法所需的运算时间比做一次加法要长得多次加法要长得多,因此第二种做法能更快地得到因此第二种做法能更快地得到结果结果.f(x)=2x5

3、-5x4-4x3+3x2-6x+7问题问题3能否探索更好的算法能否探索更好的算法,来解决任意多来解决任意多项式的求值问题项式的求值问题?f(x)=2x5-5x4-4x3+3x2-6x+7=(2x4-5x3-4x2+3x-6)x+7=(2x3-5x2-4x+3)x-6)x+7=(2x2-5x-4)x+3)x-6)x+7=(2x-5)x-4)x+3)x-6)x+7这种求多项式值的方法就叫这种求多项式值的方法就叫秦九韶算法秦九韶算法.共用了多少次算法？共用了多少次算法？例用秦九韶算法求多项式例用秦九韶算法求多项式 f(x)=2x5-5x4-4x3+3x2-6x+7当当x=5时的值时的值.解法一解法一

4、:首先将原多项式改写成如下形式首先将原多项式改写成如下形式 : f(x)=(2x-5)x-4)x+3)x-6)x+7v0=2 v1=v0 x-5=25-5=5v2=v1x-4=55-4=21v3=v2x+3=215+3=108v4=v3x-6=1085-6=534v5=v4x+7=5345+7=2677所以所以,当当x=5时时,多多项式的值是项式的值是2677.然后由内向外逐层计算一次多项式的值然后由内向外逐层计算一次多项式的值,即即2 -5 -4 3 -6 7x=5105252110510854053426702677所以所以,当当x=5时时,多项式的值是多项式的值是2677.原多项式原多项

5、式的系数的系数多项式多项式的值的值.例用秦九韶算法求多项式例用秦九韶算法求多项式 f(x)=2x5-5x4-4x3+3x2-6x+7当当x=5时的值时的值.解法二解法二:列表列表22 -5 0 -4 3 -6 0 x=5105252512512160560830403034所以所以,当当x=5时时,多项式的值是多项式的值是15170.变式变式:用秦九韶算法求多项式用秦九韶算法求多项式 f(x)=2x6-5x5-4x3+3x2-6x当当x=5时的值时的值.解解:原多项式先化为原多项式先化为: f(x)=2x6-5x5 +0 x4-4x3+3x2-6x+0列表列表21517015170 注意注意:

6、n次多项式有次多项式有n+1项项,因此缺少哪一项因此缺少哪一项应将其系数补应将其系数补0.f(x)=anxn+an-1xn-1+an-2xn-2+a1x+a0.我们可以改写成如下形式我们可以改写成如下形式:f(x)=(anx+an-1)x+an-2)x+a1)x+a0.求多项式的值时求多项式的值时,首先计算最内层括号内一首先计算最内层括号内一次多项式的值次多项式的值,即即 v1=anx+an-1,然后由内向外逐层计算一次多项式的值然后由内向外逐层计算一次多项式的值,即即一般地一般地,对于一个对于一个n次多项式次多项式v2=v1x+an-2, v3=v2x+an-3, ,vn=vn-1x+a0.

7、这样这样,求求n次多项式次多项式f(x)的值就转化为求的值就转化为求n个个一次多项式的值一次多项式的值.这种算法称为这种算法称为秦九韶算法秦九韶算法.点评点评:秦九韶算法是求一元多项式的秦九韶算法是求一元多项式的值的一种方法值的一种方法.它的特点是它的特点是:把求一个把求一个n次多项式的值次多项式的值转化为求转化为求n个一次多项式的值个一次多项式的值,通过这种转通过这种转化化,把运算的次数把运算的次数由至多由至多n(n+1)/2次乘法次乘法运算和运算和n次加法运算次加法运算,减少为减少为n次乘法运算次乘法运算和和n次加法运算次加法运算,大大提高了运算效率大大提高了运算效率.（P38）v1=an

8、x+an-1,v2=v1x+an-2,v3=v2x+an-3, ,vn=vn-1x+a0.观察上述秦九韶算法中的观察上述秦九韶算法中的n个一次式个一次式,可见可见vk的计算要用到的计算要用到vk-1的值的值. 若令若令v0=an,得得v0=an,vK=vK-1x+an-k(k=1,2,n)这是一个在秦九韶算法中反复执行的步这是一个在秦九韶算法中反复执行的步骤骤,因此可用循环结构来实现因此可用循环结构来实现.探究探究: :秦九韶算法的程序设计秦九韶算法的程序设计 问题问题1:1:用秦九韶算法求多项式的值，可以用用秦九韶算法求多项式的值，可以用循环结构来构造算法，其算法步骤如何设计？循环结构来构造

9、算法，其算法步骤如何设计？第一步，输入多项式的次数第一步，输入多项式的次数n n，最高次，最高次 项的系数项的系数a an n和和x x的值的值. . 第二步，令第二步，令v=av=an n，i=n-1.i=n-1. 第三步，输入第三步，输入i i次项的系数次项的系数a ai i. . 第四步，第四步，v=vx+av=vx+ai i，i=i-1.i=i-1.第五步，判断第五步，判断i0i0是否成立是否成立. .若是，则返回第若是，则返回第 二步；否则，输出多项式的值二步；否则，输出多项式的值v.v. 问题问题2:2:该算法的程序框图如何表示？该算法的程序框图如何表示？开始开始输入输入n，an，x的值的值v=anv=vx+ai输入输入aii0？i=n- -1i=i- -1结束结束是是输出输出v否否问题问题3:3:该程序框图对应的程序如何表述？该程序框图对应的程序如何表述？开始开始输入输入n，an，x的值的值v=anv=vx+ai输入输入aii0？i=n- -1i=i- -1结束结束是是输出输出v否否INPUT “n=”INPUT “n=”；n nINPUT “an=”INPUT “an=”；a aINPUT “x=”INPUT “x=”；x x v=a