- 1、本文档共68页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
用--辗 秦
第四步,若r=0,则m,n的最大公 约数等于m;否则,返回第二步 1:用辗转相除法求80和36的最大公约数,并用更相减损术检验所得结果. 分析:将80作为大数,36作为小数,执行辗转相除法和更相减损术的步骤即可. 解:用辗转相除法: 80=36×2+8, 36=8×4+4, 8=4×2+0. 故80和36的最大公约数是4. 4.问题提出:除了用上述算法求两个数的最大公约数之外还有没有别的算法? 5.点拨:用“更相减损术”:更相减损术,是我国数学家刘徽的专著《九章算术》中记载的.更相减损术求最大公约数的步骤如下:可半者半之,不可半者,副置分母、子之数,以少减多,更相减损,求其等也.,以等数约之. 《数书九章》——秦九韶算法 设 是一个n 次的多项式 对该多项式按下面的方式进行改写: 这是怎样的一种改写方式?最后的结果是什么? 要求多项式的值,应该先算最内层的一次多项式的值,即 然后,由内到外逐层计算一次多项式的值,即 最后的一项是什么? 这种将求一个n次多项式f(x)的值转化成求n个一次多项式的值的方法,称为秦九韶算法。 通过一次式的反复计算,逐步得出高次多项式的值,对于一个n次多项式,只需做n次乘法和n次加法即可。 秦九韶算法的特点: 例: 已知一个五次多项式为 用秦九韶算法求这个多项式当x = 5的值。 解: 将多项式变形: 按由里到外的顺序,依此计算一次多项式当x = 5时的值: 所以,当x = 5时,多项式的值等于17255.2 知识探究(一):秦九韶算法的基本思想 思考1:对于多项式f(x)=2x5+x4+x3+x2+x+1,求f(5)的值. 若先计算各项的值,然后再相加,那么一共要做多少次乘法运算和多少次加法运算? 4+3+2+1=10次乘法运算, 5次加法运算. 思考2:在上述问题中,若先计算x2的值,然后依次计算((((2x+1)x+1)x+1)x+1)x+1的值,这样每次都可以利用上一次计算的结果,再将这些数与x和1相加,那么一共做了多少次乘法运算和多少次加法运算? 5次乘法运算,5次加法运算. 思考3:利用后一种算法求多项式f(x)=anxn+an-1xn-1+…+a1x+a0的值,这个多项式应写成哪种形式? f(x)=anxn+an-1xn-1+…+a1x+a0 =(anxn-1+an-1xn-2+…+a2x+a1)x+a0 =((anxn-2+an-1xn-3+…+a2)x+a1)x+a0 =… =(…((anx+an-1)x+an-2)x+…+a1)x+a0. 思考4:对于f(x)=(…((anx+an-1)x+ an-2)x+…+a1)x+a0,由内向外逐层计算一次多项式的值,其算法步骤如何? 第一步,计算v1=anx+an-1. 第二步,计算v2=v1x+an-2. 第三步,计算v3=v2x+an-3. … 第n步,计算vn=vn-1x+a0. 知识探究(二):秦九韶算法的程序设计 思考1:用秦九韶算法求多项式的值,可以用什么逻辑结构来构造算法?其算法步骤如何设计? 第一步,输入多项式的次数n,最高次 项的系数an和x的值. 第二步,令v=an,i=n-1. 第三步,输入i次项的系数ai. 第四步,v=vx+ai,i=i-1. 第五步,判断i≥0是否成立.若是,则返回第 二步;否则,输出多项式的值v. 思考2:该算法的程序框图如何表示? 开始 输入n,an,x的值 v=an v=vx+ai 输入ai i≥0? i=n-1 i=i-1 结束 是 输出v 否 思考3:该程序框图对应的程序如何表述? 开始 输入n,an,x的值 v=an v=vx+ai 输入ai i≥0? i=n-1 i=i-1 结束 是 输出v 否 INPUT “n=”;n INPUT “an=”;a INPUT “x=”;x v=a i=n-1 WHILE i=0 INPUT “ai=”;b v=v*x+b i=i-1 WEND PRINT y END 小结作业 评价一个算法好坏的一个重要标志是运算的次数,如果一个算法从理论上需要超出计算机允许范围内的运算次数,那么这样的算法就只能是一个理论算法.在多项式求值的各种算法中,秦九韶算法是一个优秀算法. 思考:你能设计程序把“秦九韶算法”表示出来吗? 这是一个在秦九韶算法中反复执行的步骤,因此可用循环结构来实现。 算法分析: 观察上述秦九韵算法中的n个一次式,可见vk的计算要用到vk-1的值。若令v0=an,我们可以得到下面的公式: 1、求两个正整数的最大公约数 (1)求25和35的最大公约数 (2)求49和63的最大公约数 25 (1) 5 5 3
文档评论(0)