《辗转相除法与更相减损术、秦九韶算法.ppt》由会员分享，可在线阅读，更多相关《辗转相除法与更相减损术、秦九韶算法.ppt（32页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、1.3 算法案例第1课时 辗转相除法与更相减损术、秦九韶算法1.1.通过辗转相除法与更相减损术、秦九韶算法的学习通过辗转相除法与更相减损术、秦九韶算法的学习, ,进进一步体会算法思想一步体会算法思想; ;2.2.通过古代著名的算法通过古代著名的算法, ,理解掌握辗转相除法与更相减损理解掌握辗转相除法与更相减损术、秦九韶算法的含义术、秦九韶算法的含义; ;( (重点重点) )3.3.了解其计算过程了解其计算过程; ;( (重点重点) )4.4.了解其算法程序框图和程序了解其算法程序框图和程序( (难点难点) )1. 1. 回顾算法的三种表述：回顾算法的三种表述：自然语言自然语言程序框图（三种逻辑
2、结构）程序框图（三种逻辑结构）程序语言（五种基本语句）程序语言（五种基本语句）2.2.小学学过的求两个数最大公约数的方法小学学过的求两个数最大公约数的方法. .先用两个公有的质因数连续去除，一直除到所得的商是先用两个公有的质因数连续去除，一直除到所得的商是互质数为止，然后把所有的除数连乘起来互质数为止，然后把所有的除数连乘起来. .例如：求两个正整数的最大公约数例如：求两个正整数的最大公约数（1 1）求）求2525和和3535的最大公约数的最大公约数（2 2）求）求4949和和6363的最大公约数的最大公约数2525（1 1） 5 55 535357 74949（2 2） 7 77 76363
3、9 9所以，所以，2525和和3535的最大公的最大公约数为约数为5.5.所以，所以，4949和和6363的最大公的最大公约数为约数为7.7.除了用这种方法外还有除了用这种方法外还有没有其他方法吗？没有其他方法吗？辗转相除法辗转相除法 （欧几里得算法）（欧几里得算法）思考：算出思考：算出8 2518 251和和6 1056 105的最大公约数的最大公约数. .第一步第一步, ,用两数中较大的数除以较小的数，求得商和余用两数中较大的数除以较小的数，求得商和余数数8 251=6 1058 251=6 1051+2 146.1+2 146.结论：结论：8 2518 251和和6 1056 105的公
4、约数就是的公约数就是6 1056 105和和2 1462 146的公的公约数，求约数，求8 2518 251和和6 1056 105的最大公约数，只要求出的最大公约数，只要求出6 1056 105和和2 1462 146的最大公约数就可以了的最大公约数就可以了. .为什么？为什么？第二步第二步, ,对对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的的最大公约数
5、最大公约数. .完整的过程完整的过程: :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+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的的最大公约数最大公约数. . 所谓辗转相除法，就是对于给定的两个数，用较所
6、谓辗转相除法，就是对于给定的两个数，用较大的数除以较小的数大的数除以较小的数. .若余数不为零，则将余数和较若余数不为零，则将余数和较小的数构成新的一对数，继续上面的除法，直到大数小的数构成新的一对数，继续上面的除法，直到大数被小数除尽，则这时较小的数就是原来两个数的最大被小数除尽，则这时较小的数就是原来两个数的最大公约数公约数. .（1 1）辗转相除法）辗转相除法（2 2）算法步骤）算法步骤第一步第一步, ,输入两个正整数输入两个正整数m,n(mn).m,n(mn).第二步第二步, ,计算计算m m除以除以n n所得的余数所得的余数r.r.第三步第三步, ,m=n,n=r.m=n,n=r.第
7、四步第四步, ,若若r r0,0,则则m,nm,n的最大公约数等于的最大公约数等于m m；否则转；否则转到第二步到第二步. . 第五步第五步, ,输出最大公约数输出最大公约数m.m.（3 3）程序框图）程序框图（4 4）程序）程序INPUT m,nINPUT m,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结束结束否否更相减损术更相减损
8、术 算理：算理：可半者半之，不可半者，副置分母、子之数，以少可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也，以等数约之减多，更相减损，求其等也，以等数约之. .第一步：第一步：任意给定两个正整数，判断它们是否都是偶数任意给定两个正整数，判断它们是否都是偶数. .若是，则用若是，则用2 2约简；若不是则执行第二步约简；若不是则执行第二步. .第二步：第二步：以较大的数减较小的数，接着把所得的差与较小以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数的数比较，并以大数减小数. .继续这个操作，直到所得的继续这个操作，直到所得的数相等为止，则这个数（等数）或其与
9、约简的数的乘积就数相等为止，则这个数（等数）或其与约简的数的乘积就是所求的最大公约数是所求的最大公约数. .更相减损术更相减损术（1 1）算理：）算理：所谓更相减损术，就是对于给定的两个数，所谓更相减损术，就是对于给定的两个数，用较大的数减去较小的数，然后将差和较小的数构成新用较大的数减去较小的数，然后将差和较小的数构成新的一对数，再用较大的数减去较小的数，反复执行此步的一对数，再用较大的数减去较小的数，反复执行此步骤骤，直到差数和较小的数相等，此时相等的两数便为原直到差数和较小的数相等，此时相等的两数便为原来两个数的最大公约数来两个数的最大公约数. .（2 2）算法步骤）算法步骤第一步第一步
10、, ,输入两个正整数输入两个正整数a,b(ab);a,b(ab);第二步第二步, ,若若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）程序）程序I
11、NPUT “a,b=“;a,bINPUT “a,b=“;a,bWHILE abWHILE ab 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以大数减小数，并辗转相减以大数减小数，并辗转相减, , 989863633535636335352828353528287 72
12、8287 7212121217 7141414147 77 7所以，所以，9898和和6363的最大公约数等于的最大公约数等于7. 7. 秦九韶算法的基本思想秦九韶算法的基本思想对于求对于求n n次多项式的值，在我国古代数学中有一个优秀算法，次多项式的值，在我国古代数学中有一个优秀算法，即秦九韶算法，我们将对这个算法作些了解和探究即秦九韶算法，我们将对这个算法作些了解和探究. .思考思考1:1:对于多项式对于多项式f(x)=xf(x)=x5 5+x+x4 4+x+x3 3+x+x2 2+x+1+x+1，求，求f(5)f(5)的值的值. . 若先计算各项的值，然后再相加，那么一共要做多少次乘若先
13、计算各项的值，然后再相加，那么一共要做多少次乘法运算和多少次加法运算？法运算和多少次加法运算？4+3+2+1=104+3+2+1=10次乘法运算，次乘法运算，5 5次加法运算次加法运算. . 思考思考2:2:在上述问题中，若先计算在上述问题中，若先计算x x2 2的值，然后依次计算的值，然后依次计算x x2 2xx，(x(x2 2x)xx)x，(x(x2 2x)x)xx)x)x的值，这样每次的值，这样每次都可以利用上一次计算的结果，再将这些数与都可以利用上一次计算的结果，再将这些数与x x和和1 1相加，相加，那么一共做了多少次乘法运算和多少次加法运算？那么一共做了多少次乘法运算和多少次加法运
14、算？4 4次乘法运算，次乘法运算，5 5次加法运算次加法运算. . 思考思考3:3:利用后一种算法求多项式利用后一种算法求多项式f(x)=af(x)=an nx xn n+a+an-1n-1x xn-1n-1+a+a1 1x+ax+a0 0的值，这个多项式应写成哪种形式？的值，这个多项式应写成哪种形式？f(x)=af(x)=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
15、-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+a0 0. .这是怎样的一这是怎样的一种改写方式？种改写方式？最后的结果是最后的结果是什么？什么？思考思考4:4:对于对于f(x)=(af(x)=(an nx+ax+an-1n-1)x+a)x+an-2n-2)x+a)x+a1 1)x+a)x+a0 0，由，由内向外逐层计算一次多项式的值，其算法步骤如何？内向外逐层计算一次多项式的值，其算法步骤如何？第一步第一步, ,计算计算v v1 1=a
16、=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. . 第第n n步步, ,计算计算v vn n=v=vn-1n-1x+ax+a0 0. .最后的一项最后的一项是什么？是什么？思考思考5:5:上述求多项式上述求多项式f(x)=af(x)=an nx xn n+a+an-1n-1x xn-1n-1+a+a1 1x+ax+a0 0的值的的值的方法称为秦九韶算法，利用该算法求方法称为秦九韶算法，利用该算法求f(xf(x0 0) )的值，一共需的值，一
17、共需要多少次乘法运算，多少次加法运算？要多少次乘法运算，多少次加法运算？思考思考6:6:在秦九韶算法中，记在秦九韶算法中，记v v0 0=a=an n，那么第，那么第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
18、an n和和x x的值的值. . 第二步第二步: :令令v=av=an n，i=n-1. =n-1. 第三步第三步: :输入输入i次项的系数次项的系数a ai. . 第四步第四步: :v=vx+av=vx+ai，i= =i-1.-1.第五步第五步: :判断判断i00是否成立是否成立. .若是，则返回第三步；否则，若是，则返回第三步；否则，输出多项式的值输出多项式的值v. v. 思考思考2:2:该算法的程序该算法的程序框图如何表示？框图如何表示？开始开始输入输入n，an，x的值的值v=anv=vx+ai输入输入aii0？i=n- -1i=i- -1结束结束是是 输出输出v 否否思考思考3:3:该
19、程序框图对应的程序如何表述？该程序框图对应的程序如何表述？开始开始输入输入n，an，x的值的值v=anv=vx+ai输入输入aii0？i=n- -1i=i- -1结束结束是是输出输出v 否否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=0WHILE i=0 PRINT “i=”;i PRINT “i=”;i INPUT “ai=” INPUT “ai=”；a a v=v v=v* *x+ax+a i=i-1 i=i-1WENDWENDPR
20、INT vPRINT vENDEND例例2 2 已知一个已知一个5 5次多项式为次多项式为f(x)=4xf(x)=4x5 5+2x+2x4 4+3.5x+3.5x3 3-2.6x-2.6x2 2+ +1.7x-0.81.7x-0.8，用秦九韶算法求这个多项式当，用秦九韶算法求这个多项式当x=5x=5时的值时的值. .解：根据秦九韶算法把多项式改写成如下形式：解：根据秦九韶算法把多项式改写成如下形式：f(x)=(4x+2)x+3.5)x-2.6)x+1.7)x-0.8.f(x)=(4x+2)x+3.5)x-2.6)x+1.7)x-0.8.按照从内到外的顺序，依次计算一次多项式当按照从内到外的顺序
21、，依次计算一次多项式当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 826.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.阅读下列程序，说明它解决的实际问题是什么？阅读下列程序，说明它解决的实
22、际问题是什么？解：求多项式解：求多项式 f(x)=1+2x+3xf(x)=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=n+1 n=n+1WENDWENDPRINT yPRINT yENDEND1. 1. 用辗转相除法求用辗转相除法求225225和和135135的最大公约数的最大公约数. .显然显然4545是是9090和和4545的最大公约数，也就是的最大公约数，也就是225225和和
23、135135的最大的最大公约数公约数. . 225=135225=1351+901+90135=90135=901+451+4590=4590=452 22.2.利用辗转相除法求两数利用辗转相除法求两数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的最大公约数是的最大公约数是
24、53.53.3.3.用秦九韶算法求多项式用秦九韶算法求多项式f(x)=2xf(x)=2x5 5-5x-5x4 4-4x-4x3 3+3x+3x2 2-6x+7-6x+7当当x=5x=5时的值时的值. .解解: :首先将原多项式改写成如下形式首先将原多项式改写成如下形式 : : f(x)=(2x-5)x-4)x+3)x-6)x+7f(x)=(2x-5)x-4)x+3)x-6)x+7然后由内向外逐层计算一次多项式当然后由内向外逐层计算一次多项式当x=5x=5时的值时的值, ,即即v v0 0=2 v=2 v1 1=v=v0 0 x-5=2x-5=25-5=55-5=5v v2 2=v=v1 1x-
25、4=5x-4=55-4=215-4=21v v3 3=v=v2 2x+3=21x+3=215+3=1085+3=108v v4 4=v=v3 3x-6=108x-6=1085-6=5345-6=534v v5 5=v=v4 4x+7=534x+7=5345+7=2 6775+7=2 677所以所以, ,当当x=5x=5时时, ,多项式的值是多项式的值是2 677.2 677.1.1.比较辗转相除法与更相减损术的区别比较辗转相除法与更相减损术的区别（1 1）都是求最大公约数的方法，计算上辗转相除法以除）都是求最大公约数的方法，计算上辗转相除法以除法为主，更相减损术以减法为主，计算次数上辗转相除法
26、为主，更相减损术以减法为主，计算次数上辗转相除法计算次数相对较少，特别当两个数字大小区别较大时，法计算次数相对较少，特别当两个数字大小区别较大时，计算次数的区别较明显计算次数的区别较明显. .（2 2）从结果体现形式来看，辗转相除法体现结果是以相）从结果体现形式来看，辗转相除法体现结果是以相除余数为除余数为0 0而得到，而更相减损术则以减数与差相等而得而得到，而更相减损术则以减数与差相等而得到到. .2.2.评价一个算法好坏的一个重要标志是运算的次数，如评价一个算法好坏的一个重要标志是运算的次数，如果一个算法从理论上需要超出计算机允许范围内的运算果一个算法从理论上需要超出计算机允许范围内的运算次数，那么这样的算法就只能是一个理论算法次数，那么这样的算法就只能是一个理论算法. .在多项式在多项式求值的各种算法中，秦九韶算法是一个优秀算法求值的各种算法中，秦九韶算法是一个优秀算法. . 昨天的努力就是今天的收获，今天的努力就是未来的希望.岁月不饶人，不妨现在就行动！