时辗转相除法与更相减损术秦九韶算法.pptx

《时辗转相除法与更相减损术秦九韶算法.pptx》由会员分享，可在线阅读，更多相关《时辗转相除法与更相减损术秦九韶算法.pptx（33页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1.回顾算法的三种表述：自然语言程序框图（三种逻辑结构）程序语言（五种基本语句）第1页/共33页2.思考：小学学过的求两个数最大公约数的方法？先用两个公有的质因数连续去除，一直除到所得的商是互质数为止，然后把先用两个公有的质因数连续去除，一直除到所得的商是互质数为止，然后把所有的除数连乘起来所有的除数连乘起来.第2页/共33页辗转相除法（欧几里得算法）思考1:求两个正整数的最大公约数（1）求25和35的最大公约数（2）求49和63的最大公约数25（1）5535749（2）77639所以，所以，2525和和3535的最大公约数为的最大公约数为5.5.所以，所以，4949和和6363的最大公约数为

2、的最大公约数为7.7.除了用这种方法外还有没有其他方法？第3页/共33页思考2：算出8251和6105的最大公约数.第一步：第一步：用两数中较大的数除以较小的数，求得商和余数用两数中较大的数除以较小的数，求得商和余数8251=61051+21468251=61051+2146结论：结论：82518251和和61056105的公约数就是的公约数就是61056105和和21462146的公约数，求的公约数，求82518251和和61056105的最的最大公约数，只要求出大公约数，只要求出61056105和和21462146的公约数就可以了的公约数就可以了.第二步：第二步：对对61056105和和2

3、1462146重复第一步的做法重复第一步的做法6105=21462+18136105=21462+1813同理同理61056105和和21462146的最大公约数也是的最大公约数也是21462146和和18131813的最大公约数的最大公约数.为什么？为什么？第4页/共33页完整的过程:8251=61051+2146 6105=21462+1813 2146=18131+3331813=3335+148333=1482+37148=374+0 显然37是148和37的最大公约数，也就是8251和6105的最大公约数.第5页/共33页例1 用辗转相除法求225和135的最大公约数.显然45是90

4、和45的最大公约数，也就是225和135的最大公约数.225=1351+90135=901+4590=452第6页/共33页思考3：从上面的两个例子可以看出计算的规律是什么？S1S1：用大数除以小数：用大数除以小数S2S2：除数变成被除数，余数变成除数：除数变成被除数，余数变成除数S3S3：重复：重复S1S1，直到余数为，直到余数为0 0思考4：辗转相除法中的关键步骤是哪种逻辑结构？辗转相除法是一个反复执行直到余数等于辗转相除法是一个反复执行直到余数等于0 0停止的步骤，这实际上是一个循停止的步骤，这实际上是一个循环结构环结构.第7页/共33页8251=61051+2146 6105=2146

5、2+1813 2146=18131+3331813=3335+148333=1482+37148=374+0m=nqm=nqr r用程序框图表示出右边的过程r=m MOD nm=nn=rr=0?是否第8页/共33页辗转相除法（欧几里得算法）（1 1）算理：算理：所谓辗转相除法，就是对于给定的两个数，用较大的数除以较所谓辗转相除法，就是对于给定的两个数，用较大的数除以较小的数小的数.若余数不为零，则将余数和较小的数构成新的一对数，继续上面的若余数不为零，则将余数和较小的数构成新的一对数，继续上面的除法，直到大数被小数除尽，则这时较小的数就是原来两个数的最大公约数除法，直到大数被小数除尽，则这时较

6、小的数就是原来两个数的最大公约数.第9页/共33页（2 2）算法步骤）算法步骤第一步：第一步：输入两个正整数输入两个正整数m,n(mn).m,n(mn).第二步：第二步：计算计算m m除以除以n n所得的余数所得的余数r.r.第三步：第三步：m=n,n=r.m=n,n=r.第四步：第四步：若若r r0,0,则则m,nm,n的最大公约数等于的最大公约数等于m m；否则转到第二步否则转到第二步.第五步：第五步：输出最大公约数输出最大公约数m.m.第10页/共33页（3 3）程序框图）程序框图（4 4）程序）程序INPUT “m,n=”;m,nDO r=m MOD n m=n n=rLOOP UNT

7、IL r=0PRINT mEND开始输入m，n求m除以n的余数rm=nn=rr=0？是输出m结束否第11页/共33页更相减损术 算理：可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也，以等数约之.第一步：第一步：任意给定两个正整数，判断他们是否都是偶数任意给定两个正整数，判断他们是否都是偶数.若是，则用若是，则用2 2约简；约简；若不是则执行第二步若不是则执行第二步.第二步：第二步：以较大的数减较小的数，接着把所得的差与较小的数比较，并以大以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数数减小数.继续这个操作，直到所得的减数和差相等为止，则这个等数或其与继

8、续这个操作，直到所得的减数和差相等为止，则这个等数或其与约简的数的乘积就是所求的最大公约数约简的数的乘积就是所求的最大公约数.第12页/共33页更相减损术（1 1）算理：）算理：所谓更相减损术，就是对于给定的两个数，用较大的数减去较所谓更相减损术，就是对于给定的两个数，用较大的数减去较小的数，然后将差和较小的数构成新的一对数，再用较大的数减去较小的数，小的数，然后将差和较小的数构成新的一对数，再用较大的数减去较小的数，反复执行此步骤直到差数和较小的数相等，此时相等的两数便为原来两个数反复执行此步骤直到差数和较小的数相等，此时相等的两数便为原来两个数的最大公约数的最大公约数.第13页/共33页（

9、2 2）算法步骤）算法步骤第一步：第一步：输入两个正整数输入两个正整数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.第14页/共33页（3 3）程序框图）程序框图开始输入m，nnk？m=n是输出m结束mn？k=m-n是否n=km=k否第15页/

10、共33页（4 4）程序）程序INPUT “a,b=“;a,bWHILE ab r=a-b IF br THEN a=b b=r ELSE a=r END IFWENDPRINT bEND第16页/共33页例2 用更相减损术求98与63的最大公约数解：解：由于由于6363不是偶数，把不是偶数，把9898和和6363以大数减小数，并辗转相减以大数减小数，并辗转相减 989863633535636335352828353528287 728287 7212121217 7141414147 77 7所以，所以，9898和和6363的最大公约数等于的最大公约数等于7 7 第17页/共33页秦九韶算法的

11、基本思想对于求n次多项式的值，在我国古代数学中有一个优秀算法，即秦九韶算法，我们将对这个算法作些了解和探究.思考1:对于多项式f(x)=x5+x4+x3+x2+x+1，求f(5)的值.若先计算各项的值，然后再相加，那么一共要做多少次乘法运算和多少次加法运算？4+3+2+1=104+3+2+1=10次乘法运算，次乘法运算，5 5次加法运算次加法运算.第18页/共33页思考2:在上述问题中，若先计算x2的值，然后依次计算x2x，(x2x)x，(x2x)x)x的值，这样每次都可以利用上一次计算的结果，再将这些数与x和1相加，那么一共做了多少次乘法运算和多少次加法运算？4 4次乘法运算，次乘法运算，5

12、 5次加法运算次加法运算.第19页/共33页思考3:利用后一种算法求多项式f(x)=anxn+an-1xn-1+a1x+a0的值，这个多项式应写成哪种形式？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-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

13、)x+)x+a+a1 1)x+a)x+a0 0.第20页/共33页思考4:对于f(x)=(anx+an-1)x+an-2)x+a1)x+a0，由内向外逐层计算一次多项式的值，其算法步骤如何？第一步第一步:计算计算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.第第n n步步:计算计算v vn n=v=vn-1n-1x+ax+a0 0.第21页/共33页思考5:上述求多项式f(x)=anxn+an-1xn-1+a1x+a0的值的方法称为秦九韶算法

14、，利用该算法求f(x0)的值，一共需要多少次乘法运算，多少次加法运算？思考6:在秦九韶算法中，记v0=an，那么第k步的算式是什么？v vk k=v=vk-1k-1x+ax+an-kn-k(k=1(k=1，2 2，n)n)第22页/共33页秦九韶算法的程序设计 思考1:用秦九韶算法求多项式的值，可以用什么逻辑结构来构造算法？其算法步骤如何设计？第一步第一步:输入多项式的次数输入多项式的次数n n，最高次项的系数，最高次项的系数a an n和和x x的值的值.第二步第二步:令令v=av=an n，i=n-1.=n-1.第三步第三步:输入输入i次项的系数次项的系数a ai.第四步第四步:v=vx+

15、av=vx+ai，i=i-1.-1.第五步第五步:判断判断i00是否成立是否成立.若是，则返回第三步；否则，输出多项式的值若是，则返回第三步；否则，输出多项式的值v.v.第23页/共33页思考2:该算法的程序框图如何表示？开始输入n，an，x的值v=anv=vx+ai输入aii0？i=n-1i=i-1结束是 输出v 否第24页/共33页思考3:该程序框图对应的程序如何表述？开始输入n，an，x的值v=anv=vx+ai输入aii0？i=n-1i=i-1结束是输出v 否INPUT “n=”；nINPUT “an=”；aINPUT “x=”；x v=a i=n-1WHILE i=0 PRINT“i

16、=”;i INPUT“ai=”；a v=v*x+a i=i-1WENDPRINT vEND第25页/共33页例3 已知一个5次多项式为f(x)=4x5+2x4+3.5x3-2.6x2+1.7x-0.8 用秦九韶算法求f(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.v v1 1=45+2=22=45+2=22；v v2 2=225+3.5=113.5=225+3.5=113.5；v v3 3=113.55-2.6=564.9=113.55-2.6=564.9；v v4 4=564.95+1.

17、7=2826.2=564.95+1.7=2826.2；v v5 5=2826.25-0.8=14130.2.=2826.25-0.8=14130.2.所以所以f(5)=14130.2.f(5)=14130.2.第26页/共33页例4 阅读下列程序，说明它解决的实际问题是什么？求多项式 f(x)=1+2x+3x2+4x3+5x4在x=a时的值.INPUT“x=”；an=0y=0WHILE n5 y=y+(n+1)*a n n=n+1WENDPRINT yEND第27页/共33页1.利用辗转相除法求两数4081与20723的最大公约数.20723=40815+318;4081=31812+265;

18、318=2651+53;265=535+0.(53)(53)第28页/共33页2.用秦九韶算法求多项式f(x)=2x5-5x4-4x3+3x2-6x+7当x=5时的值.解解:首先将原多项式改写成如下形式首先将原多项式改写成如下形式 :f(x)=(2x-5)x-f(x)=(2x-5)x-4)x+3)x-6)x+74)x+3)x-6)x+7然后由内向外逐层计算一次多项式的值然后由内向外逐层计算一次多项式的值,即即v v0 0=2 v=2 v1 1=v=v0 0 x-5=25-5=5x-5=25-5=5v v2 2=v=v1 1x-4=55-4=21x-4=55-4=21v v3 3=v=v2 2x

19、+3=215+3=108x+3=215+3=108v v4 4=v=v3 3x-6=1085-6=534x-6=1085-6=534v v5 5=v=v4 4x+7=5345+7=2677x+7=5345+7=2677所以所以,当当x=5x=5时时,多项式的值是多项式的值是2677.2677.第29页/共33页1.比较辗转相除法与更相减损术的区别（1）都是求最大公约数的方法，计算上辗转相除法以除法为主，更相减损术以减法为主，计算次数上辗转相除法计算次数相对较少，特别当两个数字大小区别较大时计算次数的区别较明显.（2）从结果体现形式来看，辗转相除法体现结果是以相除余数为0而得到，而更相减损术则以减数与差相等而得到.第30页/共33页2.评价一个算法好坏的一个重要标志是运算的次数，如果一个算法从理论上需要超出计算机允许范围内的运算次数，那么这样的算法就只能是一个理论算法.在多项式求值的各种算法中，秦九韶算法是一个优秀算法.第31页/共33页昨天的努力就是今天的收获，今天的努力就是未来的希望。岁月不饶人，不妨现在就行动！第32页/共33页感谢您的观看！第33页/共33页