1.3算法案例(秦九韶算法)

5

算 法 案 例

5

复习引入:1、求两个数的最大公约数的两种方法分别是 、 ( )和( )。

2、两个数21672,8127的最大公约数是 ( 、两个数 ， 的最大公约数是 A、2709 、 B、2606 、 C、2703 、 D、2706 、

)

5

新课讲解:怎样求多项式f(x)=x +x+1当x=5时的值呢 时的值呢？ 怎样求多项式f(x)=x5+x4+x3+x2+x+1当x=5时的值呢？

5

计算多项式f(x) =x5+x4+x3+x2+x+1 的值的算法： 当x = 5的值的算法： 的值的算法 算法1: 算法 ： f(x) =x5+x4+x3+x2+x+1 因为 所以f(5)=55+54+53+52+5+1 + =3125+625+125+25+5+1 + + + + + = 3906 算法2: 算法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 × × × 1 1 1 1 =5×(5×(5×(5 ×(5 +1) +1 )+1)+1) +1 × × × 1 1 1 1 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 + + + + + = 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 × × × 1 1 1 1 =5×(5×(5×(5 ×(5 +1) +1 )+1)+1) +1 × × × 1 1 1 1 1共做了4次乘法运算， 次加法运算 次加法运算。 共做了 次乘法运算，5次加法运算。 次乘法运算

5

《数书九章》——秦九韶算法 数书九章》 秦九韶算法 设 f (x) 是一个 次的多项式 是一个nn n 1

这是怎样的 f (x) = an x + an 1x +L+ a1x + a0 一种改写方 对该多项式按下面的方式进行改写： 对该多项式按下面的方式进行改写： 式？最后的 结果是什么？ n n 1 f (x) = an x + an 1x +L+ a1x + a0= (an xn 1 + an 1xn 2 +L+ a1)x + a0

=L L

= ((an xn 2 + an 1xn 3 +L+ a2 )x + a1)x + a0= (L(an x + an 1)x + an 2 )x +L+ a1)x + a0

5

f (x) = (L(an x + an 1)x + an 2 )x +L+ a1)x + a0要求多项式的值，应该先算最内层的一次多项式的值， 要求多项式的值，应该先算最内层的一次多项式的值，即 然后，由内到外逐层计算一次多项式的值， 然后，由内到外逐层计算一次多项式的值，即

v1 = an x + an 1 v2 = v1x + an 2

L L

v3 = v2 x + an 3

最后的一 项是什么？ 项是什么？

vn = vn 1x + a0

这种将求一个n次多项式 的值转化成求n个一 这种将求一个 次多项式f(x)的值转化成求 个一 次多项式 的值转化成求 次多项式的值的

方法，称为秦九韶算法 秦九韶算法。 次多项式的值的方法，称为秦九韶算法。

5

秦九韶算法的特点： 秦九韶算法的特点：通过一次式的反复计算， 通过一次式的反复计算，逐步得出高次多 项式的值，对于一个n次多项式 只需做n次乘 次多项式， 项式的值，对于一个 次多项式，只需做 次乘 法和n次加法即可 次加法即可。 法和 次加法即可。

5

例： 已知一个五次多项式为

f (x) = 5x5 + 2x4 + 3.5x3 2.6x2 +1.7x 0.8

用秦九韶算法求这个多项式当x 的值。 用秦九韶算法求这个多项式当 = 5的值。 的值 解： 将多项式变形： 将多项式变形：

f (x) = ((((5x + 2)x + 3.5)x 2.6)x +1.7)x 0.8

按由里到外的顺序，依此计算一次多项式当 时的值： 按由里到外的顺序，依此计算一次多项式当x = 5时的值： 时的值

v0 = 5 v1 = 5×5 + 2 = 27 v2 = 27×5+ 3.5 =138.5 v3 =138.5×5 2.6 = 689.9 v4 = 689.9×5 +1.7 = 3451.2 v5 = 3451.2×5 0.8 =17255.2

你从中看到了 怎样的规律？ 怎么用程序框 图来描述呢？

所以， 所以，当x = 5时，多项式的值等于 时 多项式的值等于17255.2

5

开始

程序框图：输入f(x)的系数： a0,a1,a2,a3,a4a5 输入x0

v0 = an vk = vk 1 x + an k (k = 1,2,L, n)这是一个在秦九韶算法中 这是一个在秦九韶算法中 反复执行的步骤， 反复执行的步骤，因此可 用循环结构来实现。 用循环结构来实现。

n=1 v=a5 n=n+1 v=vx0+a5-n n≤5?Y

N

输出v 结束

5

另解：(秦九韶算法的另一种直观算法) 多项式的系数

5

2 25

3.5 135

-2.6

1.7

-0.8

+X5

0 5

692.5 3449.5 17256

27 138.5 689.9 3451.2 17255.2

多项式的值

5

思考：你能设计程序把“秦九韶算法”表示出来吗？

(1)、算法步骤： 、算法步骤：第一步：输入多项式次数 、最高次项的系数a 第一步：输入多项式次数n、最高次项的系数 n和x 的值. 的值 第二步： v的值初始化为 的值初始化为a i的值初始化为 的值初始化为n-1. 第二步：将v的值初始化为an,将i的值初始化为n-1. 第三步：输入 次项的系数 次项的系数a 第三步：输入i次项的系数 n. 第四步： 第四步：v=vx+ai, i=i-1. 第五步：判断 是否大于或等于 是否大于或等于0,若是， 第五步：判断i是否大于或等于 ，若是，则返回第 三步；否则，输出多项式的值v。 三步；否则，输出多项式的值 。

5

(2)程序框图： )程序框图：

开始

输入n,a 输入 n,x V=an

i=n-1 i=i-1 v=vx+ai i>=0? N 输出v 输出 结束输入a 输入 i

Y

5

(3)程序： )程序：INPUT “n=”;n INPUT “an=“;a INPUT “x=“;x v=a i=n-1 WHILE i>=0 PRINT “i=“;i INPUT “ai=“;a v=v*x+a i=i-1 WEND PRINT v END

5

练习： 1、已知多项式f(x)=x5+5x4+10x3+10x2+5x+1 、已知多项式 时的值。 用秦九韶算法求这

个多项式当x=-2时的值。 秦九韶算法求这个多项式当 时的值 2、已知多项式f(x)=2x4-6x3-5x2+4x-6 、已知多项式 时的值。 用秦九韶算法求这个多项式当x=5时的值。 秦九韶算法求这个多项式当 时的值

5

课堂小结： 课堂小结：1、秦九韶算法的方法和步骤 、 2、秦九韶算法的程序框图 、

本文来源：https://www.bwwdw.com/article/59r4.html