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.2算法案例
必修三1.3.2算法案例_数学_高中教育_教育专区。教师姓名 课题 胡柱石、汤玉龙...韶算法是南宋数学家秦九韶首先提出的求 的高效算法 二、探究新知: 例 1 用...
§1.3 算法案例(1)
2.基 §1.3 算法案例(1)授课 时间 学习 目标 重点 难点 第周 星期 第 8...二、 【对学、群学】 1、对子之间交流、统一答案,把不会的内容用红笔标注,...
必修§3-2 算法案例
必修三第一章§3-2 算法案例_数学_高中教育_教育专区。必修三 第一章 §3-...(1)把十进制数 168 化为八进制数; (2)把五进制数 33(5)化为二进制数。...
§1.3.1中国古代数学中的算法案例
鹿邑二高导学案班级 姓名 小组 高一年级数学学科 编写人:紫气东来审核人:备课组长签字: 课题:§1.3.1 中国古代数学中的算法案例 课时:2 本期总课时:9 I、 ...
1.3算法案例
1.3算法案例⑶_数学_高中教育_教育专区。§1.3 算法案例、三维目标 (...第步,计算 v1=anx+an-1. 第二步,计算 v2=v1x+an-2. 第三步,计算...
1.3.2算法案例(第二课时)
章:算法案例§1.3 .2 秦九韶算法 (第 2 课时) 设计者:康宏、石双贵、王四海、陈军生、魏阳平、王长丽(集体备课教案) 教学目标: 【知识与技能】 了解...
§1.3.1算法案例3 一课一练
§1.3.1 算法案例 3 1、把七进制数 235 化为十进制数为( A、124 B、...7 、下图是把二进制数 111 ( 2 ) 化成十进制数的一个程序框图,则判断框...
9.§1.3.2算法案例—秦九韶算法
教师课时教案备课人 课题 课标要求 教学目标 重点 难点 授课时间§ 1.3.2 算法案例—秦九韶算法 1.了解秦九韶算法的计算过程,理解利用秦九韶算法减少计算次数...
高中数学必修三_1.3算法案例
关键词:算法案例 1/2 同系列文档 高中数学必修_1.1.1算法... 高中数学必修...二.新知导学 问题 1:阅读辗转除法和更相减损术,它的作用是什么?体会它的实...
1.3算法案例(2)
08算法案例学案 暂无评价 4页 免费如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈。 1.3算法案例(2) 隐藏>> 1.3 算法...
更多相关标签:

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

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