学习目标通过对算法案例的学习进一步体会算法的特点.ppt

《学习目标通过对算法案例的学习进一步体会算法的特点.ppt》由会员分享，可在线阅读，更多相关《学习目标通过对算法案例的学习进一步体会算法的特点.ppt（16页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、学习目标通过对算法案例的学习进一步体会算法的特点 Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life,there is hope。有生命必有希望。有生命必有希望学习目标：学习目标：通过对算法案例的学习，进一步体会算法的特点通过对算法案例的学习，进一步体会算法的特点。重点：理解秦九韶算法的思想。重点：理解秦九韶算法的思想。难点：用循环结构表示算法的步骤。难点：用循环结构表示算法的步骤。怎样求多项式怎样求多项式f(x)=xf(x)=x5 5+x+x4 4+x+x3 3+x+x2 2+x+1+x+1当当x=5x=5时的值呢？时的值呢

2、？计算多项式计算多项式()=)=当当x=5x=5的值的算法：的值的算法：算法算法1 1：(5)=5(5)=55 55 55 55 5算法算法2 2：f(5)=5f(5)=5(5(5(5(55 52 2)+5)+5(5(55 52 2)+5)+55 52 2+5+52 2+5+1+5+1算法算法3 3：(5)=5(5)=55 55 55 55 5=(5=(55 55 55 5)5 5=(5=(55 55 5)5 5)5 5=(5=(5+5+5+)5+5+)5+5+)5+5+=(5+=(5+)5+5+)5+5+)5+5+)5+5+共做了共做了1010次乘法，次乘法，5 5次加法。次加法。共做了共做

3、了4 4次乘法，次乘法，5 5次加法。次加法。共做了共做了4 4次乘法，次乘法，5 5次加法。次加法。再将第二种方法与第三种方法比较，两种方法都是利用再将第二种方法与第三种方法比较，两种方法都是利用上一步的结果进行运算。两种方法哪种更有效？我们将上题上一步的结果进行运算。两种方法哪种更有效？我们将上题加上系数再比较。加上系数再比较。算法二：算法二：共做了共做了9 9次乘法，次乘法，5 5次加法。次加法。算法三：算法三：共做了共做了5 5次乘法，次乘法，5 5次加法。次加法。分析各做了几次乘法和几次加法？分析各做了几次乘法和几次加法？请将下列多项式进行改写：请将下列多项式进行改写：设设是一个是一

4、个n n 次的多项式次的多项式对该多项式进行改写：对该多项式进行改写：推广到一般：推广到一般：把求一个把求一个n n次多项式的值转化为求次多项式的值转化为求n n个一次多个一次多项式的值项式的值,通过这种转化通过这种转化,把运算的次数减少为做把运算的次数减少为做n n次乘法和次乘法和n n次加法，大大提高了运算效率。次加法，大大提高了运算效率。秦九韶算法的特点：秦九韶算法的特点：这种将求一个这种将求一个n次多项式次多项式f(x)的值转化成求的值转化成求n个一个一次多项式的值的方法，称为次多项式的值的方法，称为秦九韶算法秦九韶算法。例：例：已知一个五次多项式为已知一个五次多项式为用秦九韶算法求这

5、个多项式当用秦九韶算法求这个多项式当x=5的值。的值。解：解：将多项式变形：将多项式变形：5 2 3.5 -2.6 1.7 -0.8 X5+25 5a0a1a2a3a4a5v1v2v3v4v5135692.5 3449.51725627 138.5689.9 3451.217255.2程序框图程序框图：输入输入f(x)的系数：的系数：a0,a1,a2,a3,a4a5输入输入x开始开始i 5?输出输出v v=vx+a5-i i=i+1YN v=a5 i=1结束结束(1)(1)、算法步骤：、算法步骤：第一步：输入多项式次数第一步：输入多项式次数n n、最高次项的系数、最高次项的系数a an n和和

6、x x的值的值.第二步：将第二步：将v v的值初始化为的值初始化为a an n，将，将i i的值初始化为的值初始化为1.1.第三步：输入第三步：输入n-in-i次项的系数次项的系数a an-in-i.第四步：第四步：v=vx+av=vx+an-in-i,i=i+1.,i=i+1.第五步：判断第五步：判断i i是否大于是否大于n n，若是，则输出多项式的，若是，则输出多项式的值值v v；否则，返回第三步。；否则，返回第三步。推广：一般的秦九韶算法的程序如何设计？推广：一般的秦九韶算法的程序如何设计？（2）程序框图：）程序框图：输入输入an-i开始开始输入输入n,an,xin?输出输出v结束结束v=vx+an-ii=i+1YNi=1V=an（3）程序：）程序：INPUT “n=”；nINPUT“an=“;aINPUT“x=“;xv=ai=1DOINPUT“a(n-i)=”;a v=v*x+a i=i+1LOOP UNTIL inPRINT vEND课堂小结：课堂小结：1 1、秦九韶算法的方法和步骤、秦九韶算法的方法和步骤2 2、秦九韶算法的程序框图、秦九韶算法的程序框图作业：作业：P48 2