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中国古代数学中的算法案例
鹿邑二高导学案班级 姓名 小组 高一年级数学学科 编写人:紫气东来审核人:备课组长签字: 课题:§1.3.1 中国古代数学中的算法案例 课时:2 本期总课时:9 I、 ...
§1.3.1算法案例3 一课一练
§1.3.1 算法案例 3 1、把七进制数 235 化为十进制数为( A、124 B、...7 、下图是把二进制数 111 ( 2 ) 化成十进制数的一个程序框图,则判断框...
§1.3 算法案例
1.3.1算法案例一 13页 1财富值 1.3算法案例(三) 2页 1财富值 1.3.1...二、讲授新课 (一)辗转相除法与更相减损术 1.短除法 求两个正整数的最大...
1.3算法案例(2)
08算法案例学案 暂无评价 4页 免费如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈。 1.3算法案例(2) 隐藏>> 1.3 算法...
9.§1.3.2算法案例—秦九韶算法
教师课时教案备课人 课题 课标要求 教学目标 重点 难点 授课时间§ 1.3.2 算法案例—秦九韶算法 1.了解秦九韶算法的计算过程,理解利用秦九韶算法减少计算次数...
1.3.2算法案例(第二课时)
章:算法案例§1.3 .2 秦九韶算法 (第 2 课时) 设计者:康宏、石双贵、王四海、陈军生、魏阳平、王长丽(集体备课教案) 教学目标: 【知识与技能】 了解...
1. 3 算法案例(二)_图文
3 算法案例(二) 1.了解各种进位制与十进制之间转换的规律; 2.学会各种进位制转换成十进制的计算方法,研究十进制转换为各种进位制 的除 k 取余法,并理解其中...
高中数学必修三_1.3算法案例
关键词:算法案例 1/2 同系列文档 高中数学必修_1.1.1算法... 高中数学必修...二.新知导学 问题 1:阅读辗转除法和更相减损术,它的作用是什么?体会它的实...
1.3算法案例
2014 年 5 月 §1.3 算法案例学习目标:理解算法案例的算法步骤和程序框图;...解: (1)辗转相除法 第一步, 第二步, 第三步, 因此, (2)更相减损术 ...
1.3_算法案例
1.3_算法案例_高一数学_数学_高中教育_教育专区。1.3 算法案例 教学分析 在...给定两个正整数,判断它们是否都是偶数,若是,用 2 约简;若不是,执 行第二...
更多相关标签:
1.3算法案例    智能算法30个案例分析    算法案例    算法案例ppt    pagerank算法应用案例    遗传算法案例    算法案例教案    决策树算法案例    

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

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