第1课时辗转相除法与更相减损术、秦九韶算法

1、1.3 算法案例第1课时 辗转相除法与更相减损术、秦九韶算法回顾算法的三种表述：回顾算法的三种表述：自然语言自然语言程序框图（三种逻辑结构）程序框图（三种逻辑结构）程序语言（五种基本语句）程序语言（五种基本语句） 希腊人常以线段代数希腊人常以线段代数. .甲乙两数可以看成长度分别为甲乙甲乙两数可以看成长度分别为甲乙两数的直尺拿短尺去量长尺，若有剩余，再用剩余部分为尺，两数的直尺拿短尺去量长尺，若有剩余，再用剩余部分为尺，去量原来的短尺，如此继续下去去量原来的短尺，如此继续下去. .如果两尺长度之比为有理数，如果两尺长度之比为有理数，经过辗转相量，在有限次内，总会有量尽的时候经过辗转相量，在有限

2、次内，总会有量尽的时候. .若最后量尽若最后量尽时所用的尺回头分别来量原来的两把尺，也会量尽的时所用的尺回头分别来量原来的两把尺，也会量尽的. .希腊人希腊人就说这两把尺（两个线段，两个数）是可共度的就说这两把尺（两个线段，两个数）是可共度的. .这就是辗转这就是辗转相除法相除法. .希腊人以为任何两段都是可共度的，后来发现问题不希腊人以为任何两段都是可共度的，后来发现问题不那么简单那么简单. . 除了辗转相处法，古代还有什么类似的成就呢？除了辗转相处法，古代还有什么类似的成就呢？1.1.通过辗转相除法与更相减损术、秦九韶算法的通过辗转相除法与更相减损术、秦九韶算法的学习学习, ,进一步体会算

3、法思想进一步体会算法思想. .2.2.会用辗转相除法与更相减损术求两个数的最大会用辗转相除法与更相减损术求两个数的最大公约数公约数. .( (重点重点) )3.3.会用秦九韶算法求多项式的值会用秦九韶算法求多项式的值. .( (重点重点) )4.4.了解三种算法的程序框图和程序了解三种算法的程序框图和程序( (难点难点) )9 159 151818和和3030的最大公约数的最大公约数是是2 23=6.3=6.先用两个数公有的先用两个数公有的质因数质因数连连续去除续去除, ,一直除到所得的商是一直除到所得的商是互质数为止互质数为止, ,然后把所有的除然后把所有的除数连乘起来数连乘起来. . 问题

4、问题11：在小学，我们已经学过求最大公约数的知：在小学，我们已经学过求最大公约数的知识，你能求出识，你能求出1818与与3030的最大公约数吗？的最大公约数吗？2 23 318 3018 30 问题问题2:2:我们都是利用找公约数的方法来求最大公我们都是利用找公约数的方法来求最大公约数，如果公约数比较大而且根据我们的观察又不约数，如果公约数比较大而且根据我们的观察又不能得到一些公约数，我们又应该怎样求它们的最大能得到一些公约数，我们又应该怎样求它们的最大公约数？比如求公约数？比如求82518251与与61056105的最大公约数的最大公约数? ? 一、辗转相除法一、辗转相除法 （欧几里得算法）

5、（欧几里得算法）思考：算出思考：算出8 2518 251和和6 1056 105的最大公约数的最大公约数. .第一步第一步, ,用两数中较大的数除以较小的数，求得商用两数中较大的数除以较小的数，求得商和余数和余数8 251=6 1058 251=6 1051+2 146.1+2 146.结论：结论：8 2518 251和和6 1056 105的公约数就是的公约数就是6 1056 105和和2 1462 146的的公约数，求公约数，求8 2518 251和和6 1056 105的最大公约数，只要求出的最大公约数，只要求出6 1056 105和和2 1462 146的最大公约数就可以了的最大公约数

6、就可以了. .1 1. .课堂探究课堂探究第二步第二步, ,对对6 1056 105和和2 1462 146重复第一步的做法，重复第一步的做法，6 105=2 1466 105=2 1462+1 8132+1 813，同理同理6 1056 105和和2 1462 146的最大公约数也是的最大公约数也是2 1462 146和和1 8131 813的的最大公约数最大公约数. .完整的过程完整的过程: :8 251=6 1058 251=6 1051+2 146 1+2 146 6 105=2 1466 105=2 1462+1 813 2+1 813 2 146=1 8132 146=1 8131

7、+3331+3331 813=3331 813=3335+1485+148333=148333=1482+372+37148=37148=374+04+0 显然显然3737是是148148和和3737的最大公约数，也就是的最大公约数，也就是8 2518 251和和6 1056 105的最大公约数的最大公约数. .（1 1）算理：所谓辗转相除法，就是对于给定的两）算理：所谓辗转相除法，就是对于给定的两个正整数，用较大的数除以较小的数个正整数，用较大的数除以较小的数. .若余数不为若余数不为零，则将余数和较小的数构成新的一对数，继续零，则将余数和较小的数构成新的一对数，继续上面的除法，直到大数被小

8、数除尽，则这时较小上面的除法，直到大数被小数除尽，则这时较小的数就是原来两个数的最大公约数的数就是原来两个数的最大公约数. .2 2、辗转相除法、辗转相除法（2 2）算法步骤）算法步骤第一步第一步, ,输入两个正整数输入两个正整数m,n(mm,n(mn).n).第二步第二步, ,计算计算m m除以除以n n所得的余数所得的余数r.r.第三步第三步, ,m=m=n,nn,n=r.=r.第四步第四步, ,若若r r0,0,则则m,nm,n的最大公约数等于的最大公约数等于m m；否；否则转到第二步则转到第二步. . 第五步第五步, ,输出最大公约数输出最大公约数m.m.（3 3）程序框图）程序框图（

9、4 4）程序）程序INPUT INPUT m,nm,nDODO r = m MOD n r = m MOD n m=n m=n n=r n=rLOOP UNTIL r=0LOOP UNTIL r=0PRINT mPRINT mENDEND开始开始输入输入m m，n n求求m m除以除以n n的余数的余数r rm=nm=nn=rn=rr=0r=0？是是输出输出m m结束结束否否除了辗转相除法，还有其他的方除了辗转相除法，还有其他的方法求两正整数的最大公约数吗？法求两正整数的最大公约数吗？可半者半之，不可半者，副置分母、子之数，可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也，

10、以等数约之以少减多，更相减损，求其等也，以等数约之. . 更相减损术更相减损术第一步，第一步，任意给定两个正整数，判断它们是否都是任意给定两个正整数，判断它们是否都是偶数偶数. .若是，用若是，用2 2约简；若不是，执行第二步约简；若不是，执行第二步. .第二步，第二步，以较大的数减去较小的数，接着把所得的以较大的数减去较小的数，接着把所得的差与较小的数比较，并以大数减小数差与较小的数比较，并以大数减小数. .继续这个操作，继续这个操作，直到所得的数相等为止，则这个数（等数）或这个直到所得的数相等为止，则这个数（等数）或这个数与约简的数的乘积就是所求的最大公约数数与约简的数的乘积就是所求的最大

11、公约数. .1 1、课堂探究、课堂探究二、更相减损术二、更相减损术2 2、更相减损术、更相减损术（1 1）算理：）算理：所谓更相减损术，就是对于给定的两所谓更相减损术，就是对于给定的两个数，用较大的数减去较小的数，然后将差和较小个数，用较大的数减去较小的数，然后将差和较小的数构成新的一对数，再用较大的数减去较小的数，的数构成新的一对数，再用较大的数减去较小的数，反复执行此步骤，直到差数和较小的数相等，此时反复执行此步骤，直到差数和较小的数相等，此时相等的两数便为原来两个数的最大公约数相等的两数便为原来两个数的最大公约数. .（2 2）算法步骤）算法步骤第一步第一步, ,输入两个正整数输入两个正

12、整数a,ba,b; ;第二步第二步, ,若若a a不等于不等于b ,b ,则执行第三步；否则转到第则执行第三步；否则转到第五步；五步；第三步第三步, ,把把a-ba-b的差赋给的差赋给r;r;第四步第四步, ,如果如果br, br, 那么把那么把b b赋给赋给a,a,把把r r赋给赋给b;b;否则把否则把r r赋给赋给a a，执行第二步；，执行第二步；第五步第五步, ,输出最大公约数输出最大公约数b.b.（3 3）程序框图）程序框图开始开始输入输入a，bbr？a=b是是输出输出b结束结束ab？r=a- -b是是否否b=ra=r否否（4 4）程序）程序INPUT “INPUT “a,ba,b=“

13、;=“;a,ba,bWHILE WHILE abab r=a-b r=a-b IF br THEN IF br THEN a=b a=b b=r b=r ELSE ELSE a=r a=r END IF END IFWENDWENDPRINT bPRINT bENDEND例例1 1 用辗转相除法与更相减损术求用辗转相除法与更相减损术求9898与与6363的最大公的最大公约数约数. .解：更相减损术解：更相减损术由于由于6363不是偶数，把不是偶数，把9898和和6363以大数减小数，并以大数减小数，并辗转相减辗转相减, , 三、例题选讲三、例题选讲98986363353563633535282

14、8353528287 728287 7212121217 7141414147 77 7所以，所以，9898与与6363的最大公约数等于的最大公约数等于7.7. 辗转相除法辗转相除法989863631 1+ +3535636335351 1+ +2828353528281 1+ +7 728287 74 4+0+0所以，所以，9898与与6363的最大公约数等于的最大公约数等于7.7. 辗转相除法与更相减损术的比较辗转相除法与更相减损术的比较: : （1 1）都是求最大公约数的方法，计算上辗转相除法以除法）都是求最大公约数的方法，计算上辗转相除法以除法为主，更相减损术以减法为主为主，更相减损术

15、以减法为主; ;计算次数上辗转相除法计算次数计算次数上辗转相除法计算次数相对较少，特别当两个数字大小区别较大时计算次数的区别较相对较少，特别当两个数字大小区别较大时计算次数的区别较明显。明显。 （2 2）从结果体现形式来看，辗转相除法体现结果是以相除）从结果体现形式来看，辗转相除法体现结果是以相除余数为余数为0 0则得到，而更相减损术则以减数与差相等而得到则得到，而更相减损术则以减数与差相等而得到. .除了上述算法，下面学习另外一种古代优秀的算法除了上述算法，下面学习另外一种古代优秀的算法. .对于求对于求n n次多项式的值，在我国古代数学中有一个次多项式的值，在我国古代数学中有一个优秀算法，

16、即秦九韶算法，我们将对这个算法作些优秀算法，即秦九韶算法，我们将对这个算法作些了解和探究了解和探究. .1 1. .课堂探究课堂探究四、秦九韶算法四、秦九韶算法思考思考1:1:对于多项式对于多项式f(xf(x)=x)=x5 5+x+x4 4+x+x3 3+x+x2 2+x+1+x+1，求，求f(5)f(5)的值的值. . 若先计算各项的值，然后再相加，那么一共若先计算各项的值，然后再相加，那么一共要做多少次乘法运算和多少次加法运算？要做多少次乘法运算和多少次加法运算？4+3+2+1=104+3+2+1=10次乘法运算，次乘法运算，5 5次加法运算次加法运算. . 思考思考2:2:在上述问题中，

17、若先计算在上述问题中，若先计算x x2 2的值，然后依次计的值，然后依次计算算x x2 2xx，(x(x2 2x)xx)x，(x(x2 2x)x)xx)x)x的值，这样的值，这样每次都可以利用上一次计算的结果，再将这些数与每次都可以利用上一次计算的结果，再将这些数与x x相乘和相乘和1 1相加，那么一共做了多少次乘法运算和多少相加，那么一共做了多少次乘法运算和多少次加法运算？次加法运算？4 4次乘法运算，次乘法运算，5 5次加法运算次加法运算. . 思考思考3:3:利用后一种算法求多项式利用后一种算法求多项式f(xf(x)=)=a an nx xn n +a +an-1n-1x xn-1n-1

18、+a+a1 1x+ax+a0 0的值，这个多项式应写成哪种形式？的值，这个多项式应写成哪种形式？f(xf(x)=a)=an nx xn n+a+an-1n-1x xn-1n-1+ +a+a1 1x+ax+a0 0 =(a=(an nx xn-1n-1+a+an-1n-1x xn-2n-2+ +a+a2 2x+ax+a1 1)x+a)x+a0 0=(a=(an nx xn-2n-2+a+an-1n-1x xn-3n-3+ +a+a2 2)x+a)x+a1 1)x+a)x+a0 0 = =(=(a(an nx+ax+an-1n-1)x+a)x+an-2n-2)x+)x+a+a1 1)x+a)x+a

19、0 0. .这是怎样的这是怎样的一种改写方一种改写方式？最后的式？最后的结果是什么？结果是什么？思考思考4:4:对于对于f(xf(x)=(a)=(an nx+ax+an-1n-1)x+a)x+an-2n-2)x+a)x+a1 1)x)x+a+a0 0，由内向外逐层计算一次多项式的值，其算法，由内向外逐层计算一次多项式的值，其算法步骤如何？步骤如何？第一步第一步, ,计算计算v v1 1=a=an nx+ax+an-1n-1. . 第二步第二步, ,计算计算v v2 2=v=v1 1x+ax+an-2n-2. .第三步第三步, ,计算计算v v3 3=v=v2 2x+ax+an-3n-3. .

20、第第n n步步, ,计算计算v vn n=v=vn-1n-1x+ax+a0 0. .最后的一最后的一项是什么？项是什么？思考思考5:5:上述求多项式上述求多项式f(xf(x)=a)=an nx xn n+a+an-1n-1x xn-1n-1+a+a1 1x+ax+a0 0的值的值的方法称为秦九韶算法，利用该算法求的方法称为秦九韶算法，利用该算法求f(xf(x0 0) )的值，一的值，一共需要多少次乘法运算，多少次加法运算？共需要多少次乘法运算，多少次加法运算？n n次乘法运算，次乘法运算，n n次加法运算次加法运算思考思考6:6:在秦九韶算法中，记在秦九韶算法中，记v v0 0=a=an n，

21、那么第，那么第k k步的算式步的算式是什么？是什么？v vk k=v=vk-1k-1x+ax+an-kn-k (k=1 (k=1，2 2，n)n)秦九韶算法的程序设计秦九韶算法的程序设计 思考思考1:1:用秦九韶算法求多项式的值用秦九韶算法求多项式的值，其算法步骤如何其算法步骤如何设计？设计？第一步，第一步，输入多项式的次数输入多项式的次数n n，最高次项的系数，最高次项的系数a an n和和x x的值的值. . 第二步，第二步，令令v=av=an n，i=n-1. i=n-1. 第三步，第三步，输入输入i i次项的系数次项的系数a ai i. . 第四步，第四步，v=v=vx+avx+ai

22、i，i=i-1.i=i-1.第五步，第五步，判断判断i0i0是否成立是否成立. .若是，则返回第三步；若是，则返回第三步；否则，输出多项式的值否则，输出多项式的值v.v. 算法步骤算法步骤开始开始输入输入n，an，x的值的值v=anv=vx+ai输入输入aii0？i=n- -1i=i- -1结束结束是是 输出输出v 否否思考思考2:2:该算法的程序该算法的程序框图如何表示？框图如何表示？INPUT “n=”INPUT “n=”；n nINPUT “anINPUT “an =”=”；a aINPUT “x=”INPUT “x=”；x x v=av=a i=n-1 i=n-1WHILE i=0WH

23、ILE i=0 PRINT “i=”;i PRINT “i=”;i INPUT “ INPUT “aiai=”=”；a a v=v v=v* *x+ax+a i=i-1 i=i-1WENDWENDPRINT vPRINT vENDEND思考思考3:3:该程序框图对应该程序框图对应的程序如何表述？的程序如何表述？例例2 2、已知一个、已知一个5 5次多项式为次多项式为f(xf(x)=4x)=4x5 5+2x+2x4 4+3.5x+3.5x3 3-2.6x-2.6x2 2+1.7x-0.8+1.7x-0.8，用秦九韶算法求这个多项式当用秦九韶算法求这个多项式当x=5x=5时的值时的值. .解：解：

24、根据秦九韶算法把多项式改写成如下形式：根据秦九韶算法把多项式改写成如下形式：f(xf(x)=(4x+2)x+3.5)x-2.6)x+1.7)x-0.8.)=(4x+2)x+3.5)x-2.6)x+1.7)x-0.8.按照从内到外的顺序，依次计算一次多项式当按照从内到外的顺序，依次计算一次多项式当x=5x=5时的值：时的值：v v0 0=4;=4;v v1 1=4=45+2=225+2=22；v v2 2=22=225+3.5=113.55+3.5=113.5；v v3 3=113.5=113.55-2.6=564.95-2.6=564.9；v v4 4=564.9=564.95+1.7=2 8

25、26.25+1.7=2 826.2；v v5 5=2 826.2=2 826.25-0.8=14 130.2.5-0.8=14 130.2.所以所以f(5)=14 130.2.f(5)=14 130.2.阅读右面程序，阅读右面程序，说明它解决的说明它解决的实际问题是什么？实际问题是什么？解：解：求多项式求多项式f(xf(x)=1+2x+3x)=1+2x+3x2 2+4x+4x3 3+5x+5x4 4在在x=ax=a时的值时的值. .INPUT “x=”INPUT “x=”；a an=0n=0y=0y=0WHILE n5WHILE n5 y=y+(n+1)y=y+(n+1)* *a an n n

26、=n+1 n=n+1WENDWENDPRINT yPRINT yENDEND【变式练习变式练习】1 1下列对辗转相除法的说法错误的是下列对辗转相除法的说法错误的是( () )A A辗转相除法也叫欧几里得算法，但比欧几里得算辗转相除法也叫欧几里得算法，但比欧几里得算法早法早B B辗转相除法的基本步骤是用较大的数除以较小的辗转相除法的基本步骤是用较大的数除以较小的数数C C在对两个数求最大公约数时，除辗转相除法之外在对两个数求最大公约数时，除辗转相除法之外还有更相减损术还有更相减损术D D在用辗转相除法时，需要用到循环语句编写程序在用辗转相除法时，需要用到循环语句编写程序A A2 2秦九韶算法与直

27、接计算相比较，下列说法错误秦九韶算法与直接计算相比较，下列说法错误的是的是( () )A A秦九韶算法与直接计算相比，大大节省了乘法的秦九韶算法与直接计算相比，大大节省了乘法的次数，使计算量减小，逻辑结构简单次数，使计算量减小，逻辑结构简单B B秦九韶算法减少做乘法的次数，在计算机上也就秦九韶算法减少做乘法的次数，在计算机上也就加快了计算的速度加快了计算的速度C C秦九韶算法减少做乘法的次数，在计算机上也就秦九韶算法减少做乘法的次数，在计算机上也就降低了计算的速度降低了计算的速度D D秦九韶算法避免对自变量秦九韶算法避免对自变量x x单独作幂的计算，而是单独作幂的计算，而是与系数一起逐次增长幂

28、次，从而可提高计算的精度与系数一起逐次增长幂次，从而可提高计算的精度C C3.3.利用辗转相除法求两数利用辗转相除法求两数4 0814 081与与20 72320 723的最大公的最大公约数约数. .解：解： 20 723=4 08120 723=4 0815+318;5+318;4 081=3184 081=31812+265;12+265;318=265318=2651+53;1+53;265=53265=535+0. 5+0. 所以所以4 0814 081与与20 72320 723的最大公约数是的最大公约数是53.53.4.4.已知已知f f( (x x) )3 3x x4 42 2x x2 24 4x x2 2，利用秦九韶算法求，利用秦九韶算