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

搜 试试 帮助 全部 DOC PPT TXT PDF XLS 百度文库 教育专区 高等教育 法学...1.3 学习目标: 算法案例(第二课时)周金顺 平塘民族中学高二年级 1、了解各种...

高中数学1.4算法案例第2课时课堂探究素材

搜试试 3 悬赏文档 全部 DOC PPT TXT PDF XLS 广告 百度文库 教育专区 ...高中数学1.4算法案例第2课时课堂探究素材_数学_高中教育_教育专区。算法案例(第 ...

算法案例教案

搜 试试 7 帮助 全部 DOC PPT TXT PDF XLS ...课题:§1.3 算法案例 第 1 课时 辗转相除法与更...(2)上面问题有没有更有效的算法呢?我国南宋时期的...

《1.4算法案例(2)》教案

搜试试 3 悬赏文档 全部 DOC PPT TXT PDF XLS ...《1.4算法案例(2)》教案_高一数学_数学_高中教育_...这就是我们这一堂课所要探讨的内容. 二、建构教学...

k5第11课时—算法案例(2)

搜 试试 帮助 全部 DOC PPT TXT PDF XLS 百度文库 教育专区 初中教育 数学 ...;必修三 第 1 章 算法初步——算法案例(2) 知识就是力量 第三步: r1 ? ...

§1.3 算法案例(2)

搜试试 7 悬赏文档 全部 DOC PPT TXT PDF XLS ...§1.3 算法案例(2)_金融/投资_经管营销_专业资料...第周 星期 第 9 节 课型 新授课 主备课人 ...

算法案例练习(一)

搜 试试 7 帮助 全部 DOC PPT TXT PDF XLS 百度文库 教育专区 高中教育 ...算法案例练习(一)一、选择题(题型注释) 1.十进制数 25 转化为二进制数为( ...

1.3_算法案例

搜试试 3 帮助 全部 DOC PPT TXT PDF XLS ...三维目标 1.理解算法案例的算法步骤和程序框图. 2....课时安排 3 课时 教学过程 第 1 课时 案例 1 ...

1.3算法案例(第1课时)

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

《算法案例(1)》教学设计

搜 试试 7 帮助 全部 DOC PPT TXT PDF XLS ...《算法案例(1)》教学设计_其它课程_高中教育_教育专区...介绍中国古代算法的案例-韩信点兵-孙子问题; (2)用...
更多相关标签:
网站地图

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