9512.net
甜梦文库
当前位置:首页 >> 数学 >>

§1.3.1-2算法案例(二)



§1.3.1-2算法案例(二)

重庆市万州高级中学 曾国荣 wzzxzgr@163.com

§1.3.1-2算法案例(二)

学习目标
1.理解并掌握秦九韶算法的计算过程,了解利用秦 九韶算法可以减少计算次数提高效率的实质. 2.通过秦九韶算法,进一步算法的基本思想,了解其 算法程序框图和程序. 3.理解

数学算法与计算机算法的区别,理解计算机 对数学的辅助作用. 4.通过对秦九韶算法的学习,了解中国古代数学家 对数学的贡献,认识中国文化历史的悠久.

2013-8-15

重庆市万州高级中学 曾国荣 wzzxzgr@163.com

2

§1.3.1-2算法案例(二)

复习

1、求两个数的最大公约数的两种方法分别是( ( ).

)和

2、两个数21672,8127的最大公约数是( A、2709 B、2606 C、2703



D、2706

2013-8-15

重庆市万州高级中学 曾国荣 wzzxzgr@163.com

3

§1.3.1-2算法案例(二)

问题

怎样求多项式f(x)=x5+x4+x3+x2+x+1当x=5时的值?
算法1 f(5)=55+54+53+52+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次加法运算.
2013-8-15 重庆市万州高级中学 曾国荣 wzzxzgr@163.com 4

秦九韶算法

§1.3.1-2算法案例(二)

新课

《数书九章》——秦九韶算法
n( n ? 1) 次乘法运算 2

设 f (x) 是一个n 次的多项式
f ( x ) ? an x n ? an?1 x n?1 ? ? ? a1 x ? a0

n次加法运算

对该多项式按下面的方式进行改写
f ( x ) ? an x n ? an?1 x n?1 ? ? ? a1 x ? a0 ? (an x n?1 ? an?1 x n? 2 ? ? ? a1 ) x ? a0 ? ((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

2013-8-15

重庆市万州高级中学 曾国荣 wzzxzgr@163.com

5

§1.3.1-2算法案例(二)

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

要求多项式的值,应该先算最内层的一次多项式的值,即 v1 ? an x ? an?1 n次乘法运算 n次加法运算 然后,由内到外逐层计算一次多项式的值,即 这是一个在秦 九韶算法中反 复执行的步骤, 因此可用循环 结构来实现.
v2 ? v1 x ? an? 2 v 3 ? v 2 x ? an ? 3
? v0 ? an ? ? v k ? v k ?1 x ? an ? k ( k ? 1, 2,? , n)

?? vn ? vn?1 x ? a0

这种将求一个n次多项式f(x)的值转化成求n个一次 多项式的值的方法,称为秦九韶算法
2013-8-15 重庆市万州高级中学 曾国荣 wzzxzgr@163.com 6

§1.3.1-2算法案例(二)

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

算法步骤

? v0 ? an ? ? v k ? v k ?1 x ? an ? k ( k ? 1, 2,? , n)

第一步:输入多项式次数n、最高次项的系数an和x的值 第二步:将v的值初始化为an,将i的值初始化为n-1 第三步:输入i次项的系数ai v1 ? an x ? an?1 第四步:v=vx+ai,i=i-1. v2 ? v1 x ? an? 2 第五步:判断i是否大于或等于0,若是, v3 ? v2 x ? an? 3 则返回第三步;否则,输出多项式的值v. ??
vn ? vn?1 x ? a0

2013-8-15

重庆市万州高级中学 曾国荣 wzzxzgr@163.com

7

§1.3.1-2算法案例(二)

开始

程序框图
第一步:输入多项式次数n、最 高次项的系数an和x的值

输入n,an,x的值

v=an
i=n-1 i=i-1 v=vx+ai i≥0?
N Y

第二步:将v的值初始化为an, 将i的值初始化为n-1

第三步:输入i次项的系数ai
第四步:v=vx+ai,i=i-1.

第五步:判断i是否大于或等于 0,若是,则返回第三步;否则,输 出多项式的值v.

输入ai

输出v

结束
2013-8-15 重庆市万州高级中学 曾国荣 wzzxzgr@163.com 8

§1.3.1-2算法案例(二)

开始
输入n,an,x的值

程序
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
9

v=an
i=n-1 i=i-1 v=vx+ai i≥0?
N Y

输入ai

输出v

结束
2013-8-15

重庆市万州高级中学 曾国荣 wzzxzgr@163.com

§1.3.1-2算法案例(二)

例2 已知一个五次多项式为
f ( x ) ? 5 x 5 ? 2 x 4 ? 3.5 x 3 ? 2.6 x 2 ? 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时的值:
v2 ? 27 ? 5 ? 3.5 ? 138.5 v0 ? 5 v1 ? 5 ? 5 ? 2 ? 27 v4 ? 689.9 ? 5 ? 1.7 ? 3451.2 v3 ? 138.5 ? 5 ? 2.6 ? 689.9 v5 ? 3451.2 ? 5 ? 0.8 ? 17255.2 所以,x = f(5)=时17255.2

5 x=5

2 25

3.5

-2.6

1.7

-0.8 17256

135 692.5 3449.5

27 136.5 689.9 3451.2 17255.2
2013-8-15 重庆市万州高级中学 曾国荣 wzzxzgr@163.com 10

§1.3.1-2算法案例(二)

课堂练习 <<教材>> P.45

练习2

书面作业
<<教材>> P.48 习题1.3 A组2

2013-8-15

重庆市万州高级中学 曾国荣 wzzxzgr@163.com

11



更多相关文章:
...恩施巴东县第高级中学高中数学 §1.3算法案例(秦...
湖北省恩施巴东县第一高级中学高中数学 §1.3算法案例(秦九韶算法)教案 新...(二)推进新课、新知探究、提出问题 5 4 3 2 (1)求多项式 f(x)=x +x ...
算法初步 §1.3有详细答案
§ 1.3 算法案例 课时目标 通过三种算法案例:辗转相除法与更相减损术,秦九韶...第四步,若 r=0,则 m、n 的最大公约数等于 m;否则,返回第二步. 2.更...
...天天练 §1.3.1算法案例2 Word版无答案]
2013-2014学年高一人教A版数学必修三天天练 §1.3.1算法案例2 Word版无答案]_高中教育_教育专区。2013-2014学年高一人教A版数学必修三天天练 §1.3.1算法案...
1.3算法案例
§1.3 算法案例1 课时【学习目标】 1. 掌握辗转相除法的算法步骤。 2....二.学习交流: 1. 根据秦九韶算法能把多项式 f(x)=3x 5 +4x 4 +5x 3 ...
§ 13.3 算法案例
第13课时5.4.3算法案例三(... 2页 免费 13高一数学(1-3算法案例的... 8...二、疑难知识导析 1. 表示不超过 的整数部分,如 就是错误的,应为-2. ,但...
必修三《1.3 算法案例》学案3
§1.3 算法案例 3 授课 时间 学习 目标 重点 难点 第周 星期 第节 课型 ...常在设的右下角表明基数,如二进制数 10(2) ,七进制数 260(7) ,十进制数...
高一数学算法案例1
必修3 学案 § 1.3.1 算法案例(1) ☆学习目标:1°理解辗转相除法与更相...若是,用 2 约简;若不是,执 行第二步. (2) 以较大的数减去较小的数,...
算法案例教案
课题:§1.3 算法案例 第 1 课时 辗转相除法与更相减损术、秦九韶算法一、...(二)研探新知(1)怎样用短除法求最大公约数? (2)怎样用穷举法(也叫枚举...
高中数学必修3《1.3算法案例)》教案设计
高中数学必修3《1.3算法案例)》教案设计_数学_高中教育_教育专区。www.xkb1....给定两个正整数,判断它们是否都是偶数,若是,用 2 约简;若不是,执 行第二...
1.3算法案例教案
1.3算法案例教案_数学_高中教育_教育专区。考试指南报——课堂网(www.k45.cn...而表示各种进位制数一般在数字右下脚加注来表示 ,如 111001(2)表示二进制数,...
更多相关标签:
1.3算法案例    1.3算法案例教案    智能算法30个案例分析    算法案例ppt    算法案例    pagerank算法应用案例    遗传算法案例    决策树算法案例    

All rights reserved Powered by 甜梦文库 9512.net

copyright ©right 2010-2021。
甜梦文库内容来自网络,如有侵犯请联系客服。zhit325@126.com|网站地图