版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、会计学1算法案例算法案例-秦九韶算法秦九韶算法问题1设计求多项式f(x)=2x5-5x4-4x3+3x2-6x+7当x=5时的值的算法,并写出程序.x=5f=2x5-5x4-4x3+3x2-6x+7PRINT fEND程序点评:上述算法一共做了15次乘法运算,5次加法运算.优点是简单,易懂;缺点是不通用,不能解决任意多项多求值问题,而且计算效率不高.第1页/共14页 这析计算上述多项式的值,一共需要9次乘法运算,5次加法运算.问题2有没有更高效的算法?分析:计算x的幂时,可以利用前面的计算结果,以减少计算量,即先计算x2,然后依次计算222,(),()xx xxxxxxx的值.第二种做法与第一
2、种做法相比,乘法的运算次数减少了,因而能提高运算效率.而且对于计算机来说,做一次乘法所需的运算时间比做一次加法要长得多,因此第二种做法能更快地得到结果.第2页/共14页问题3能否探索更好的算法,来解决任意多项式的求值问题?f(x)=2x5-5x4-4x3+3x2-6x+7=(2x4-5x3-4x2+3x-6)x+7=(2x3-5x2-4x+3)x-6)x+7=(2x2-5x-4)x+3)x-6)x+7=(2x-5)x-4)x+3)x-6)x+7v0=2v1=v0 x-5=25-5=5v2=v1x-4=55-4=21v3=v2x+3=215+3=108v4=v3x-6=1085-6=534v5=
3、v4x+7=5345+7=2677所以,当x=5时,多项式的值是2677.这种求多项式值的方法就叫秦九韶算法.第3页/共14页第4页/共14页第5页/共14页例3:用秦九韶算法求多项式 f(x)=2x5-5x4-4x3+3x2-6x+7当x=5时的值.解法一:首先将原多项式改写成如下形式 : f(x)=(2x-5)x-4)x+3)x-6)x+7v0=2 v1=v0 x-5=25-5=5v2=v1x-4=55-4=21v3=v2x+3=215+3=108v4=v3x-6=1085-6=534v5=v4x+7=5345+7=2677所以,当x=5时,多项式的值是2677.然后由内向外逐层计算一次多
4、项式的值,即第6页/共14页2 -5 -4 3 -6 7x=5105252110510854053426702677所以,当x=5时,多项式的值是2677.原多项式的系数多项式的值.例3:用秦九韶算法求多项式 f(x)=2x5-5x4-4x3+3x2-6x+7当x=5时的值.解法二:列表2第7页/共14页2 -5 0 -4 3 -6 0 x=5105252512512160560830403034所以,当x=5时,多项式的值是15170.练一练:用秦九韶算法求多项式 f(x)=2x6-5x5-4x3+3x2-6x当x=5时的值.解:原多项式先化为: f(x)=2x6-5x5 +0 x4-4x3
5、+3x2-6x+0列表21517015170 注意:n次多项式有n+1项,因此缺少哪一项应将其系数补0.第8页/共14页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,然后由内向外逐层计算一次多项式的值,即一般地,对于一个n次多项式v2=v1x+an-2, v3=v2x+an-3, ,vn=vn-1x+a0.这样,求n次多项式f(x)的值就转化为求n个一次多项式的值.这种算法称为秦九韶算法.第9页/共14页
6、点评:秦九韶算法是求一元多项式的值的一种方法.它的特点是:把求一个n次多项式的值转化为求n个一次多项式的值,通过这种转化,把运算的次数由至多n(n+1)/2次乘法运算和n次加法运算,减少为n次乘法运算和n次加法运算,大大提高了运算效率.第10页/共14页v1=anx+an-1,v2=v1x+an-2,v3=v2x+an-3, ,vn=vn-1x+a0.观察上述秦九韶算法中的n个一次式,可见vk的计算要用到vk-1的值.若令v0=an,得v0=an,vK=vK-1x+an-k(k=1,2,n这是一个在秦九韶算法中反复执行的步骤,因此可用循环结构来实现.问题画出程序框图,表示用秦九韶算法求5次多项式f(x)=a5x5+a4x4+a3x3+a2x2+a1x+a0当x=x0 (x0是任意实数)时的值的过程,然后写出程序.第11页/共14页否程序框图开始输入a0,a1,a2,a3,a4,a5输入x0n5?n=1v=a5v=vx0+a5-nn=n+1输出v结束是INPUT a0, a1,
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2E-4E-6E-2-4-6-Nonatrienal-13C2-生命科学试剂-MCE
- 中考语文复习语法常考点解析及应用
- 医疗机构血液透析收治标准和血液透析室基本标准
- 开工奠基仪式流程
- 人教版六年级语文上册第五单元试卷
- 【信息技术】数据分析与可视化 课件 2023-2024学年人教-中图版(2019)高中信息技术必修1
- 旅游车驾驶员安全管理制度
- 初中语文教学中的朗读技巧和方法
- DL-T 1807-2018 油浸式电力变压器、电抗器局部放电超声波检测与定位导则
- 关于安全警示教育心得体会【三篇】
- 施工图深化设计方案(幕墙工程)
- 20100927-宣化上人《愣严咒句偈疏解》(简体全)
- 如何撰写医学科研项目申请书
- 中国游戏产业报告2023
- 部编版六年级语文下册第三次月考试卷及答案全套
- 2023年同等学力人员申请硕士学位工商管理学科综合水平考试真题及答案
- 裁床记录时间表
- 基于医院信息化平台的急诊护理绩效考核体系的构建与实践
- 红色经典影片与近现代中国发展期末考试答案
- 物流信息系统智慧树知到课后章节答案2023年下集美大学
- 家装装修施工方案简单版
评论
0/150
提交评论