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

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算法案例(2)
08算法案例学案 暂无评价 4页 免费如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈。 1.3算法案例(2) 隐藏>> 1.3 算法...
1.3算法案例2
3页 免费如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈。 1.3算法案例2 隐藏>> 2. 秦九韶算法与排序 (1)教学目标 ...
高中数学必修三1.3算法案例
4、写出从键盘任意输入两个正整数 a,b,输出这两个数的最小公倍数的算法,画出程序框图,写出 算法语句. 1.3算法案例 2——秦九韶算法》导学案【学习目标...
§1.3.1算法案例2 一课一练
§​1​.​3​.​1​算​法​案​例​2​ ​一​课​一​练§1.3.1 算法案例 2 1、用秦九韶算法和直接算法求当 x ? x0 ...
1.3算法案例
1.3 算法案例 第 1、2 课时 辗转相除法与更相减损术(1)教学目标 (a)知识与技能 1.理解辗转相除法与更相减损术中蕴含的数学原理,并能根据这些原理进行算法...
1.3 算法案例
1.3 算法案例_数学_高中教育_教育专区。1.3 算法案例 . 课时安排 3 课时 提出问题 (1)怎样用短除法求最大公约数? (2)怎样用穷举法(也叫枚举法)求最大...
高中数学必修3《1.3算法案例)》教案设计
三维目标 1.理解算法案例的算法步骤 和程序框图. 2.引导学生得出自己设计的算法程序. 3. 体会算法的基本思想,提高逻辑思维能力,发展有条理地思考与数学表达能力. ...
1.3算法案例
1. 3 算法案例 (讲) 在初中,我们已经学过求最大公约数的知识,你能求出 ...例 2 用更相减损术求 98 与 63 的最大公约数. 解:由于 63 不是偶数,把...
1.3算法案例
算法案例型: 新授课 名: 审核人: 使用日期: 刘小颖 、标学装 (1)理解...2)理解秦九韶算法的特点,并能利用秦九韶算法计算元 n 次多项式的值; (3...
更多相关标签:
1.3算法案例 | 1.3算法案例教案 | 1 1 2 3 5 8递归算法 | 算法导论 24.1 3 | 算法导论22.1 3 | 算法导论19.3 1 | 算法导论 33.1 3 | 算法导论30.1 3 |