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


算 法 案 例 ----秦九韶算法

秦九韶(1208年-1261年)南宋官员、 数学家,与李冶、杨辉、朱世杰并称宋 元数学四大家。字道古,汉族,自称鲁 郡(今山东曲阜)人,生于普州安岳 (今属四川)。精研星象、音律、算术、 诗词、弓剑、营造之学,历任琼州知府、 司农丞,后遭贬,卒于梅州任所,著作 《数书九章》,其中的大衍求一术、三 斜求积术和秦九韶算法是具有世界意义 的重要贡献。

在数学的发展史上,从公元前2、 3世纪公元14世纪,中国的数学虽有 过高潮,也有过低落,但一直走在 世界的前列,是世界数学的中心。 中国古代数学对世界数学发展有着 不可磨灭的贡献。秦九韶算法就是 中国古代数学的一枝奇葩。 今天这节课我们领略秦九韶算 法的魅力。

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

2、两个数21672,8127的最大公约数是 (



A、2709

B、2606

C、2703

D、2706

新课讲解:

怎样求多项式f(x)=x5+x4+x3+x2+x+1当x=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: 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

算法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 =5×(5×(5×(5 ×(5 +1) +1 )+1)+1) +1
共做了4次乘法运算,5次加法运算。

思考:
(1)设计求多项式

f ( x) ? 2 x ? 5 x ? 4 x ? 3x ? 6 x ? 7
5 4 3 2

当x=5时的值的算法,并写出程序。 (2)有没有更高效的算法?能否探求更好的 算法,来解决任意多项式的求解问题?

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

f ( x) ? an x ? an?1 x
n n

n ?1

? ...... ? a1 x ? a0

对该多项式按下面的方式进行改写:

f ( x) ? an x ? an?1 x ? ...... ? a1 x ? a0 n ?1 n?2 ? (an x ? an?1 x ? ...... ? a1 ) x ? a0

n ?1

这是怎样 的一种改 写方式? 最后的结 果是什么?

? (( an x n ?2 ? an?1 x n ?3 ? ...... ? a2 ) x ? a1 ) x ? a0

? (......( an x ? an?1 ) x ? an?2 ) x ? ...... ? a1 ) x ? a0

? ......

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

v1 ? an x ? an?1

v2 ? v1 x ? an?2 v3 ? v2 x ? an?3 vn ? vn?1 x ? a0

......

最后的一 项是什么?

这种将求一个n次多项式f(x)的值转化成求n个一 次多项式的值的方法,称为秦九韶算法。

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

例: 已知一个五次多项式为
5 4 3

f ( x) ? 5x ? 2 x ? 3.5x ? 2.6 x ? 1.7 x ? 0.8
2

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

f ( x) ? (((( 5 x ? 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

开始

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

输入x0

?v 0 ? a n ? ?v k ? v k ?1 x ? an? k ( k ? 1,2,? , n)
这是一个在秦九韶算法中 反复执行的步骤,因此可 用循环结构来实现。

n=1

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

v=vx0+a5-n
N

输出v
结束

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

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

多项式的值

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

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

(2)程序框图:

开始

输入n,an,x

V=an

i=n-1 i=i-1

v=vx+ai
i>=0? N 输出v
输入ai

Y

结束

(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

课堂小结:
1、秦九韶算法的方法和步骤

2、秦九韶算法的程序框图

练习: P45 第2 题

作业:
P48 A组 2


相关文档

更多相关文档

1.3案例2秦九韶算法
1.3算法案例2(秦九韶算法)
1.3.2算法案例(2)秦九韶算法
1.3.2《算法案例-秦九韶算法》(整理)
1.3.2算法案例(秦九韶算法)[1]
1[1].3案例2秦九韶算法
1.3算法案例2秦九韶算法
1.3课时2算法案例秦九韶算法
1.3.2《算法案例---秦九韶算法》
1.3.2 算法案例-秦九韶算法 课件2
电脑版