高中数学必修三1.3.2秦九韶算法.ppt

《高中数学必修三1.3.2秦九韶算法.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、1.3.2案例2、秦九韶算法复习1、求两个数的最大公约数的两种方法分别是（）和（）.2、两个数21672，8127的最大公约数是（）A、2709B、2606C、2703D、2706辗转相除法更相减损术A案例2、秦九韶算法秦九韶算法是求一元多项式的值的一种方法。问题怎样求多项式f(x)=x5+x4+x3+x2+x+1当x=5时的值呢？算法一：把5代入，计算各项的值，然后把它们加起来。算法二：先计算x2的值，然后依次计算x2·x、（x2·x）·x、（（x2·x）·x）·x的值。计算多项式ｆ（ｘ）=ｘ５＋ｘ４＋ｘ３＋ｘ

2、２＋ｘ＋１当x=5的值因为ｆ（ｘ）=ｘ５＋ｘ４＋ｘ３＋ｘ２＋ｘ＋１所以ｆ（5）=5５＋5４＋5３＋5２＋5＋１=3125＋625＋125＋25＋5＋１=3906分析：算法1中用了几次乘法运算？和几次加法运算？算法一：把5代入，计算各项的值，然后把它们加起来。=5x5x5x5x5＋5x5x5x5＋5x5x5＋5x5＋5＋１算法1：算法2：ｆ（5）=5５＋5４＋5３＋5２＋5＋１=5×（5４＋5３＋5２＋5＋１）＋１=5×（5×（5３＋5２＋5＋１）＋１）＋１=5×（5×（5×（5２＋5＋１）＋１）＋１）＋１=5×（

3、5×（5×（5×（5＋１）＋１）＋１）＋１）＋１算法二：先计算x2的值，然后依次计算x2·x、（x2·x）·x、（（x2·x）·x）·x的值分析：算法2中用了几次乘法运算？和几次加法运算？计算多项式ｆ（ｘ）=ｘ５＋ｘ４＋ｘ３＋ｘ２＋ｘ＋１当x=5的值计算多项式ｆ（ｘ）=ｘ５＋ｘ４＋ｘ３＋ｘ２＋ｘ＋１当x=5的值算法1：因为ｆ（ｘ）=ｘ５＋ｘ４＋ｘ３＋ｘ２＋ｘ＋１所以ｆ（5）=5５＋5４＋5３＋5２＋5＋１=3125＋625＋125＋25＋5＋１=3906算法2：ｆ（5）=5５＋5４＋5３＋5２＋5＋１=5×（5４

4、＋5３＋5２＋5＋１）＋１=5×（5×（5３＋5２＋5＋１）＋１）＋１=5×（5×（5×（5２＋5＋１）＋１）＋１）＋１=5×（5×（5×（5×（5＋１）＋１）＋１）＋１）＋１10次的乘法运算,5次的加法运算4次的乘法运算,5次的加法运算显然，采用第二种算法，计算机能够更快地得到结果。那么，有没有更有效的算法呢？《数书九章》——秦九韶算法对该多项式按下面的方式进行改写设是一个n次的一元多项式省略了若干个半括号省略了若干项要求多项式的值，应该先算最内层的一次多项式的值，即然后，由内到外逐层计算一次多项式的值，即这种

5、将求一个n次多项式f(x)的值转化成求n个一次多项式的值的方法,称为秦九韶算法分析：秦九韶算法中用了几次乘法运算？和几次加法运算？解：按由里到外的顺序,依此计算一次多项式当x=5时的值：所以,x=5时，多项式的值为17255.2例2已知一个五次多项式为用秦九韶算法求这个多项式当x=5的值.练习：教材P48、2课后必做作业：请同学们课后阅读教材38页，理解并能识别秦九韶算法的程序。第一步：输入多项式次数n、最高次项的系数an和x的值算法步骤第二步：将v的值初始化为an,将i的值初始化为n-1第三步：输入i次项的系数

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

7、n,x的值v=ani=n-1i≥0？输出v输入aiv=vx+aii=i-1结束NYINPUT“n=”；nINPUT“an=”；aINPUT“x=”；xv=ai=n-1WHILEi>=0PRINT“i=”；iINPUT“ai=”;av=v*x+ai=i-1WENDPRINTvEND程序秦九韶算法的程序设计课堂小结：1、秦九韶算法的方法和步骤2、秦九韶算法的流程图及程序