1.3案例2秦九韶算法.1.ppt

案例2 秦九韶算法 问题: 设计求多项式f(x)=2x5-5x4-4x3+3x2-6x+7 当x=5时的值的算法,并写出程序. f(x)=2x5-5x4-4x3+3x2-6x+7 =((((2x-5)x-4)x+3)x-6)x+7 * 案例1 辗转相除法 知识反馈： 1 用辗转相除法求225和135的最大公约数 ∵225=135×1+90 135=90×1+45 90=45×2 ∴45是225和135的最大公约数 直到型: DO r=m MOD n m=n n=r LOOP UNTIL r=0 2.把辗转相除法编写成一个计算机程序 INPUT m,n PRINT m END 当型: INPUT m,n r=1 WHILE r0 r=m MOD n m=n n=r WEND PRINT m END 更相减损术 可半者半之,不可半者,副置分母、子之数,以少减多,更相减损,求其等也以等数约之。 第一步：任意给定两个正整数;判断他们是否都是偶 数.若是,则用2约简;若不是则执行第二步. 第二步：以较大的数减较小的数,接着把所得的差与较小的数比较,并以大数减小数.继续这个操作,直到所得的减数和差相等为止,则这个数（等数）或这个数与约简的数的乘积就是所求的最大公约数。 1、《九章算术》中的更相减损术： 一、背景介绍： 2、现代数学中的更相减损术： 二、更相减损术求最大公约数 1.求98与63的最大公约数 所以7就是98与63的最大公约数 解： 2.用更相减损术求下列两数的最大公约数. ⑴ 84 , 36 ⑵ 153 , 119 解（1）用4去约84，36得21，9 ∵21-9=12 12-9=3 9-3=6 6-3=3 3-3=0 ∴ 84与36的最大公约数是4×3=12 （2）过程略，153与119的最大公约数是17 程序框图 开始 输入a,b(ab) a≠b? 是 否 输出b 结束 b=r a=b r=a-b rb? a=r 否 是 INPUT “a,b=“;a,b IF ab THEN t=a a=b b=t END IF WHILE ab r=a-b IF br THEN a=b b=r ELSE a=r END IF WEND PRINT b END 求两个正数184与72的最大公约数． 练习： 8 比较辗转相除法与更相减损术的区别 （1）都是求最大公约数的方法，计算上辗转相除法以除法为主，更相减损术以减法为主，计算次数上辗转相除法计算次数相对较少，特别当两个数字大小区别较大时计算次数的区别较明显。 （2）从结果体现形式来看，辗转相除法体现结果是以相除余数为0则得到，而更相减损术则以减数与差相等而得到 X=5 f=2*x^5-5*x^4-4*x^3+3*x^2-6*x+7 PRINT “f=”;f END 共做了15次乘法运算,5次加法运算.优点是简单,易懂,缺点是不通用,不能解决任意多项式的求值问题,而且效率不高. 有没有更高效的算法呢? 如果把每一个括号都看成一个常数,那么变形后的式子有哪些“一次式”? x的系数依次是什么? 若将的值代入变形后的式子,那么求值的计算过程是怎样的? 思考:上述算法共做了几次乘法运算,几次加法运算? 我国南宋时期的数学家秦九韶(约1202-1261)在它的著作《数书九章》中提出了下面的算法. 首先计算最内层括号内一次多项式的值,即 这样,求n次多项式f(x)的值就转化为求n个一次多项式的值. 这种算法称为秦九韶算法. 直到今天，这种算法仍是多项式求值比较先进的算法. 秦九韶是享誉世界的数学家,美国当代数学史家萨顿（G.Sarton)说,秦九韶是“他那个民族、他那个时代、并且确实也是所有时代最伟大的数学家之一”. 3. P38 思考 怎样用程序框图表示秦九韶算法? 用循环结构来实现. 开始 输入n,an,x的值 v=an i=n-1 i≥0? v=vx+ai 输入ai i=i-1 输出v 结束 是 否 INPUT “n,an,x=”; n, a, 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