秦九韶算法
秦九韶算法
复习引入 1、求两个数的最大公约数的两种方法分别是 ()和() 2、两个数21672,8127的最大公约数是( A、2709B、2606C、2703D、2706
1、求两个数的最大公约数的两种方法分别是 （ ）和（ ）。 2、两个数21672，8127的最大公约数是 （ ） A、2709 B、2606 C、2703 D、2706 复习引入:
新课讲解: 怎样求多项式f(×)=x3+x+x3+x2+x+1当x=5时的值呢?
新课讲解: 考 思 怎样求多项式f(x)=x5+x4+x3+x2+x+1当x=5时的值呢？
计算多项式f(x)=x5+x4+x3+x2+x+1 当ⅹ=5的值的算法: 算法1因为f(X)=X5+x4+x3+x2+x+1 所以f(5)=55+54+53+52+5+1 3125+625+125+25+5+1 算法2 =3906 f(5)=55+54+53+52+5+1 5×(54+53+52+5+1)+1 =5×(5×(53+52+5+1)+1)+1 5×(5×(5×(52+5+1)+1)+1)+1 =5×(5×(5×(5×(5+1)+1)+1)+1)+1 分析:两种算法中各用了几次乘法运 算?和次加法
计算多项式ｆ(ｘ) =ｘ５＋ｘ４＋ｘ３＋ｘ２＋ｘ＋１ 当x = 5的值的算法： 算法1：因为ｆ(ｘ) =ｘ５＋ｘ４＋ｘ３＋ｘ２＋ｘ＋１ 所以ｆ(5)=5５＋5４＋5３＋5２＋5＋１ =3125＋625＋125＋25＋5＋１ 算法2： = 3906 ｆ(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 ×(5 +１) +１ )+１)+１) +１ 分析：两种算法中各用了几次乘法运 算？和几次加法运算？
算法1 因为f(x)=X5+x4+x3+x2+x+1 F以f(5)=55+54+53+52+5+1 =3125+625+125+25+5+1 =3906 共做了1+2+3+4=10次乘法运算,5次加法运算。 算法2 f(5)=55+54+53+52+5+1 =5×(54+53+52+5+1)+1 =5×(5×(53+52+5+1)+1)+1 =5×(5×(5×(52+5+1)+1)+1)+1 =5×(5×(5×(5×(5+1)+1)+1)+1)+1 共做了4次乘法运算,5次加法运算
算法1： 因为ｆ(ｘ) =ｘ５＋ｘ４＋ｘ３＋ｘ２＋ｘ＋１ 所以ｆ(5)=5５＋5４＋5３＋5２＋5＋１ =3125＋625＋125＋25＋5＋１ = 3906 算法2： ｆ(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 ×(5 +１) +１ )+１)+１) +１ 共做了1+2+3+4=10次乘法运算，5次加法运算。 共做了4次乘法运算，5次加法运算
《数书九章》——秦九韶算法 设f(x)是一个n次的多项式 这是怎样的 种改写方 对该多项式按下面的方式进行改写:式?最后的 结果是什么? 思考:当知道了x的值后该如何求多 项式的值?
《数书九章》——秦九韶算法 1 0 1 f(x)=anx n+an−1x n−++ax+a 设 f (x) 是一个n 次的多项式 对该多项式按下面的方式进行改写： 1 0 1 f(x)=anx n+an−1x n−++ax+a 1 0 2 1 =(anx n−1+an−x n−++a)x+a 2 1 0 3 1 =((an x n−2+an−x n−++a)x+a)x+a = =((anx+an−1)x+an−2)x++a1)x+a0 思考：当知道了x的值后该如何求多 项式的值？ 这是怎样的 一种改写方 式？最后的 结果是什么？
要求多项式的值,应该先算最内层的一次多项式的值,即 然后,由内到外逐计算一次多项式的值,即 吗=e+42/最后的 项是什么? 3=2Hz3 思考:在求多项式的值上,这是怎 这种将求一解多项术猴值转化成求n个一 次多项式的值的方法,称为秦九韶算法
f(x)=((anx+an−1)x+an−2)x+a1)x+a0 要求多项式的值，应该先算最内层的一次多项式的值，即 v1=anx+an−1 然后，由内到外逐层计算一次多项式的值，即 v2=v1x+an−2 v3 =v2x+an−3 vn =vn−1x+a0 最后的一 项是什么？ 这种将求一个n次多项式f(x)的值转化成求n个一 次多项式的值的方法，称为秦九韶算法。 思考：在求多项式的值上，这是怎 样的一个转化？
秦九韶算法的特点: 通过一次式的反复计算,逐步得出高次多 项式的值,对于一个n次多项式,只需做n次乘 法和n次加法即可
通过一次式的反复计算，逐步得出高次多 项式的值，对于一个n次多项式，只需做n次乘 法和n次加法即可。 秦九韶算法的特点：
例:已知一个五次多项式为 用秦九韶算法求这个多项式当x=5的值。 解将多项式变形 按由里到外的顺序,依此计算一次多项式当x=5时的值: 155 5B33 你从中看到了 怎样的规律? 5826白≤ 怎么用程序框 68Hz多4 图来描述呢 34868172 所以,当x=5时,多项式的值等于172552
例： 已知一个五次多项式为 f(x)=5x 5+2x 4+3.5x 3−2.6x 2+1.7x−0.8 用秦九韶算法求这个多项式当x = 5的值。 解：将多项式变形： f(x)=(((( 5x+2)x+3.5)x−2.6)x+1.7)x−0.8 按由里到外的顺序，依此计算一次多项式当x = 5时的值： v1=55+2=27 v0 = 5 v2=275+3.5=138.5 v3=138.55−2.6=689.9 v4=689.95+1.7=3451 .2 v5 =3451 .25−0.8=17255 . 所以，当x = 5时，多项式的值等于17255.2 你从中看到了 怎样的规律？ 怎么用程序框 图来描述呢？
开始 序框图: 输入fx)的系数: ao.a1a2a3.aa 输入 n=1 n=n+1 这是一个在秦九韶算法中 反复执行的步骤,因此可 V=VXota 用循环结构来实现。 5? 输出v 结束
程序框图： 开始 输入f(x)的系数： a0 ,a1 ,a2 ,a3 ,a4a5 输入x0 n≤5? 输出v 结束 v=vx0+a5-n n=n+1 Y N n=1 v=a5 = + = = v v − xa −(k ,, ,n) v a k k nk n 1 12 0 这是一个在秦九韶算法中 反复执行的步骤，因此可 用循环结构来实现