1[1].3算法案例(第2课时秦九韶算法)整理
算法案例,（第二课时） 秦九韶算法,1、求两个数的最大公约数的两种方法分别是 （辗转相除法）和（更相减损术）。 2、两个数21672，8127的最大公约数是 （ ） A、2709 B、2606 C、2703 D、2706,_,A,3、求324，243，135三个数的最大公约数.,27,分析：求三个数的最大公约数可以先求出两个数的最大公约数，第三个数与前两个数的最大公约数再求最大公约数即为所求。,秦九韶（约1202年1261年）南 宋官员、数学家，与李冶、杨辉、 朱世杰并称宋元数学四大家。主要成就:1247年完成了数学名著数书九章，其中的大衍求一术、三斜求积术和秦九韶算法是具有世界意义的重要贡献。秦九韶算法就是中国古代数学的一枝奇葩。直到今天，这种算法仍是多项式求值比较先进的算法 。 美国著名科学史家萨顿说过，秦九韶是“他那个民族，他那个时代，并且确实也是所有时代最伟大的数学家之一”。,案例2、秦九韶算法,知识探究(一):秦九韶算法的基本思想,思考1:对于多项式f(x)=x5+x4+x3+x2+x+1，怎么样求f(5)的值呢？,计算多项式() =当x = 5的值,算法1：,因为() =,所以(5)=55555,=3125625125255,= 3906,算法2：,(5)=55555,=5×(5555 ) ,=5×(5×(555 ) ) ,=5×(5×(5×(5+5 +) + ) + ) +,=5×(5×(5×(5 ×(5 +) + )+)+) +,分析：两种算法中各用了几次乘法运算？和几次加法运算？,算法1：,算法2：,共做了1+2+3+4=10次乘法运算，5次加法运算。,共做了4次乘法运算，5次加法运算。,思考2:利用后一种算法求多项式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,次乘法运算，,次加法运算.,n,n,思考3:对于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.,上述求多项式f(x)=anxn+an-1xn-1+a1x+a0的值的方法称为秦九韶算法，利用该算法可求f(x0)的值.,思考4:在秦九韶算法中，记v0=an，那么第k步的算式是什么？,vk=vk-1x,第一步，计算v1=anx+an-1=,v0x+an-1.,第k步，,如：第三步，计算v3=v2x+an-3.,+an-k,(k=,1，2，n),秦九韶算法的递推关系式,v0=an,例1 已知一个5次多项式为 用秦九韶算法求f(5)的值.,f(x)=(4x+2)x+3.5)x-2.6)x+1.7)x-0.8.,v1=,v2=,v3=,v4=,v5=,所以f(5)=14130.2.,解：根据秦九韶算法，把多项式改写成,v0=,4；,4×5+2=,22；,22×5+3.5=,113.5；,113.5×5-2.6=,564.9；,2826.2；,564.9×5+1.7=,14130.2.,2826.2×5-0.8=,求f(4)的值.,f(x)=(3x+2)x-9)x-11)x+1,解：根据秦九韶算法，把多项式改写成,v1=,v2=,v3=,v4=,f(4)=709.,v0=,3；,3×4+2=,14；,14×4-9=,47；,47×4-11=,177；,709；,177×4+1=,秦九韶算法的特点及注意事项：,特点：,通过一次式的反复计算，有规律的推算出下一个值，从而计算高次多项式的值，这种算法也称为“递推法”.一般地，对于一个n次多项式需进行 次乘法运算和 _次加法运算。,n,n,注意：,若多项式函数中间出现空项，,要以系数为0补齐此项，即0×xm,2， 应用秦九韶算法计算x=3时的值时，v3的值为( ),已知,A 27 B 11 C 109 D 36,f(x)=(x+0)x+2)x+3)x+1)x+1,v1=,v2=,v3=,v0=,1；,1×3+0=,3；,3×3+2=,11；,11×3+3=,36.,D,分析：() =023,3.用秦九韶算法计算多项式,当x=0.4时的值时，需要做乘法和加法的次数分别是( ),A 6,6 B 5,6 C 5,5 D 6,5,A,知识探究(二):秦九韶算法的程序设计,思考1:用秦九韶算法求多项式的值，可以用什么逻辑结构来构造算法？其算法步骤如何设计？,第一步，输入多项式的次数n，最高次 项的系数an和x的值.,第二步，令v=an，i=n-1.,第三步，输入i次项的系数ai.,第四步，v=vx+ai，i=i-1.,第五步，判断“i0”是否成立.若是，则,循环结构,返回第三步，否则，,输出多项式的值v.,这是一个在秦九韶算法中反复执行的步骤，因此可用循环结构来实现。,思考2:该算法的程序框图如何表示？,是,1.计算v1=anx+an-1.,2.计算v2=v1x+an-2.,3.计算v3=v2x+an-3.,n.计算vn=vn-1x+a0.,思考3:程序？,INPUT “n=”；n,INPUT “an=”；a,INPUT “x=”；x,v=a,i=n-1,WHILE i=0,INPUT “ai=”；a,v=v*x+a,i=i-1,WEND,PRINT v,END,是,PRINT “i=”；i,另解：（秦九韶算法的另一种直观算法）,5 2 3.5 -2.6 1.7 -0.8,X5,27 138.5 689.9 3451.2 17255.2,+,多项式的系数,多项式的值,25 135 692.5 3449.5 17256,0,5,1、已知多项式f(x)=x5+5x4+10x3+10x2+5x+1 用秦九韶算法求这个多项式当x=-2时的值。,练习：,2、已知多项式f(x)=2x4-6x3-5x2+4x-6 用秦九韶算法求这个多项式当x=5时的值。,小结,评价一个算法好坏的一个重要标志是运算的次数，如果一个算法从理论上需要超出计算机允许范围内的运算次数，那么这样的算法就只能是一个理论算法.在多项式求值的各种算法中，秦九韶算法是一个优秀算法.,
