1.3.2算法案例（第二课时）ppt

《1.3.2算法案例（第二课时）ppt》由会员分享，可在线阅读，更多相关《1.3.2算法案例（第二课时）ppt（9页珍藏版）》请在装配图网上搜索。

1、1、求两个数的最大公约数的两种方法分别、求两个数的最大公约数的两种方法分别是是 和和 。2、两个数、两个数21672，8127的最大公约数是（的最大公约数是（ ）A、2709 B、2606 C、2703 D、2706案例2、秦九韶算法怎样求多项式怎样求多项式f(x)=xf(x)=x5 5+x+x4 4+x+x3 3+x+x2 2+x+1+x+1当当x=5x=5时的值呢？时的值呢？计算多项式计算多项式() =xx x x x 当当x = 5的值的值算法算法1：(5)=55555=3125625125255= 3906算法算法2：(5)=55555=5(5555 ) =5(5(555 ) ) =5

2、(5(5(5+5 +) + ) + ) +=5(5(5(5 (5 +) + )+)+) +共做了共做了1+2+3+4=101+2+3+4=10次乘法运算，次乘法运算，5 5次加法运算。次加法运算。共做了共做了4 4次乘法运算，次乘法运算，5 5次加法运算。次加法运算。数书九章数书九章秦九韶算法秦九韶算法0111)(axaxaxaxfnnnn设设)(xf是一个是一个n 次的多项式次的多项式对该多项式按下面的方式进行改写：对该多项式按下面的方式进行改写：0111)(axaxaxaxfnnnn01211)(axaxaxannnn012312)(axaxaxaxannnn0121)(axaxaxaxa

3、nnn这是怎样的一种改写方式？最后的结果是什么？0121)()(axaxaxaxaxfnnn要求多项式的值，应该先算最内层的一次多项式的值，即要求多项式的值，应该先算最内层的一次多项式的值，即11nnaxav然后，由内到外逐层计算一次多项式的值，即然后，由内到外逐层计算一次多项式的值，即212naxvv323naxvv01axvvnn最后的一最后的一项是什么？项是什么？这种将求一个这种将求一个n次多项式次多项式f(x)的值转化成求的值转化成求n个一个一次多项式的值的方法，称为次多项式的值的方法，称为秦九韶算法秦九韶算法。算法步骤：算法步骤：第一步：输入多项式次数第一步：输入多项式次数n、最高次

4、项的系数、最高次项的系数an和和x的值的值.第二步：将第二步：将v的值初始化为的值初始化为an，将，将i的值初始化为的值初始化为n-1.第三步：输入第三步：输入i次项的系数次项的系数ai.第四步：第四步：v=vx+ai,i=i-1.第五步：判断第五步：判断i是否小于或等于是否小于或等于0，若是，则返回第，若是，则返回第三步；否则，输出多项式的值三步；否则，输出多项式的值v。程序框图：程序框图：这是一个在这是一个在秦九韶算法秦九韶算法中反复执行的步骤，因中反复执行的步骤，因此可用循环结构来实现。此可用循环结构来实现。输入输入ai开始开始输入输入n,an,xi=0?输出输出v结束结束v=vx+ai

5、i=i-1YNi=n-1V=an ),(nkaxvvavknkkn2110例例 已知一个五次多项式为已知一个五次多项式为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你从中看到了怎样的规律？怎么用程序框图来描述呢？