案例2秦九韶算法1.ppt

案例1 辗转相除法,知识反馈： 1 用辗转相除法求225和135的最大公约数,225=1351+90,135=901+45,90=452,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的最大公约数是43=12,（2）过程略，153与119的最大公约数是17,程序框图,是,否,b=r,a=b,r=a-b,a=r,否,是,INPUT “a,b=“;a,b IF 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则得到，而更相减损术则以减数与差相等而得到,案例2 秦九韶算法,问题: 设计求多项式f(x)=2x5-5x4-4x3+3x2-6x+7 当x=5时的值的算法,并写出程序.,X=5 f=2*x5-5*x4-4*x3+3*x2-6*x+7 PRINT “f=”;f END,共做了15次乘法运算,5次加法运算.优点是简单,易懂,缺点是不通用,不能解决任意多项式的求值问题,而且效率不高.,有没有更高效的算法呢?,f(x)=2x5-5x4-4x3+3x2-6x+7 =(2x-5)x-4)x+3)x-6)x+7,如果把每一个括号都看成一个常数,那么变形后的式子有哪些“一次式”? x的系数依次是什么?,若将的值代入变形后的式子,那么求值的计算过程是怎样的?,思考:上述算法共做了几次乘法运算,几次加法运算?,我国南宋时期的数学家秦九韶(约1202-1261)在它的著作数书九章中提出了下面的算法.,首先计算最内层括号内一次多项式的值,即,这样,求n次多项式f(x)的值就转化为求n个一次多项式的值.,这种算法称为秦九韶算法.,直到今天，这种算法仍是多项式求值比较先进的算法.,秦九韶是享誉世界的数学家,美国当代数学史家萨顿（G.Sarton)说,秦九韶是“他那个民族、他那个时代、并且确实也是所有时代最伟大的数学家之一”.,3. P38 思考,怎样用程序框图表示秦九韶算法?,用循环结构来实现.,是,否,INPUT “n,an,x=”; n, a,