当前位置:首页 >> 数学 >>

1.3 算法案例2


第一章
算法初步
1.3 算法案例

案例2 秦九韶算法

计算多项式f(x) =x5+x4+x3+x2+ x+1当x = 5的值 算法1: f(x) =x5+x4+x3+x2+x+1 =x ×x×x×x ×x + x × x×x ×x + x × x × x
+x×x+x+1
算法:


所以f(5)=55+54+53+52+5+1 =3125+625+125+25+5+1 = 3906 =((((x+1)x+1)x+1)x+1)x+1

f(x) =x5+x4+x3+x2+x+1
=(( ((5 +1 ) × 5 +1 ) ×5 +1 ) × 5+1 ) ×5 +1

f(5)

《数书九章》——秦九韶算法



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

f ( x) ? an xn ? an?1xn?1 ? ?? a1x ? a0
对该多项式按下面的方式进行改写:

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

n?1

? (an x

n?1

? an?1x

? ?? a1x ? a0
n ?2
n?3

? ?? a1 ) x ? a0
? ?? a2 ) x ? a1 ) x ? a0

? ((an x

n ?2

? ??

? an?1x

? (?(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 ? v 0 x ? an ?1

v0 ? an

v k ? v k?1x ? an ?k
最后的一项 是什么?

然后,由内到外逐层计算一次多项式的值,即

v2 ? v1 x ? an?2 v3 ? v2 x ? an?3

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

??

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

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

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

f ( x) ? ((((5x ? 2) x ? 3.5) x ? 2.6) x ? 1.7) x ? 0.8
v0 ? 5 v1 ? 5 ? 5 ? 2 ? 27 v2 ? 27? 5 ? 3.5 ? 138.5

按由里到外的顺序,依此计算一次多项式当x = 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

点评:秦九韶算法是求一元多项式的 值的一种方法. 它的特点是:把求一个n次多项式的值 转化为求n个一次多项式的值,通过n次乘 法运算和n次加法运算,大大提高了运算效 率.

课后活动
1、预习下一节内容。 2、完成《创新设计》“当堂检测”部分. 3、P48 1 2


相关文章:
1. 3 算法案例(二)_图文
3 算法案例() 1.了解各种进位制与十进制之间转换的规律; 2.学会各种进位制转换成十进制的计算方法,研究十进制转换为各种进位制 的除 k 取余法,并理解其中...
1.3算法案例
1.3算法案例_高二数学_数学_高中教育_教育专区。1.3 算法案例 1. 8251 与 6105 的最大公约数是( A.4 B.37 ) C.148 ) D.1 813 2.如图所示的程序...
1.3算法案例
试仿照书本第 37 页所给案例 2计算规律, 尝试利用更相减损术求出 72 与 168 的最大公 约数。 问 3.比较辗转相除法与更相减损术的区别 (1)都是求 ...
1.3_算法案例
三维目标 1.理解算法案例的算法步骤和程序框图. 2.引导学生得出自己设计的算法程序. 3. 体会算法的基本思想,提高逻辑思维能力,发展有条理地思考与数学表达能力. ...
1.3 算法案例
1.3 算法案例_数学_高中教育_教育专区。1.3 算法案例 . 课时安排 3 课时 提出问题 (1)怎样用短除法求最大公约数? (2)怎样用穷举法(也叫枚举法)求最大...
1.3.1 算法案例作业(二)
2011高三数学总复习第二讲 5页 免费如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈。 1.3.1 算法案例作业(二) 算法案例...
1.3算法案例
1.3 算法案例 第 1、2 课时 辗转相除法与更相减损术(1)教学目标 (a)知识与技能 1.理解辗转相除法与更相减损术中蕴含的数学原理,并能根据这些原理进行算法...
第1章 1.3 算法案例(2) 学案
第1章 1.3 算法案例(2) 学案_数学_高中教育_教育专区 暂无评价|0人阅读|0次下载|举报文档 第1章 1.3 算法案例(2) 学案_数学_高中教育_教育专区。1.3 ...
1.3 算法案例 教学设计2
人教A 版高中数学必修三第一章教学 课题 课程 类型 课时 《算法案例 》教学设计 2 1.3.2 秦九韶算法新授课 一课时 教学 重点 1.秦九韶算法的特点 2.两种...
高中数学必修三1.3算法案例
4、写出从键盘任意输入两个正整数 a,b,输出这两个数的最小公倍数的算法,画出程序框图,写出 算法语句. 1.3算法案例 2——秦九韶算法》导学案【学习目标...
更多相关标签:
1.3算法案例 | 1.3算法案例 教案 | 1 1 2 3 5 8递归算法 | 1 5 3 6 4 5简便算法 | 算法导论16.1 3 | 智能算法30个案例分析 | pagerank算法应用案例 | 算法案例ppt |