1.3.2 案例2、秦九韶算法,辗转相除法 更相减损术,A,案例2、秦九韶算法,秦九韶算法是求一元多项式的值的一种方法。,问题,怎样求多项式f(x)=x5+x4+x3+x2+x+1当x=5时的值呢？,算法一：把5代入，计算各项的值，然后把它们加起来。,算法二：先计算x2的值，然后依次计算x2x、（ x2x）x、（ （ x2x）x）x的值。,计算多项式（） =当x = 5的值,因为（） =,所以（5）=55555,=3125625125255,= 3906,分析：算法1中用了几次乘法运算？和几次加法运算？,算法一：把5代入，计算各项的值，然后把它们加起来。,=5x5x5x5x55x5x5x55x5x55x55,算法1：,算法2：,（5）=55555,=5（5555） ,=5（5（555 ） ） ,=5（5（ 5 （55 ） ） ） ,=5（5（ 5 （5 （5 ） ） ） ） ,算法二：先计算x2的值，然后依次计算 x2x、（ x2x）x、（ （ x2x）x）x 的值,分析：算法2中用了几次乘法运算？和几次加法运算？,计算多项式（） =当x = 5的值,计算多项式（） =当x = 5的值,算法1：,因为（） =,所以（5）=55555,=3125625125255,= 3906,算法2：,（5）=55555,=5（5555） ,=5（5（555 ） ） ,=5（5（ 5 （55 ） ） ） ,=5（5（ 5 （5 （5 ） ） ） ） ,10次的乘法运算,5次的加法运算,4次的乘法运算,5次的加法运算,显然，采用第二种算法，计算机能够更快地得到结果。,那么，有没有更有效的算法呢？,数书九章秦九韶算法,对该多项式按下面的方式进行改写,省略了若干 个半括号,省略了若干项,要求多项式的值，应该先算最内层的一次多项式的值，即,然后，由内到外逐层计算一次多项式的值，即,这种将求一个n次多项式f(x)的值转化成求n个一次多项式的值的方法,称为秦九韶算法,分析：秦九韶算法中用了几次乘法运算？和几次加法运算？,解： 按由里到外的顺序,依此计算一次多项式当x = 5时的值：,所以,x = 5时，多项式的值为17255.2,练习：教材P48、 2,课后必做作业： 请同学们课后阅读教材38页，理解并能识别秦九韶算法的程序。,秦九韶算法的程序设计,秦九韶算法的程序设计,秦九韶算法的程序设计,课堂小结： 1、秦九韶算法的方法和步骤 2、秦九韶算法的流程图及程序,谢谢观看！ 2020,