13案例2秦九韶算法

1、20222022年年6 6月月1919日星期日日星期日2 2时时4141分分2424秒秒20222022年年6 6月月1919日星期日日星期日2 2时时4141分分2424秒秒 学习目标学习目标 1.理解并掌握秦九韶算法的计算过程理解并掌握秦九韶算法的计算过程,了解利用秦九韶算了解利用秦九韶算法可以减少计算次数提高效率的实质法可以减少计算次数提高效率的实质 2.通过秦九韶算法通过秦九韶算法,进一步算法的基本思想进一步算法的基本思想,了解其算法程了解其算法程序框图和程序序框图和程序 3.理解数学算法与计算机算法的区别理解数学算法与计算机算法的区别,理解计算机对数学理解计算机对数学的辅助作用的辅助

2、作用. 4.通过对秦九韶算法的学习通过对秦九韶算法的学习,了解中国古代数学家对数学了解中国古代数学家对数学的贡献的贡献,认识中国文化历史的悠久认识中国文化历史的悠久.20222022年年6 6月月1919日星期日日星期日2 2时时4141分分2424秒秒复习复习1 1、求两个数的最大公约数的两种方法分别是（、求两个数的最大公约数的两种方法分别是（ ）和（和（ ）. .2 2、两个数、两个数2167221672，81278127的最大公约数是（的最大公约数是（ ）A A、2709 B2709 B、2606 C2606 C、2703 D2703 D、2706270620222022年年6 6月月1

3、919日星期日日星期日2 2时时4141分分2424秒秒问题问题怎样求多项式怎样求多项式f(x)=xf(x)=x5 5+x+x4 4+x+x3 3+x+x2 2+x+1+x+1当当x=5x=5时的值？时的值？算法算法1 1(5)=55555 = 3906算法算法2 2(5)=55555=5(5555 ) =5(5(555 ) ) =5(5(5(5+5 +) + ) + ) +=5(5(5(5 (5 +) + )+)+) +共做了共做了1+2+3+4=101+2+3+4=10次乘法运算次乘法运算,5,5次加法运算次加法运算. .共做了共做了4 4次乘法运算次乘法运算,5,5次加法运算次加法运算.

4、 .秦九韶算法秦九韶算法20222022年年6 6月月1919日星期日日星期日2 2时时4141分分2424秒秒新新 课课数书九章数书九章秦九韶算法秦九韶算法对该多项式按下面的方式进行改写对该多项式按下面的方式进行改写设设)(xf是一个是一个n n 次的多项式次的多项式1110( )nnnnf xa xaxa xa 1110( )nnnnf xa xaxa xa 12110()nnnna xaxaxa 231210()nnnna xaxaxaxa 1210()nnna xaxaxaxan次加法运算次加法运算(1)2n n 次乘法运算次乘法运算20222022年年6 6月月1919日星期日日星期

5、日2 2时时4141分分2424秒秒要求多项式的值，应该先算最内层的一次多项式的值，即要求多项式的值，应该先算最内层的一次多项式的值，即然后，由内到外逐层计算一次多项式的值，即然后，由内到外逐层计算一次多项式的值，即 这种将求一个这种将求一个n n次多项式次多项式f(xf(x) )的值转化成的值转化成求求n n个个一次多项式一次多项式的值的方法的值的方法, ,称为称为秦九韶算法秦九韶算法1210( )()nnnf xa xaxaxaxa11nnva xa 212nvv xa 323nvv xa 10nnvvxa 这是一个在这是一个在秦秦九韶算法中反九韶算法中反复执行的步骤复执行的步骤,因此可用

6、循环因此可用循环结构来实现结构来实现.01(1,2, )nkkn kvavvxakn n次加法运算次加法运算n次乘法运算次乘法运算20222022年年6 6月月1919日星期日日星期日2 2时时4141分分2424秒秒01(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 v的值初始化为的值

7、初始化为a an n, ,将将i i的值初始化为的值初始化为n-1n-1第三步：输入第三步：输入i i次项的系数次项的系数a ai i第四步：第四步：v=vx+av=vx+ai i,i,i=i-1.=i-1.第五步：判断第五步：判断i i是否大于或等于是否大于或等于0,0,若是若是, ,则返回第三步则返回第三步; ;否则否则, ,输出多项式的值输出多项式的值v.v.20222022年年6 6月月1919日星期日日星期日2 2时时4141分分2424秒秒第一步：输入多项式次数第一步：输入多项式次数n n、最、最高次项的系数高次项的系数a an n和和x x的值的值第二步：将第二步：将v v的值初

8、始化为的值初始化为a an n, ,将将i i的值初始化为的值初始化为n-1n-1第三步：输入第三步：输入i i次项的系数次项的系数a ai i第四步：第四步：v=vx+av=vx+ai i,i,i=i-1.=i-1.第五步：判断第五步：判断i i是否大于或等于是否大于或等于0,0,若是若是, ,则返回第三步则返回第三步; ;否则否则, ,输输出多项式的值出多项式的值v.v.程序框图程序框图开始开始输入输入n,an,x的值的值v=ani=n-1i0？输出输出v输入输入aiv=vx+aii=i-1结束结束NY20222022年年6 6月月1919日星期日日星期日2 2时时4141分分2424秒秒

9、开始开始输入输入n,an,x的值的值v=ani=n-1i0？输出输出v输入输入aiv=vx+aii=i-1结束结束NYINPUT “n=”；nINPUT “an=”；aINPUT “x=”；xv=ai=n-1WHILE i=0 PRINT “i=”；i INPUT “ai=”;a v=v*x+a i=i-1WENDPRINT vEND程序程序20222022年年6 6月月1919日星期日日星期日2 2时时4141分分2424秒秒按由里到外的顺序按由里到外的顺序,依此计算一次多项式当依此计算一次多项式当x = 5时的值：时的值：所以所以,x = f(5)=时时17255.2例例2 已知一个五次多项式为已知一个五次多项式为用秦九韶算法求这个多项式当用秦九韶算法求这个多项式当x = 5的值的值.5432( )523.52.61.70.8f xxxxxx解：解： 将多项式变形：将多项式变形：( )(52)3.5)2.6)1.7)0.8f xxxxxx05v 15 5227v 22