当前位置:首页 >> 理学 >>

秦九韶算法介绍和实例分析


算 法 案 例
第二课时

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

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



新课讲解:
怎样求多项式f(x)=x +x+1当x=5时的值呢 时的值呢? 怎样求多项式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: 算法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 × × × 1 1 1 1 =5×(5×(5×(5 ×(5 +1) +1 )+1)+1) +1 × × × 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 × × × 1 1 1 1 =5×(5×(5×(5 ×(5 +1) +1 )+1)+1) +1 × × × 1 1 1 1 1
共做了4次乘法运算, 次加法运算 次加法运算。 共做了 次乘法运算,5次加法运算。 次乘法运算

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

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

=L L

= ((anxn?2 +an?1xn?3 +L a2)x +a )x +a0 + 1
=(L anx+an?1)x+an?2)x+L a )x+a0 ( + 1

f (x) =(L anx+an?1)x+an?2)x+L a )x+a0 ( + 1
要求多项式的值,应该先算最内层的一次多项式的值, 要求多项式的值,应该先算最内层的一次多项式的值,即 然后,由内到外逐层计算一次多项式的值, 然后,由内到外逐层计算一次多项式的值,即

v = anx+an?1 1

v2 =v x+an?2 1

L L

v3 =v2x+an?3

最后的一 项是什么? 项是什么?

vn =vn?1x+a0

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

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

例: 已知一个五次多项式为

f (x) =5x5 +2x4 +3.5x3 ?2.6x2 +1.7x?0.8

用秦九韶算法求这个多项式当x 的值。 用秦九韶算法求这个多项式当 = 5的值。 的值 解: 将多项式变形: 将多项式变形:

f (x) = ((((5x+2)x+3.5)x ?2.6)x+1.7)x?0.8

按由里到外的顺序,依此计算一次多项式当 时的值: 按由里到外的顺序,依此计算一次多项式当x = 5时的值: 时的值

v0 =5 v =5×5+2 =27 1 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

?v0 = an ? , , ?vk = vk?1x +an?k (k =12,L n)
这是一个在秦九韶算法中 这是一个在秦九韶算法中 反复执行的步骤, 反复执行的步骤,因此可 用循环结构来实现。 用循环结构来实现。

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

N

输出v 结束

另解:(秦九韶算法的另一种直观算法) 多项式的系数

5

2 25

3.5 135

-2.6

1.7

-0.8

+
X5

0 5

692.5 3449.5 17256

27 138.5 689.9 3451.2 17255.2

多项式的值

思考:你能设计程序把“秦九韶算法”表示出来
吗?

(1)、算法步骤: 、算法步骤:
第一步:输入多项式次数 、最高次项的系数a 第一步:输入多项式次数n、最高次项的系数 n和x 的值. 的值 第二步: v的值初始化为 的值初始化为a i的值初始化为 的值初始化为n-1. 第二步:将v的值初始化为an,将i的值初始化为n-1. 第三步:输入 次项的系数 次项的系数a 第三步:输入i次项的系数 n. 第四步: 第四步:v=vx+ai, i=i-1. 第五步:判断 是否大于或等于 是否大于或等于0,若是, 第五步:判断i是否大于或等于 ,若是,则返回第 三步;否则,输出多项式的值v。 三步;否则,输出多项式的值 。

(2)程序框图: )程序框图:

开始

输入n,a 输入 n,x V=an

i=n-1 i=i-1 v=vx+ai i>=0? N 输出v 输出 结束
输入a 输入 i

Y

(3)程序: )程序:
INPUT “n=”;n INPUT “an=“;a INPUT “x=“;x v=a i=n-1 WHILE i>=0 PRINT “i=“;i INPUT “ai=“;a v=v*x+a i=i-1 WEND PRINT v END

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

课堂小结: 课堂小结:
1、秦九韶算法的方法和步骤 、 2、秦九韶算法的程序框图 、


相关文章:
秦九韶算法公开课教案
教学课题 授课年级 授课类型知识技 知识技 1.3 算法案例——秦九韶算法 ...算方法 学流 介绍秦九韶算法, 介绍秦九韶算法,求一般多项式的值 程用循环结构...
2017九年级数学秦九韶算法与排序2.doc
2017九年级数学秦九韶算法与排序2.doc_数学_初中教育_教育专区。§1.3 秦九...分析:先画出程序框图(见课本) 排序 排序的算法很多,课本主要介绍里两种排序方法...
1.3.2算法案例(秦九韶算法)[1]_图文
3.让学生明确秦九韶算法的作用和意义。 4.通过交流关于秦九韶的简介,突破本...对数学进行虔心钻研,并广泛搜集历学、数学、星象、音律、营造等资料,进行分析、...
数值分析matlab程序实例
数值分析matlab程序实例_数学_自然科学_专业资料 暂无评价|0人阅读|0次下载|举报文档数值分析matlab程序实例_数学_自然科学_专业资料。1,秦九韶算法,求出 P(x=3...
2017年普通高考数学科一轮复习精品学案 第17讲 基本案例
案例一.课标要求:通过阅读中国古代数学中的算法案例,...vn=vn-1x+a0 观察秦九韶算法的数学模型,计算 vk...3.排序 排序的算法很多,课本主要介绍里两种排序方法...
...中提出的多项式求值的秦九韶算法,至今仍_答案_百度高考...
8.秦九韶是我国南宋时期的数学家,普州(现四川省安岳县)人,他在所著的《数书九章》中提出的多项式求值的秦九韶算法,至今仍是比较先进的算法。如图所示的程序...
第一章“算法初步” 简介
数学中,中学生能够很容易理解的内容还有熟知 的割圆术、多项式求值的秦九韶算法...算法案例的处理也 遵循了这一原则,重在对案例的算法的分析,案例的选择也 主要...
更多相关标签: