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

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时的值。


相关文章:
1.3.2算法案例(秦九韶算法)[1]_图文
总场中学高中部有效课堂教学 总场中学高中部有效课堂教学 教学案 课 算法案例—秦九韶算法 题:1.3.2 算法案例 秦九韶算法 1.3.2 算法案例 秦九韶算法 算法...
1.3.2算法案例(第二课时)
第一章:算法案例§1.3 .2 秦九韶算法 (第 2 课时) 设计者:康宏、石双贵、王四海、陈军生、魏阳平、王长丽(集体备课教案) 教学目标: 【知识与技能】 了解...
1.3.2秦九韶算法 导学案
雅安中学 数学必修 3 第一章 1.3.2 算法案例秦九韶算法 § 1.3.2 算法案例 ———秦九韶算法班级: [中~国%教@* 育出 姓名: 学习目标 1.了解...
1.3算法案例-秦九韶算法教学设计
1.3算法案例-秦九韶算法教学设计_高一数学_数学_高中教育_教育专区。高中数学必修三,第一章1.3算法案例-秦九韶算法教学设计1.3 算法案例(二)__秦九韶算法 ...
9.§1.3.2算法案例—秦九韶算法
河北武邑中学教师课时教案备课人 课题 课标要求 教学目标 重点 难点 授课时间§ 1.3.2 算法案例秦九韶算法 1.了解秦九韶算法的计算过程,理解利用秦九韶算法...
1.3.1算法案例
1.3.2算法案例秦九韶算法... 1.3.3算法案例--进位制1/2 相关文档推荐 1.3算法案例 62页 2财富值 1.3算法案例 32页 2财富值 1.3算法案例 44页 ...
...§1.3算法案例(秦九韶算法)教案 新人教A版必修3
湖北省恩施巴东县第一高级中学高中数学 §1.3算法案例(秦九韶算法)教案 新人教A版必修3_数学_高中教育_教育专区。时 案例 2 秦九韶算法 (一)导入新课 思路 ...
§1.3.1算法案例2 一课一练
§​1​.​3​.​1​算​法​案​例​2​ ​一​课​一​练§1.3.1 算法案例 2 1、用秦九韶算法和直接算法求当 x ? x0 ...
高中数学 1.3算法案例---秦九韶算法同步测试 新人教版...
高中数学 1.3算法案例---秦九韶算法同步测试 新人教版必修3_数学_高中教育_教育专区。1.3 算法案例---秦九韶算法 3 2 1 、利用秦九韶算法求多项式 7 x...
第9课时-§1.3算法案例——秦九韶算法
北京师范大学(珠海)附属高级中学 2011 级 高二年级第学期(理科数学)备课组教案课题:§1.3 算法案例——秦九韶算法 教学目标: 知识与能力: 了解秦九韶算法的...
更多相关标签: