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

1.3.2算法案例(二)正式版ppt_图文


案例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次加法运算。

例1:用秦九韶算法求多项式 f(x)=2x5-5x4-4x3+3x2-6x+7当x=5时的值. 解法一: f(x)=((((2x-5)x-4)x+3)x-6)x+7 然后由内向外逐层计算一次多项式的值,即 v0=2

v1=v0x-5=2×5-5=5
v2=v1x-4=5×5-4=21 v3=v2x+3=21×5+3=108 所以,当x=5时,多 v5=v4x+7=534×5+7=2677 项式的值是2677. 这种求多项式值的方法就叫秦九韶算法. v4=v3x-6=108×5-6=534

例1:用秦九韶算法求多项式 f(x)=2x5-5x4-4x3+3x2-6x+7当x=5时的值.

解法二:列表
2

原多项式的系 数

x=5
2

-5 10 5

-4 25 21

3 105 108

-6 7 540 2670 534 2677
多项式的值.

所以,当x=5时,多项式的值是2677.

练一练:用秦九韶算法求多项式 f(x)=2x6-5x5-4x3+3x2-6x当x=5时的值. 解:原多项式先化为:

f(x)=2x6-5x5 +0×x4-4x3+3x2-6x+0
3 -6 0 605 3040 15170 2 608 3034 15170 所以,当x=5时,多项式的值是15170. 注意:n次多项式有n+1项,因此缺少哪一项 应将其系数补0. 列表 x=5 2 -5 10 5 0 -4 25 125 25 121

一般地,对于一个n次多项式 f(x)=anxn+an-1xn-1+an-2xn-2+……+a1x+a0. 我们可以改写成如下形式: f(x)=(…(anx+an-1)x+an-2)x+…+a1)x+a0. 求多项式的值时,首先计算最内层括号内一 次多项式的值,即 v1=anx+an-1,

然后由内向外逐层计算一次多项式的值,即
v2=v1x+an-2, v3=v2x+an-3, ……, vn=vn-1x+a0.

这样,求n次多项式f(x)的值就转化为求n个 一次多项式的值.这种算法称为秦九韶算法.

点评:秦九韶算法是求一元多项式的 值的一种方法. 它的特点是:把求一个n次多项式的值 转化为求n个一次多项式的值,通过这种转 化,把运算的次数由至多n(n+1)/2次乘法运 算和n次加法运算,减少为n次乘法运算和n 次加法运算,大大提高了运算效率.

课本P45页练习T2;

P48页A组T2.


相关文章:
蓝桥杯培训教程
搜试试 2 悬赏文档 全部 DOC PPT TXT PDF XLS ...*问题分析与算法设计 假设这个人分别为 A、B、C...程序实例 1: #include <stdio.h> #include <...
...模拟教学方法的创新及规范化推广-中华医学会_图...
搜试试 2 悬赏文档 全部 DOC PPT TXT PDF XLS 广告 百度文库 专业资料 ...8Augus t, 2011 JOURNAL OF SICHUAN AdaBoost 算法的推 14 广_组集成学习...
《软件开发基础》课程标准
搜试试 2 悬赏文档 全部 DOC PPT TXT PDF XLS ...以及在软件开发过程中要解决的数据结构与常用算法的实现...应在每章选取真实的开发案例, 增强学生的理解与...
三年级上数学教案长方形和正方形的周长_人教版-文...
搜试试 2 悬赏文档 全部 DOC PPT TXT PDF XLS ...1、结合实例进一步理解周长的含义,经历探索长方形和...正方形的周长的多种方法,并结合自身实际进行算法优化...
操作系统实验报告
搜试试 2 悬赏文档 全部 DOC PPT TXT PDF XLS ...(二) 要求 1. 能熟练的在 12 种操作系统的...2. 调度程序应包含 23 种不同的调度算法,运行...
对地观测技术国家测绘地理信息局重点试验室科技发...
搜试试 2 悬赏文档 全部 DOC PPT TXT PDF XLS ...可以达到 30-50米左右的对地定位精度(即 1-3像素...(多目视觉) 的航空数字影像测图关键技术及算法, ...
四年级下册数学各单元试题
搜试试 2 悬赏文档 全部 DOC PPT TXT PDF XLS ...新人教版小学数学四年级下学期 第单元测试题 1....乘法结合律 2.986-297 的简便算法是( A.986-...
导学案模版
搜试试 2 悬赏文档 全部 DOC PPT TXT PDF XLS ...、达标检测 1、书 37 页做做第二排 2、...(师板书重点理 解十位的算法) 3、师带领学生回顾...
C语言全套基础知识
搜试试 2 悬赏文档 全部 DOC PPT TXT PDF XLS ...第二,有穷性,算法只能有个输入,个输出,...在下面的例子中, 假定 ch 接收到字符"A"并且奇偶...
更多相关标签: