1.3.1（2）算法案例
图片预览
文档简介
课件17张PPT。 求多项式 f(x)=5x5+4x4+3x3+2x2+x+1当时的值，
并统计所做的计算的种类及计算次数。 一个自然的做法是把5代入多项式 f（x）,这样共需做( )次乘法运算( )次加法计算. 14 5 计算x的幂时，可以利用前面的计算结果，以
减少计算量，即先计算x2，然后依次计算，(x2·x)， (x2·x)·x，((x2·x)·x)·x的值,这样共需做( )次乘法运算( )次加法计算.8 5 思考：能否探索更好的算法，解决任意多项式的求值问题？55 显然这种算法与前两种相比，乘法的运算次
数减少了，因而能提高运算效率，而且对于计算
机来说，做一次乘法所需的运算时间比做一次加
法要长得多，因此这种做法能更快地得到结果.这
种算法就叫秦九韶算法. 秦九韶简介：秦九韶（公元1202-12
61年）南宋，数学家。他在1247年（淳
佑七年）着成《数书九章》十八卷．全
书共81道题，为九大类：大衍类、天时
类、田域类、测望类、赋役类、钱谷类
、营建类、军旅类、市易类。这是一部
划时代的巨著，它总结了前人在开中所
使用的列筹方法，将其整齐而有系统地
应用到高次方程的有理或无理根的求解上去，其中对“
大衍求一术”（一次同余组解法）和“正负开方术”（高
次方程的数值解法）等有十分深入的研究。其中的“大
衍求一术”（一次同余组解法），在世界数学史上占有
崇高的地位. 在古代《孙子算经》中载有“物不知数”这个问题，举例说明：有一数，三三数之余二，五五
数之余二，七七数之余二，问此数为何？这一类问题
的解法可以推广成解一次同余式组的一般方法．奏九
韶给出了理论上的证明，并将它定名为” 大衍求一术
”.这节课我们主要研究的是秦九韶算法中的一种. 即
利用秦九韶算法求一般多项式时值. 尽管秦九韶算法
是距今700多年前提出的，但现在仍是多项式求值的比
较先进的算法；秦九韶是享誉世界的数学家，美国当
代数学史家萨顿（G.Sarton）说，秦九韶是” 他那个
时代、并且确实也是所有时代最伟大的数学家之一！
例1 已知一个5次多项式为f(x)=5x5+2x4+3.5x32.6
x2+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; 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。 思考：例1计算时需要多少次乘法计算？多少
次加法计算？5次乘法计算和5次加法计算 练习：
用秦九韶算法计算x=3时,多项式 f(x)=7x7+
6x6+5x5+4x4+3x3+2x2+x的值, 并统计需要多少次
乘法计算和多少次加法计算？f(3)=21324,7次乘法计算和6次加法计算 思考:怎样用秦九韶算法求一般多项式 f（x）
=anxn+an-1xn-1+an-2xn-2+…+a1x+a0当x=x0(x0是任意
的实数)时的值? 利用秦九韶算法把一个n次多项式f(x)=anxn+
an-1xn-1+an-2xn-2+…+a1x+a0 改写成如下形式：f(x)=anxn+an-1xn-1+an-2xn-2+…+a1x+a0
=(anxn-1+an-1xn-2+an-2xn-3+…a1)x+a0
=((anxn-2+an-1xn-3+…+a2)x+a1)x+a0
=……………
=(…((anx+an-1)x+an-2)x+…+a1)+a0 这样就把n次多项式的求值问题转化成求n个
一次多项式的值的问题即求
v1=anx+an-1,
v2=v1x+an-2,
v3=v2x+an-3,
……
vn=vn-1x+a0,的值得过程.思考:
（1）在利用秦九韶算法计算n次多项式当时需要
多少次乘法计算和多少次加法计算？ 至多n次乘法运算和至多n次加法运算 （2）你能把秦九韶算法编成一个计算机程序吗? 首先我们来分析秦九韶算法的算理: 观察上述秦九韶算法中的n个一次式，可见vk
的计算要用vk-1到的值.若令v0=an,我们可以得到下
面的公式:这是一个在秦九韶算法中反复执行的步骤,因此可
用循环结构设计出算法.
第一步，输入多项式次数n、最高次项的系
数an和x的值. 第二步，将v的值初始化为an，将i的值初始
化为n-1.第三步，输入i 次项的系数ai.第四步，v=vx+ai，i=i-1. 第五步，判断i是否大于或等于0.若是，则返
回第三步；否则，输出多项式的值v.算法分析：否是程序框图：程序： 例2 用秦九韶算法计算多项 f(x)=8x7+5x6+3x4+
2x+1当x=2时的值.并指出计算多项式需要进行的乘法
运算和加法运算次数. 分析：注意本题中有几项不存在，此时在计算
时，我们应该将这些项加上，比如含这一项可看作.解：f(x)=((((((8x+5)x+0)x+3)x+0)x+0)x+2)x+1
而x=2，所以有
m0=8， m1=8×2+5=21，
m2=21×2+0=42， m3=42×2+3=87，
m4=87×2+0=174， m5=174×2+0=348，
m6=348×2+2=698， m7=698×2+1=1397，
∴当x=2时，多项式 f(x)的值为1397．7次乘法运算和4次加法运算 练习:
（1）用秦九韶算法求多项式f(x)=x7-2x6+3x3-4x2
+1当x=2时的值.
（2）利用秦九韶算法计算f(x)=0.83x5+0.41x4+
0.16x3+0.33x2+0.5x+1当x=5时的值，并统计需要
多少次乘法计算和多少次加法计算？ 当x=2时，f(x)=9．f(5)=2881.75，5次乘法计算和5次加法计算 补充练习:
设计利用秦九韶算法计算5次多项式f(x)=
a5x5+a4x4+a3x3+a2x2+a1x+a0当x=x0时的值的程序
框图.利用程序框图试编写BASIC程序并在计算
机上测试自己的程序.
并统计所做的计算的种类及计算次数。 一个自然的做法是把5代入多项式 f（x）,这样共需做( )次乘法运算( )次加法计算. 14 5 计算x的幂时，可以利用前面的计算结果，以
减少计算量，即先计算x2，然后依次计算，(x2·x)， (x2·x)·x，((x2·x)·x)·x的值,这样共需做( )次乘法运算( )次加法计算.8 5 思考：能否探索更好的算法，解决任意多项式的求值问题？55 显然这种算法与前两种相比，乘法的运算次
数减少了，因而能提高运算效率，而且对于计算
机来说，做一次乘法所需的运算时间比做一次加
法要长得多，因此这种做法能更快地得到结果.这
种算法就叫秦九韶算法. 秦九韶简介：秦九韶（公元1202-12
61年）南宋，数学家。他在1247年（淳
佑七年）着成《数书九章》十八卷．全
书共81道题，为九大类：大衍类、天时
类、田域类、测望类、赋役类、钱谷类
、营建类、军旅类、市易类。这是一部
划时代的巨著，它总结了前人在开中所
使用的列筹方法，将其整齐而有系统地
应用到高次方程的有理或无理根的求解上去，其中对“
大衍求一术”（一次同余组解法）和“正负开方术”（高
次方程的数值解法）等有十分深入的研究。其中的“大
衍求一术”（一次同余组解法），在世界数学史上占有
崇高的地位. 在古代《孙子算经》中载有“物不知数”这个问题，举例说明：有一数，三三数之余二，五五
数之余二，七七数之余二，问此数为何？这一类问题
的解法可以推广成解一次同余式组的一般方法．奏九
韶给出了理论上的证明，并将它定名为” 大衍求一术
”.这节课我们主要研究的是秦九韶算法中的一种. 即
利用秦九韶算法求一般多项式时值. 尽管秦九韶算法
是距今700多年前提出的，但现在仍是多项式求值的比
较先进的算法；秦九韶是享誉世界的数学家，美国当
代数学史家萨顿（G.Sarton）说，秦九韶是” 他那个
时代、并且确实也是所有时代最伟大的数学家之一！
例1 已知一个5次多项式为f(x)=5x5+2x4+3.5x32.6
x2+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; 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。 思考：例1计算时需要多少次乘法计算？多少
次加法计算？5次乘法计算和5次加法计算 练习：
用秦九韶算法计算x=3时,多项式 f(x)=7x7+
6x6+5x5+4x4+3x3+2x2+x的值, 并统计需要多少次
乘法计算和多少次加法计算？f(3)=21324,7次乘法计算和6次加法计算 思考:怎样用秦九韶算法求一般多项式 f（x）
=anxn+an-1xn-1+an-2xn-2+…+a1x+a0当x=x0(x0是任意
的实数)时的值? 利用秦九韶算法把一个n次多项式f(x)=anxn+
an-1xn-1+an-2xn-2+…+a1x+a0 改写成如下形式：f(x)=anxn+an-1xn-1+an-2xn-2+…+a1x+a0
=(anxn-1+an-1xn-2+an-2xn-3+…a1)x+a0
=((anxn-2+an-1xn-3+…+a2)x+a1)x+a0
=……………
=(…((anx+an-1)x+an-2)x+…+a1)+a0 这样就把n次多项式的求值问题转化成求n个
一次多项式的值的问题即求
v1=anx+an-1,
v2=v1x+an-2,
v3=v2x+an-3,
……
vn=vn-1x+a0,的值得过程.思考:
（1）在利用秦九韶算法计算n次多项式当时需要
多少次乘法计算和多少次加法计算？ 至多n次乘法运算和至多n次加法运算 （2）你能把秦九韶算法编成一个计算机程序吗? 首先我们来分析秦九韶算法的算理: 观察上述秦九韶算法中的n个一次式，可见vk
的计算要用vk-1到的值.若令v0=an,我们可以得到下
面的公式:这是一个在秦九韶算法中反复执行的步骤,因此可
用循环结构设计出算法.
第一步，输入多项式次数n、最高次项的系
数an和x的值. 第二步，将v的值初始化为an，将i的值初始
化为n-1.第三步，输入i 次项的系数ai.第四步，v=vx+ai，i=i-1. 第五步，判断i是否大于或等于0.若是，则返
回第三步；否则，输出多项式的值v.算法分析：否是程序框图：程序： 例2 用秦九韶算法计算多项 f(x)=8x7+5x6+3x4+
2x+1当x=2时的值.并指出计算多项式需要进行的乘法
运算和加法运算次数. 分析：注意本题中有几项不存在，此时在计算
时，我们应该将这些项加上，比如含这一项可看作.解：f(x)=((((((8x+5)x+0)x+3)x+0)x+0)x+2)x+1
而x=2，所以有
m0=8， m1=8×2+5=21，
m2=21×2+0=42， m3=42×2+3=87，
m4=87×2+0=174， m5=174×2+0=348，
m6=348×2+2=698， m7=698×2+1=1397，
∴当x=2时，多项式 f(x)的值为1397．7次乘法运算和4次加法运算 练习:
（1）用秦九韶算法求多项式f(x)=x7-2x6+3x3-4x2
+1当x=2时的值.
（2）利用秦九韶算法计算f(x)=0.83x5+0.41x4+
0.16x3+0.33x2+0.5x+1当x=5时的值，并统计需要
多少次乘法计算和多少次加法计算？ 当x=2时，f(x)=9．f(5)=2881.75，5次乘法计算和5次加法计算 补充练习:
设计利用秦九韶算法计算5次多项式f(x)=
a5x5+a4x4+a3x3+a2x2+a1x+a0当x=x0时的值的程序
框图.利用程序框图试编写BASIC程序并在计算
机上测试自己的程序.