方法：方法：新课导入新课导入新课导入新课导入 先用两个公有的质因数连续去除，一先用两个公有的质因数连续去除，一直除到所得的商是互质数为止，然后把所直除到所得的商是互质数为止，然后把所有的除数连乘起来。有的除数连乘起来。12知识要知识要点点辗转相除法（欧几里得算法）辗转相除法（欧几里得算法） ： 所谓辗转相除法所谓辗转相除法，就是对于给定的两，就是对于给定的两个数，用较大的数除以较小的数。若余数个数，用较大的数除以较小的数。若余数不为零，则将余数和较小的数构成新的一不为零，则将余数和较小的数构成新的一对数，继续上面的除法，直到大数被小数对数，继续上面的除法，直到大数被小数除尽，则这时较小的数就是原来两个数的除尽，则这时较小的数就是原来两个数的最大公约数。最大公约数。3过程过程8251=61051+21466105=21462+18132146=18131+3331813=3335+148333=1482+37148=374+0显然显然37是是148和和37的最大公约数，也就是的最大公约数，也就是8251和和6105的最大公约数的最大公约数=37（8251，6105）=（6105，2146）=（2146，1813）=（1813，333）=（333，148）=（148，37）求求8251和和6105的最大公约数。的最大公约数。4辗转相除法算法步骤：辗转相除法算法步骤：第一步：输入两个正整数第一步：输入两个正整数m,n(mn)；第二步：计算第二步：计算m除以除以n所得的余数所得的余数r；第三步：第三步：m=n,n=r；第四步：若第四步：若r0,则则m,n的最大公约数等于的最大公约数等于m；否则转到第二步；否则转到第二步；第五步：输出最大公约数第五步：输出最大公约数m。5辗转相除法是一个反复执行直到余数等于辗转相除法是一个反复执行直到余数等于0停止停止的步骤，这实际上是一个循环结构。的步骤，这实际上是一个循环结构。用程序框图表示出过程用程序框图表示出过程r=mMODnm=nn=rr=0?是是否否6程序框图程序框图开始开始输入输入m,nr=mMODnm=nr=0?是是否否n=r输出输出m结束结束程序程序INPUT“m,n=“;m,nDOr=mMODnm=nn=rLOOPUNTILr=0PRINTmEND7九章算术九章算术更相减损术更相减损术 算理：算理：可半者半之，不可半者，副置分母、子之数，可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也，以等数约之。以少减多，更相减损，求其等也，以等数约之。第一步：第一步：任意给定两个正整数；判断他们是否都是任意给定两个正整数；判断他们是否都是偶数。若是，则用偶数。若是，则用2 2约简；若不是则执行第二步。约简；若不是则执行第二步。第二步：第二步：以较大的数减较小的数，接着把所得的差以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止，则这个等数就是所直到所得的减数和差相等为止，则这个等数就是所求的最大公约数。求的最大公约数。8知识要知识要点点 更相减损术更相减损术 所谓更相减损术所谓更相减损术，就是对于给定的两，就是对于给定的两个数，用较大的数减去较小的数，然后将个数，用较大的数减去较小的数，然后将差和较小的数构成新的一对数，再用较大差和较小的数构成新的一对数，再用较大的数减去较小的数，反复执行此步骤直到的数减去较小的数，反复执行此步骤直到差数和较小的数相等，此时相等的两数便差数和较小的数相等，此时相等的两数便为原来两个数的最大公约数。为原来两个数的最大公约数。9用更相减损术求用更相减损术求98与与63的最大公约数。的最大公约数。解析：解析：由于由于63不是偶数，把不是偶数，把98和和63以大数减以大数减小数，并辗转相减。小数，并辗转相减。按照算法步按照算法步骤来求解！骤来求解！10=7所以，所以，98和和63的最大公约数等于的最大公约数等于7。（98，63）=（63，35）98-63=3563-35=28=（35，28）35-28=7=（28，7）28-7=21=（21，7）21-7=14=（14，7）14-7=7=（7，7）解：解：11更相减损术算法描述：更相减损术算法描述：第一步：输入两个正整数第一步：输入两个正整数a,b(ab);第二步：若第二步：若a不等于不等于b,则执行第三步；否则转则执行第三步；否则转到第五步；到第五步；第三步：把第三步：把a-b的差赋予的差赋予r;第四步：如果第四步：如果br,那么把那么把b赋给赋给a,把把r赋给赋给b;否否则把则把r赋给赋给a，执行第二步；，执行第二步；第五步：输出最大公约数第五步：输出最大公约数b。算法步骤！算法步骤！12a=r开始开始输入输入a,bab?是是否否输出输出b结束结束b=ra=br=a-brb?否否是是程序框图程序框图程序程序INPUT“a,b=“;a,bWHILEabr=a-bIFbrTHENa=bb=rELSEa=rENDIFWENDPRINTbEND13知识要知识要点点 秦九韶算法秦九韶算法所谓秦九韶算法所谓秦九韶算法，就是求一个，就是求一个n次多项次多项式的值的方法。式的值的方法。14要求多项式的值，应该先算最内层的一次多项式的值，即要求多项式的值，应该先算最内层的一次多项式的值，即然后，由内到外逐层计算一次多项式的值，即然后，由内到外逐层计算一次多项式的值，即这种将求一个这种将求一个n次多项式次多项式f（x）的值转化成求）的值转化成求n个一次多项式的值的个一次多项式的值的方法，称为方法，称为秦九韶算法秦九韶算法。15例例2 已知一个五次多项式为已知一个五次多项式为用秦九韶算法求这个多项式当用秦九韶算法求这个多项式当x = 5的值。的值。解：解： 将多项式变形：将多项式变形：按由里到外的顺序，依此计算一次多项式当按由里到外的顺序，依此计算一次多项式当x = 5时的值：时的值：所以，当所以，当x = 5时，多项式的值等于时，多项式的值等于17255.2你从中看到了怎样的规律？怎么用程序框图来描述呢？16算法步骤：算法步骤：第一步：输入多项式次数第一步：输入多项式次数n、最高次项的系、最高次项的系数数an和和x的值。的值。第二步：将第二步：将v的值初始化为的值初始化为an，将，将i的值初始化为的值初始化为1。第三步：输入第三步：输入i次项的系数次项的系数an-i。第四步：第四步：v=vx+an-i,i=i+1。第五步：判断第五步：判断i是否小于或等于是否小于或等于n，若是，则返回第，若是，则返回第三步；否则，输出多项式的值三步；否则，输出多项式的值v。17开始开始输入输入f (x)的系数：的系数：a0、a1、a2、a3、a4、a5输入输入x0n=0v=a5v= vx0+a5-nn=n+1n S S=S+5 n=n+2 T=T+n 输出输出T 结束结束 是是 否否 30按照程序框图依次执行为按照程序框图依次执行为S=5,n=2,T=2;S=10,n=4,T=2+4=6;S=15,n=6,T=6+6=12;S=20,n=8,T=12+8=20;S=25,n=10,T=20+10=30S,输出输出T=30。解析解析:311.用更相减损术求下列两数的最大公约数：用更相减损术求下列两数的最大公约数：（1）（）（225，135）（2）（）（98，196）（3）（）（72，168）（4）（）（153，119）45982417随堂练习随堂练习随堂练习随堂练习322设计利用秦九韶算法计算设计利用秦九韶算法计算5次多项式次多项式当当时的值程序和的程序框图。时的值程序和的程序框图。 解：解：INPUT“a1,a2,a3,a4,a5=”;a1,a2,a3,a4,a5INPUT“x0=”;x0n=1v=a5IFn=5THENn=n+1v=x0+a5-nPRINT“v=”;vENDIFEND33程序框图：程序框图：341.(1)45;(2)98;(3)24;(4)17；2.2881.75；3.略；略；4.略。略。习题答案习题答案习题答案习题答案练习练习1.3（第（第36页）页）3536