算法案例(辗转相除法)课件.ppt

1、1.3算法案例(第1课时)案例1 辗转相除法最大公约数的定义1、运用的范围：给出两个正整数m,n求它们的最大公约数。2、最大公约数分两种情况：第一种情况：如果这两个数存在倍数关系（即较大数是较小数 的倍数）则较小数就是这两个数的最大公约数。例如：12与6的最大公约数就为6，36与18的最大公约数就是为18第二种情况：这两个数不存在倍数关系则用短除法求之短除法：一般先用这两个数公有的质因数连续去除，一直除到所得的商是互质数为止，然后把所有的除数连乘起来，在除的过程中，有时也可以用两个数的公约数去除。问题2：你又能求出8251与6105的最大公约数吗?问题1：你能求出204与85的最大公约数吗?3

2、0=181+1230与18的最大公约数相当于18与12的最大公约数18=121+618与12的最大公约数相当于12与6的最大公约数12=62+012与6的最大公约数为：6所以，30与18的最大公约数为：6算法1 辗转相除法被除数=除数商+余数所以，17为204与85的最大公约数。20485234853421734172+0问题1、用辗转相除法求两个正数a=204和b=85的最大公约数。204与85的最大公约数相当于85与34的最大公约数85与34的最大公约数相当于34与17的最大公约数34与17的最大公约数为：17解：被除数=除数商+余数解：8251=61051+2146 6105=21462

3、+1813 2146=18131+333 1813=3335+148 333=1482+37 148=374+0所以，8251与6105的最大公约数为：37问题2、用辗转相除法求出8251与6105的最大公约数。运用辗转相除法求下列两个数的最大公约数 例2.求225和135的最大公约数例1.求196和147的最大公约数 例2求225和135的最大公约数 2、解：225=1351+90135=901+45 90=452+0所以，225与135的最大公约数为：45例1求196和147的最大公约数 1、解：196=1471+49147=493+0所以，196与147的最大公约数为：49被除数=除数商

4、+余数第一步：m=nq0+r0第二步：n=r0q1+r1第三步：r0=r1q2+r2第四步：r1=r2q3+r3第五步：r2=r3q4+r4第六步：r3=r4q5+r5第n+1步：rn-2=rn-1qn+rn依次计算直至依次计算直至rn0，此时所得到的除数，此时所得到的除数rn1即为所求的即为所求的最大公约数。最大公约数。辗转相除法的基本步骤：(用qi表示商，ri表示余数）被除数=除数商+余数 8251=61051+2146 6105=21462+1813 2146=18131+333 1813=3335+148 148=374+0所以，8251与6105的最大公约数为：37算法步骤：第一步：

5、给定两个正整数m，n；第二步：计算m除以n所得的余数r；第三步：m=n，n=r；第四步：若r=0，则m，n的最大公约数等于m；否则，返回第二步。程序框图：开始开始输入m,n求m除以n的余数rm=nn=rr=0?结束结束输入m是否程序：INPUT m,nDO r=m MOD n m=n n=rLOOP UNTIL r=0 PRINT mEND欧几里得辗转相除法找出a,b的最大公约数的步骤是:（1）计算ab的余数r,若r=0,则b为a,b的最大公约数；（2）若r0,则把前面的除数b作为新的被除数,把r作为新的除数,继续运算,直到余数为0,此时的除数即为a,b的最大公约数.算算 法法 案案 例例第二

6、课时1、求两个数的最大公约数的两种方法分别是、求两个数的最大公约数的两种方法分别是（）和（）和（）。）。2、两个数、两个数21672，8127的最大公约数是的最大公约数是 （）A、2709 B、2606 C、2703 D、2706复习引入:新课讲解:怎样求多项式怎样求多项式f(x)=xf(x)=x5 5+x+x4 4+x+x3 3+x+x2 2+x+1+x+1当当x=5x=5时的值呢？时的值呢？计算多项式计算多项式()=当当x=5的值的算法：的值的算法：算法算法1：因为因为()=所以所以(5)=55555=3125625125255=3906算法算法2：(5)=55555=5(5555)=5(

7、5(555 )=5(5(5(5+5+)+)+)+=5(5(5(5(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+3+4=10次乘法运算，次乘法运算，5次加法运算。次加法运算。共做了共做了4次乘法运算，次乘法运算，5次加法运算。次加法运算。数书九章数书九章秦九韶算法秦九韶算法0111)(axaxaxaxfnnnn设设)(xf是一个是一个n 次的多项式次的多项式对该多项式按下面的

8、方式进行改写：对该多项式按下面的方式进行改写：0111)(axaxaxaxfnnnn01211)(axaxaxannnn012312)(axaxaxaxannnn0121)(axaxaxaxannn这是怎样的一种改写方式？最后的结果是什么？0121)()(axaxaxaxaxfnnn要求多项式的值，应该先算最内层的一次多项式的值，即要求多项式的值，应该先算最内层的一次多项式的值，即11nnaxav然后，由内到外逐层计算一次多项式的值，即然后，由内到外逐层计算一次多项式的值，即212naxvv323naxvv01axvvnn最后的一最后的一项是什么？项是什么？这种将求一个这种将求一个n次多项式次

9、多项式f(x)的值转化成求的值转化成求n个一个一次多项式的值的方法，称为次多项式的值的方法，称为秦九韶算法秦九韶算法。通过一次式的反复计算，逐步得出高次多通过一次式的反复计算，逐步得出高次多项式的值，对于一个项式的值，对于一个n次多项式，只需做次多项式，只需做n次乘次乘法和法和n次加法即可。次加法即可。秦九韶算法的特点：秦九韶算法的特点：例：例：已知一个五次多项式为已知一个五次多项式为8.07.16.25.325)(2345xxxxxxf用秦九韶算法求这个多项式当用秦九韶算法求这个多项式当x=5的值。的值。解：解：将多项式变形：将多项式变形：8.0)7.1)6.2)5.3)25()(xxxxx

10、xf按由里到外的顺序，依此计算一次多项式当按由里到外的顺序，依此计算一次多项式当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输入x0n5?输出v结束v=vx0+a5-nn=n+1YN n=1 v=a5 ),(nkaxvvavknkkn2110这是一个在这是一个在秦九韶算法秦九韶算法中反

11、复执行的步骤，因中反复执行的步骤，因此可用循环结构来实现。此可用循环结构来实现。另解：（秦九韶算法的另一种直观算法）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 1725605(1)、算法步骤：、算法步骤：第一步：输入多项式次数第一步：输入多项式次数n、最高次项的系数、最高次项的系数an和和x的值的值.第二步：将第二步：将v的值初始化为的值初始化为an，将，将i的值初始化为的值初始化为n-1.第三步：输入第三步：输入i次项的系数次项的系数an.第四步：第四步：v=vx+

12、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-1WHILE i=0 PRINT“i=“;i INPUT“ai=“;a v=v*x+a i=i-1WENDPRINT vEND1、已知多项式、已知多项式f(x)=x5+5x4+10 x3+10 x2+5x+1用用秦九韶算法求这个多项式当秦九韶算法求这个多项式当x=-2时的值。时的值。练习：2、已知多项式、已知多项式f(x)=2x4-6x3-5x2+4x-6用用秦九韶算法求这个多项式当秦九韶算法求这个多项式当x=5时的值。时的值。课堂小结：课堂小结：1、秦九韶算法的方法和步骤、秦九韶算法的方法和步骤2、秦九韶算法的程序框图、秦九韶算法的程序框图