【高中数学必修三】秦九韶算法(课堂PPT)

1、1 1.3.2 案例案例2、秦九韶算法、秦九韶算法2复习复习1 1、求两个数的最大公约数的两种方法分别是（、求两个数的最大公约数的两种方法分别是（ ）和（和（ ）. .2 2、两个数、两个数2167221672，81278127的最大公约数是（的最大公约数是（ ）A A、2709 B2709 B、2606 C2606 C、2703 D2703 D、27062706辗转相除法辗转相除法 更相减损术更相减损术A3 案例案例2、秦九韶算法、秦九韶算法秦九韶算法是求一元多项式的值的一种方法。秦九韶算法是求一元多项式的值的一种方法。怎样求多项式怎样求多项式f(x)=xf(x)=x5 5+x+x4 4+x

2、+x3 3+x+x2 2+x+1+x+1当当x=5x=5时的值呢？时的值呢？算法一：把算法一：把5代入，计算各项的值，然后把它们加起来。代入，计算各项的值，然后把它们加起来。算法二：先计算算法二：先计算x2的值，然后依次计算的值，然后依次计算x2x、（ x2x）x、（、（ （ x2x）x）x的值。的值。4 计算多项式计算多项式（） =当当x = 5的值的值因为因为（） =所以所以（5）=55555=3125625125255= 3906算法一：把算法一：把5代入，计算各项的值，然后把它们加起来。代入，计算各项的值，然后把它们加起来。=5x5x5x5x55x5x5x55x5x55x55算法算法1

3、：5算法算法2：（5）=55555=5（5555） =5（5（555 ） ） =5（5（ 5 （55 ） ） ） =5（5（ 5 （5 （5 ） ） ） ） 算法二：先计算算法二：先计算x2的值，然后依次计算的值，然后依次计算 x2x、（、（ x2x）x、（、（ （ x2x）x）x 的值的值 计算多项式计算多项式（） =当当x = 5的值的值6计算多项式计算多项式（） =当当x = 5的值的值算法算法1：因为因为（） =所以所以（5）=55555=3125625125255= 3906算法算法2：（5）=55555=5（5555） =5（5（555 ） ） =5（5（ 5 （55 ） ） ）

4、=5（5（ 5 （5 （5 ） ） ） ） 10次的乘法运算次的乘法运算,5次的加法运算次的加法运算4次的乘法运算次的乘法运算,5次的加法运算次的加法运算显然，采用第二种算法，计算机能够更快地得到结果。显然，采用第二种算法，计算机能够更快地得到结果。那么，有没有更有效的算法呢？那么，有没有更有效的算法呢？7数书九章数书九章秦九韶算法秦九韶算法对该多项式按下面的方式进行改写对该多项式按下面的方式进行改写设设)(xf是一个是一个n n 次的一元多项式次的一元多项式1110( )nnnnf xa xaxa xa 1110( )nnnnf xa xaxa xa 12110()nnnna xaxaxa

5、231210()nnnna xaxaxa xa 1210()nnna xaxaxa xa 省略了若干省略了若干个半括号个半括号省略了若干项省略了若干项8要求多项式的值，应该先算最内层的一次多项式的值，即要求多项式的值，应该先算最内层的一次多项式的值，即然后，由内到外逐层计算一次多项式的值，即然后，由内到外逐层计算一次多项式的值，即 这种将求一个这种将求一个n n次多项式次多项式f(x)f(x)的值转化成的值转化成求求n n个个一次多项式一次多项式的值的方法的值的方法, ,称为称为秦九韶算法秦九韶算法1210( )()nnnf xa xaxaxaxa11nnva xa 212nvv xa 323

6、nvv xa 10nnvvxa 01(1,2, )nkkn kvavvxakn 9解：解：按由里到外的顺序按由里到外的顺序,依此计算一次多项式当依此计算一次多项式当x = 5时的值：时的值：所以所以,x = 5时，多项式的值为时，多项式的值为17255.2例例2 已知一个五次多项式为已知一个五次多项式为用秦九韶算法求这个多项式当用秦九韶算法求这个多项式当x = 5的值的值.5432( )523.52.61.70.8f xxxxxx 05v 15 5227v 22753.5138.5v 3138.5 52.6689.9v 4689.9 51.73451.2v 53451.2 50.817255.

7、2v 练习：教材练习：教材P48、 201(1,2, )nkkn kvavvxakn 10课后必做作业：课后必做作业： 请同学们课后阅读教材请同学们课后阅读教材38页，理解并能识别秦九韶页，理解并能识别秦九韶算法的程序。算法的程序。1101(1,2, )nkkn kvavvxakn 11101210( )()nnnnnnnf xa xaxa xaa xaxaxaxa 11nnva xa 212nvv xa 323nvv xa 10nnvvxa 第一步：输入多项式次数第一步：输入多项式次数n n、最高次项的系数、最高次项的系数a an n和和x x的值的值算法步骤算法步骤第二步：将第二步：将v

8、v的值初始化为的值初始化为a an n, ,将将i i的值初始化为的值初始化为n-1n-1第三步：输入第三步：输入i i次项的系数次项的系数a ai i第四步：第四步：v=vx+av=vx+ai i,i=i-1.,i=i-1.第五步：判断第五步：判断i i是否大于或等于是否大于或等于0,0,若是若是, ,则返回第三步则返回第三步; ;否则否则, ,输出多项式的值输出多项式的值v.v.秦九韶算法的程序设计秦九韶算法的程序设计12第一步：输入多项式次数第一步：输入多项式次数n n、最、最高次项的系数高次项的系数a an n和和x x的值的值第二步：将第二步：将v v的值初始化为的值初始化为a an

9、 n, ,将将i i的值初始化为的值初始化为n-1n-1第三步：输入第三步：输入i i次项的系数次项的系数a ai i第四步：第四步：v=vx+av=vx+ai i,i=i-1.,i=i-1.第五步：判断第五步：判断i i是否大于或等于是否大于或等于0,0,若是若是, ,则返回第三步则返回第三步; ;否则否则, ,输输出多项式的值出多项式的值v.v.程序框图程序框图开始开始输入输入n,an,x的值的值v=ani=n-1i0？输出输出v输入输入aiv=vx+aii=i-1结束结束NY秦九韶算法的程序设计秦九韶算法的程序设计13开始开始输入输入n,an,x的值的值v=ani=n-1i0？输出输出v输入输入aiv=vx+aii=i-1结束结束NYINPUT “n=”；nINPUT “an=”；aINPUT “x=”；xv=ai=n-1WHILE