广东省汕头市高中数学 第一章 算法初步 1.3 秦九韶算法与进位制 新人教A版必修3.ppt

、求两个数的最大公约数的两种方法分别是()和()。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次加法运算。《数书九章》——秦九韶算法设是一个n次的多项式对该多项式按下面的方式进行改写:思考:当知道了x的值后该如何求多项式的值?这是怎样的一种改写方式?最后的结果是什么?要求多项式的值,应该先算最内层的一次多项式的值,即然后,由内到外逐层计算一次多项式的值,即最后的一项是什么?这种将求一个n次多项式f(x)的值转化成求n个一次多项式的值的方法,称为秦九韶算法。思考:在求多项式的值上,这是怎样的一个转化?算法步骤:第一步:输入多项式次数n、:将v的值初始化为an,:输入i次项的系数an-:v=vx+an-i,i=i+:判断i是否小于或等于n,若是,则返回第三步;否则,输出多项式的值v。程序框图:这是一个在秦九韶算法中反复执行的步骤,因此可用循环结构来实现。输入an-i开始输入n,an,xi<=n?输出v结束v=vx+an-ii=i+1YNi=1V=an特点:通过一次式的反复计算,逐步得出高次多项式的值,对于一个n次多项式,只需做n次乘法和n次加法即可。