当前位置:首页 >> 数学 >> 算法案例(第二课时)ppt

算法案例(第二课时)ppt


算 法 案 例
(第二课时)

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

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



案例2、秦九韶算法

怎样求多项式f(x)=x5+x4+x

3+x2+x+1当x=5时的值呢?

计算多项式f(x) =x5+x4+x3+x2+x+1当x = 5的值 算法1: f(x) =x5+x4+x3+x2+x+1 因为 所以f(5)=55+54+53+52+5+1 =3125+625+125+25+5+1 = 3906 算法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

算法1: 因为f(x) =x5+x4+x3+x2+x+1 所以f(5)=55+54+53+52+5+1
=3125+625+125+25+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次加法运算。

《数书九章》——秦九韶算法 设 f (x) 是一个n 次的多项式
n n ?1

这是怎样的 f ( x) ? an x ? an ?1 x ? ? ? a1 x ? a0 一种改写方 对该多项式按下面的方式进行改写: 式?最后的 结果是什么? n n ?1
f ( x) ? an x ? an ?1 x
? (an x
n ?1

? ? ? a1 x ? a0

? an ?1 x

n?2

? ? ? a1 ) x ? a0
n ?3

? ??

? (( an x

n?2

? an ?1 x

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

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

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

要求多项式的值,应该先算最内层的一次多项式的值,即 然后,由内到外逐层计算一次多项式的值,即
v2 ? v1 x ? an ?2 v3 ? v2 x ? an ?3
最后的一 项是什么?

v1 ? an x ? an ?1

??
vn ? vn ?1 x ? a0

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

算法步骤:
第一步:输入多项式次数n、最高次项的系数an和x 的值. 第二步:将v的值初始化为an,将i的值初始化为1. 第三步:输入i次项的系数an-i. 第四步:v=vx+an-i,i=i+1.

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

程序框图:
?v 0 ? a n ? ?v k ? v k ?1 x ? a n? k ( k ? 1,2, ? , n)

开始
输入n,an,x

V=an

i=1 i=i+1

这是一个在秦九韶算法中 反复执行的步骤,因此可 用循环结构来实现。

v=vx+an-i
输入an-i

i<=n? N 输出v 结束

Y

特点:通过一次式的反复计算,逐步得出高次多 项式的值,对于一个n次多项式,只需做n次乘 法和n次加法即可。

例2 已知一个五次多项式为
f ( x) ? 5 x ? 2 x ? 3.5 x ? 2.6 x ? 1.7 x ? 0.8
5 4 3 2

用秦九韶算法求这个多项式当x = 5的值。 解: 将多项式变形:
f ( x) ? (((( 5 x ? 2) x ? 3.5) x ? 2.6) x ? 1.7) x ? 0.8

按由里到外的顺序,依此计算一次多项式当x = 5时的值:
v0 ? 5
v1 ? 5 ? 5 ? 2 ? 27 v2 ? 27 ? 5 ? 3.5 ? 138.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

开始

程序框图:
输入f(x)的系数: a0,a1,a2,a3,a4a5

输入x0

?v 0 ? a n ? ?v k ? v k ?1 x ? a n? k ( k ? 1,2, ? , n)

n=1

v=a5
n=n+1 n≤5?
Y

这是一个在秦九韶算法中 反复执行的步骤,因此可 用循环结构来实现。

v=vx0+a5-n
N

输出v
结束

练习、已知多项式f(x)=x5+5x4+10x3+10x2+5x+1
用秦九韶算法求这个多项式当x=-2时的值。

课堂小结:
1、秦九韶算法的方法和步骤

2、秦九韶算法的程序框图


更多相关文档:

《1.3 算法案例》第二课时

搜 试试 7 帮助 全部 DOC PPT TXT PDF XLS 百度文库 教育专区 小学教育 ...《1.2 基本算法语句》第... 《1.3 算法案例》第一课...1...

1.3 算法案例 教学设计2

人教A 版高中数学必修三第一章教学 课题 课程 类型 课时算法案例 》教学设计 2 1.3.2 秦九韶算法新授课 一课时 教学 重点 1.秦九韶算法的特点 2.两种...

1.3算法案例(第1课时)

搜 试试 7 帮助 全部 DOC PPT TXT PDF XLS ...1.3 算法案例(第 1 课时) 学习目标:1.了解什么...减损术,并学会编写辗转相除法的程 序框图及程序;2...

第09课时 算法案例

r ,转 S 2 ; S 6 输出 b . 【流程图】 【伪代码】 2 江苏省泗阳中学...算法案例(第课时)课件 12页 免费 算法案例(第三课时) 12页 1下载券 算法...

算法案例(1)

搜 试试 7 帮助 全部 DOC PPT TXT PDF XLS 百度文库 教育专区 高中教育 ...1.3.2算法案例(第二课时... 14页 免费 1.3算法案例 62页 1下载券 1.4算法...

第2课时 案例2 秦九韶算法

搜 试试 7 帮助 全部 DOC PPT TXT PDF XLS 百度文库 教育专区 高中教育 ...第2课时 案例2 秦九韶算法_高一数学_数学_高中教育_教育专区。第 2 课时 案例...

1.3算法案例教案

搜试试 3 帮助 全部 DOC PPT TXT PDF XLS 百度文库 教育专区 高中教育 数学...辗转相除法 更相减损术 算法案例 (第二课时) 教学目标 掌握秦九韶算法、进位...

1.3算法案例(3)

搜 试试 7 帮助 全部 DOC PPT TXT PDF XLS 百度文库 教育专区 高中教育 ...1.3 算法案例(3) 数学组: 时间: 课型:新授课 教学目标 1.知识目标 2....

第1章 1.3 算法案例(2) 学案

搜 试试 7 帮助 全部 DOC PPT TXT PDF XLS 百度文库 教育专区 高中教育 ...第1章 1.3 算法案例(2) 学案_数学_高中教育_教育专区。1.3 明目标、知重点...

第二课 算法与流程图

课题 第二算法与流程图 1、通过流程图实例分析...讲授法 1 课时 教师活动 学生活动 设计意图 目标 ...2、识记图形 Ppt 展示图形,请同学连线。 三、画...
更多相关标签:
算法案例ppt | 七颗钻石第二课时ppt | 番茄太阳第二课时ppt | 爱如茉莉第二课时ppt | 荷花第二课时ppt | 赶海第二课时ppt | 水上飞机第二课时ppt | 鸟语第二课时ppt |
网站地图

文档资料共享网 nexoncn.com copyright ©right 2010-2020。
文档资料共享网内容来自网络,如有侵犯请联系客服。email:zhit325@126.com