算法案例第二课时1、求两个数的最大公约数的两种方法分别是()和()。2、两个数21672,8127的最大公约数是()A、2709B、2606C、2703D、2706复习引入:新课讲解:怎样求多项式f(x)=x5+x4+x3+x2+x+1当x=5时的值呢?计算多项式f(x)=x5+x4+x3+x2+x+1当x=5的值的算法:算法1:因为f(x)=x5+x4+x3+x2+x+1所以f(5)=55+54+53+52+5+1=3125+625+125+25+5+1=3906算法2:f(5)=55+54+53+52+5+1=5×(54+53+52+5+1)+1=5×(5×(53+52+5+1)+1)+1=5×(5×(5×(52+5+1)+1)+1)+1=5×(5×(5×(5×(5+1)+1)+1)+1)+1算法1:因为f(x)=x5+x4+x3+x2+x+1所以f(5)=55+54+53+52+5+1=3125+625+125+25+5+1=3906算法2:f(5)=55+54+53+52+5+1=5×(54+53+52+5+1)+1=5×(5×(53+52+5+1)+1)+1=5×(5×(5×(52+5+1)+1)+1)+1=5×(5×(5×(5×(5+1)+1)+1)+1)+1共做了1+2+3+4=10次乘法运算,5次加法运算。共做了4次乘法运算,5次加法运算。《数书九章》——秦九韶算法0111)(axaxaxaxfnnnn设)(xf是一个n次的多项式对该多项式按下面的方式进行改写:0111)(axaxaxaxfnnnn01211)(axaxaxannnn012312))((axaxaxaxannnn0121)))((axaxaxaxannn这是怎样的一种改写方式?最后的结果是什么?0121)))(()(axaxaxaxaxfnnn要求多项式的值,应该先算最内层的一次多项式的值,即11nnaxav然后,由内到外逐层计算一次多项式的值,即212naxvv323naxvv01axvvnn最后的一项是什么?这种将求一个n次多项式f(x)的值转化成求n个一次多项式的值的方法,称为秦九韶算法。通过一次式的反复计算,逐步得出高次多项式的值,对于一个n次多项式,只需做n次乘法和n次加法即可。秦九韶算法的特点:例:已知一个五次多项式为8.07.16.25.325)(2345xxxxxxf用秦九韶算法求这个多项式当x=5的值。解:将多项式变形:8.0)7.1)6.2)5.3)25(((()(xxxxxxf按由里到外的顺序,依此计算一次多项式当x=5时的值:272551v50v5.1385.35272v9.6896.255.1383v2.34517.159.6894v2.172558.052.34515v所以,当x=5时,多项式的值等于17255.2你从中看到了怎样的规律?怎么用程序框图来描述呢?程序框图:开始输入f(x)的系数:a0,a1,a2,a3,a4a5输入x0n≤5?输出v结束v=vx0+a5-nn=n+1YNn=1v=a5),,,(nkaxvvavknkkn2110这是一个在秦九韶算法中反复执行的步骤,因此可用循环结构来实现。另解:(秦九韶算法的另一种直观算法)523.5-2.61.7-0.8X527138.5689.93451.217255.2+多项式的系数多项式的值25135692.53449.51725605(1)、算法步骤:第一步:输入多项式次数n、最高次项的系数an和x的值.第二步:将v的值初始化为an,将i的值初始化为n-1.第三步:输入i次项的系数an.第四步:v=vx+ai,i=i-1.第五步:判断i是否大于或等于0,若是,则返回第三步;否则,输出多项式的值v。思考:你能设计程序把“秦九韶算法”表示出来吗?(2)程序框图:输入ai开始输入n,an,xi=0?输出v结束v=vx+aii=i-1YNi=n-1V=an(3)程序:INPUT“n=”;nINPUT“an=“;aINPUT“x=“;xv=ai=n-1WHILEi=0PRINT“i=“;iINPUT“ai=“;av=v*x+ai=i-1WENDPRINTvEND1、已知多项式f(x)=x5+5x4+10x3+10x2+5x+1用秦九韶算法求这个多项式当x=-2时的值。练习:2、已知多项式f(x)=2x4-6x3-5x2+4x-6用秦九韶算法求这个多项式当x=5时的值。课堂小结:1、秦九韶算法的方法和步骤2、秦九韶算法的程序框图作业:1、P4722、P502