当前位置:首页 >> 数学 >> 算法案例(第二课时)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.2算法案例(第二课时)

教案课件教案课件隐藏>> 第一章:算法案例§1.3 .2 秦九韶算法 (第 2 课时) 设计者:康宏、石双贵、王四海、陈军生、魏阳平、王长丽(集体备课教案) 教学目标...

1.3算法案例(第2课时)

(必修三)1.3.2算法案例(第... 15页 免费 高中数学必修三课件1.3算法... 18页 1财富值如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议...

算法案例2

搜 试试 帮助 全部 DOC PPT TXT PDF XLS 百度文库 教育专区 高中教育 数学 ...1.1 算法案例分析(第二课时)一、教学目标: (一)知识目标: 1、体会二分法的...

1.3算法案例(二)

搜试试 3 帮助 全部 DOC PPT TXT PDF XLS 广告 百度文库 教育专区 高中...1.3算法案例(二)_数学_高中教育_教育专区。高二数学教学设计教师 刘艳娟、...

1.3算法案例(2)

搜 试试 帮助 全部 DOC PPT TXT PDF XLS 百度文库 教育专区 高中教育 数学 ...1/2 相关文档推荐 1.3.2算法案例 19页 免费 1.3.2算法案例(第二课时) ...

算法案例

搜 试试 帮助 全部 DOC PPT TXT PDF XLS 百度文库 专业资料 人文社科 教育...算法案例2 暂无评价 17页 免费 算法案例(第课时) 暂无评价 9页 免费 算法...

算法案例

搜 试试 帮助 全部 DOC PPT TXT PDF XLS 百度文库 教育专区 高中教育 数学 ...算法案例2 暂无评价 17页 免费 算法案例(第课时) 暂无评价 9页 免费 算法...

1.3算法案例(第1课时)

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

算法案例

搜 试试 帮助 全部 DOC PPT TXT PDF XLS 百度文库 教育专区 高中教育 数学 ...2财富值 算法案例(2) 暂无评价 4页 免费 算法案例(第二课时) 暂无评价 21页...
更多相关标签:
算法案例ppt | 1.3算法案例ppt | 军神第二课时ppt | 九色鹿第二课时ppt | 石榴第二课时ppt | 航天飞机第二课时ppt | 小露珠第二课时ppt | 石头书第二课时ppt |
网站地图

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