当前位置:首页 >> 数学 >> 算法案例(第二课时)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、秦九韶算法的程序框图


更多相关文档:

算法课堂PPT

算法实例课堂PPT 21页 10财富值 秦九韶算法课堂教学PPT 20页 5财富值 Java类...《算法与程序设计》课堂 PPT 第 1 页共 28 页 《算法与程序设计》课堂 PPT...

《桂林山水》(第二课时)教学设计——王天权

桂林山水第二课时教学设... 2页 免费 《桂林山水》教学案例(王... 14页 免费 《桂林山水》第二课时教... 5页 免费 桂林山水PPT课件02 35页 1下载券《...

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

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

《1老师您好》第二课时教案

《1老师您好》第二课时教案_动画/交互技巧_PPT制作技巧_PPT专区。临泽镇中心小学课堂教学设计 授课时间:2010 年月日 课题 老师,您好! 1.老师,您好!董大春复备人...

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

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

和时间赛跑 第二课时教学设计

和时间赛跑 第二课时教学设计_教学案例/设计_教学研究_教育专区。和时间赛跑 第...9.PPT 出示中心句“所有时间里的事物,都永远不会回来。 ” 所以作者会说??...

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

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

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

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

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

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

ppt上机操作题及答案

② 建立页面二:版式为“只有标题”; 标题内容为“...将第一张幻灯片的切换方式设置为中速“垂直百叶窗”...“3、 乘、除法的一些简便算法”——选中文字(或...
更多相关标签:
网站地图

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