《学习目标通过对算法案例的学习进一步体会算法的特点.ppt》由会员分享，可在线阅读，更多相关《学习目标通过对算法案例的学习进一步体会算法的特点.ppt（16页珍藏版）》请在三一文库上搜索。
1、秦九韶算法,学习目标： 通过对算法案例的学习，进一步体会算法的特点。,重点：理解秦九韶算法的思想。,难点：用循环结构表示算法的步骤。,思考:,怎样求多项式 f(x)=x5+x4+x3+x2+x+1 当x=5时的值呢？,计算多项式() = 当x = 5的值的算法：,算法1：,(5)=55555,算法2：,f(5)=5(5(552)+5(552)+552+52+5+1,算法3：,(5)=55555,=(5555)5,=(555)5)5,=(5+5 +)5+)5+)5+,=(5+)5+)5+)5+)5+,分析：每种算法中各用了几次乘法运算？和几次加法运算？,共做了10次乘法，5次加法。,共做了4次乘
2、法，5次加法。,共做了4次乘法，5次加法。,再将第二种方法与第三种方法比较，两种方法都是利用 上一步的结果进行运算。两种方法哪种更有效？我们将上题 加上系数再比较。,算法二：,共做了9次乘法，5次加法。,算法三：,共做了5次乘法，5次加法。,分析各做了几次乘法和几次加法？,请将下列多项式进行改写：,对该多项式进行改写：,思考：当知道了x的值后该如何求多项式的值？,推广到一般：,把求一个n次多项式的值转化为求n个一次多项式的值,通过这种转化,把运算的次数减少为做n次乘法和n次加法，大大提高了运算效率。,秦九韶算法的特点：,这种将求一个n次多项式f(x)的值转化成求n个一次多项式的值的方法，称为秦
3、九韶算法。,例： 已知一个五次多项式为,用秦九韶算法求这个多项式当x = 5的值。,解：,将多项式变形：,5 2 3.5 -2.6 1.7 -0.8,X5,+,25,5,a0,a1,a2,a3,a4,a5,v1,v2,v3,v4,v5,135,692.5,3449.5,17256,27,138.5,689.9,3451.2,17255.2,程序框图：,开始,v=vx+a5-i,i=i+1,Y,N,v=a5,i=1,(1)、算法步骤：,第一步：输入多项式次数n、最高次项的系数an和x的值.,第二步：将v的值初始化为an，将i的值初始化为1.,第三步：输入n-i次项的系数an-i.,第四步：v=vx+an-i, i=i+1.,第五步：判断i是否大于n，若是，则输出多项式的值v；否则，返回第三步。,推广：一般的秦九韶算法的程序如何设计？,（2）程序框图：,in?,输出v,结束,v=vx+an-i,i=i+1,Y,N,V=an,（3）程序：,INPUT “n=”；n INPUT “an=“;a INPUT “x=“;x v=a i=1 DO INPUT “a(n-i)=”;a v=v*x+a i=i+1 LOOP UNTIL in PRINT v END,课堂小结： 1、秦九韶算法的方法和步骤 2、秦九韶算法的程序框图,作业： P48 2,谢谢,