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

算法案例(第二课时)ppt


算 法 案 例
(第二课时)

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

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



案例2、秦九韶算法

怎样求多项式f(x)=x5+x4+x3+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、 品读语言文字, ...(PPT 出示:给予是一种快乐!) 2、体会“给予”,感受“子爱父”。(1)学习第...

...1.1.2 程序框图与算法的基本逻辑结构(第二课时)。do...

搜试试 3 帮助 全部 DOC PPT TXT PDF XLS 百度文库 教育专区 高中教育 数学 高一数学于美霖-1.1.2 程序框图与算法的基本逻辑结构(第二课时)。doc_高一数学...

《海底世界》第二课时教学设计

《海底世界》第二课时教学设计_其它技巧_PPT制作技巧_PPT专区。《海底世界》第二...(1.颜色,什么颜色,省略号又告诉我们什么?2.形态,课文举了什么例子来说的? ...

冲刺2011质量守恒定律第二课时PPT化学方程式1

冲刺2011质量守恒定律第二课时PPT化学方程式1 隐藏>> 化学方程式第一至第五单元 1) 2) 3) C+O2 2C+O2 S+O2 CO2(O2 充足) 2CO(O2 不充足) SO2 是淡...

《算法分析与设计》教学中PPT课件的设计制作

算法分析与设计》教学中PPT课件的设计制作_教学案例/设计_教学研究_教育专区。《算法分析与设计》教学中 PPT 课件的设计制作 摘要:PPT 作为多媒体课件制作工具已...

小鹰学飞第二课时教学设计

小鹰学飞第二课时教学设计_教学案例/设计_教学研究_教育专区。《小鹰学飞》第...(PPT 出示: “小鹰只好鼓起劲,跟着老鹰拼命向上飞。飞呀,飞呀, 大树看不见...

10.《九寨沟(第二课时)教案

10.《九寨沟(第二课时)教案_语文_小学教育_教育专区。10.《九寨沟》 (第二课时...(一)PPT 出示自学要求 1、用你喜爱的方式读第三自然段,找找写了哪几 种...

气温的变化和分布(第二课时)

气温的变化和分布(第二课时)_政史地_初中教育_教育专区。《气温的变化与分布...1.PPT 投影相关案例。 律 1.学生分析。 通过案例,更能加深学 生对气温垂直...

《风娃娃》教学设计(第二课时)

《风娃娃》教学设计(第二课时)_教学案例/设计_教学研究_教育专区。《风娃娃》...PPT:第二幅图 么做的?结果又怎么样? (2)读读课文,把你的感受读出来。 ...

第二课时 分数除以整数

教具准备: PPT 课件学具准备:3 张 32 开长方形纸 教学过程: 一、复习导入...五、课后作业 板书设计: 算法一 4/5÷2=4÷2/5=2/5 算法二 4/5÷2=...
更多相关标签:
网站地图

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