当前位置:首页 >> 销售/营销 >>

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


算 法 案 例
第二课时

新课讲解:
怎样求多项式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次加法运算。

《数书九章》——秦九韶算法
这是怎样 f ( x) ? an x ? an?1 x ? ? ? a1 x ? a0 的一种改 对该多项式按下面的方式进行改写: 写方式? 最后的结 n n ?1 f ( x) ? an x ? an?1 x ? ? ? a1 x ? a0 果是什么? ? (an x n?1 ? an?1 x n?2 ? ? ? a1 ) x ? a0
n n ?1

设 f ( x) 是一个n 次的多项式

? (( an x

n?2

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

? ??

? an?1 x

n ?3

? ? ? a2 ) 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 2 f ( x) ? 5x ? 2 x ? 3.5x ? 2.6 x ? 1.7 x ? 0.8 用秦九韶算法求这个多项式当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?

v=vx0+a5-n
N

Y 输出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 输入ai Y

i>=0? N 输出v
结束

(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、已知多项式f(x)=x5+5x4+10x3+10x2+5x+1

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

用秦九韶算法求这个多项式当x=5时的值。


相关文章:
高中数学必修3教学设计:1.3《算法案例---秦九韶算法》
〔教案〕 教学目标: 1.3 算法案例――-秦九韶算法 (1) 在学习中国古代数学中的算法案例的同时,进一步体会算法的 特点。 (2) 体会中国古代数学对世界数学发展...
高中数学人教版必修3 1.3算法案例 作业(系列二)
高中数学人教版必修3 1.3算法案例 作业(系列二) - 1.3 算法案例 辗转相除法与更相减损术、秦九韶算法 1.利用秦九韶算法求 f(x)=1+2x+3x +…+6x 当...
人教B版必修3高中数学1.3《算法案例 秦九韶算法》word...
四川省古蔺县中学高中数学必修三:1.3算法案例---秦九韶算法》 学案 学习目标: (1)在学习中国古代数学中的算法案例的同时,进一步体会算法的特点。 (2)体会...
社会主义核心价值观案例_秦九韶算法_陈娟兰
2. 教学设计片段:【案例】数学必修 3 第一章《算法初步》1.3 算法秦九韶算法教学设计(片段) 3 / 16 内容与内容解析 秦九韶算法是必修 3 呈现的三个算法...
...三天天练 §1.3.1算法案例2 Word版无答案]
2013-2014学年高一人教A版数学必修三天天练 §1.3.1算法案例2 Word版无答案]天天练 §1.3.1 算法案例 2 1、用秦九韶算法和直接算法求当 x ? x0 时 ...
山西省忻州市2016_2017学年高中数学第一章算法初步1.3算法案例...
山西省忻州市2016_2017学年高中数学第一章算法初步1.3算法案例预习案 - 1.3.1 辗转相除法、更相减损术与秦九韶算法 【教学目标】 1.知识与技能 (1)理解...
...人教A版高中数学必修三1.3《算法案例(秦九韶算法)》...
2016人教A版高中数学必修三1.3算法案例(秦九韶算法)》word教案 - 时 案例 2 秦九韶算法 (一)导入新课 思路 1(情境导入) 大家都喜欢吃苹果吧, 我们吃...
社会主义核心价值观案例-秦九韶算法-陈金宇_图文
社会主义核心价值观案例-秦九韶算法-陈金宇 - 社会主义核心价值观案例 秦九韶算法 课题名称 作者姓名 联系电话 数学必修 3 第一章 《算法初步》 1.3 算法 (“...
【数学】1.3《算法案例---秦九韶算法》教案(新人教A版...
(2) 体会中国古知识改变命运, 知识改变命运,学习成就未来 〔教案〕 教学目标: 1.3 算法案例――-秦九韶算法 (1) 在学习中国古代数学中的算法案例的同时, ...
秦九韶算法实验报告
算法案例(二)秦九韶算法 15页 1下载券 秦九韶算法习题 31下载券秦...《数值计算》实验报告学院:软件学院 实验名称 秦九昭算法 专业:软件工程 班级:...
更多相关标签: