1.3算法案例第1课时辗转相除法与更相减损术、秦九韶算法1.通过辗转相除法与更相减损术、秦九韶算法的学习,进一步体会算法思想;2.通过古代著名的算法,理解掌握辗转相除法与更相减损术、秦九韶算法的含义;(重点)3.了解其计算过程;(重点)4.了解其算法程序框图和程序．(难点)1.回顾算法的三种表述：自然语言程序框图（三种逻辑结构）程序语言（五种基本语句）2.小学学过的求两个数最大公约数的方法.先用两个公有的质因数连续去除，一直除到所得的商是互质数为止，然后把所有的除数连乘起来.例如：求两个正整数的最大公约数（1）求25和35的最大公约数（2）求49和63的最大公约数25（1）5535749（2）77639所以，25和35的最大公约数为5.所以，49和63的最大公约数为7.除了用这种方法外还有没有其他方法吗？辗转相除法（欧几里得算法）思考：算出8251和6105的最大公约数.第一步,用两数中较大的数除以较小的数，求得商和余数8251=6105×1+2146.结论：8251和6105的公约数就是6105和2146的公约数，求8251和6105的最大公约数，只要求出6105和2146的最大公约数就可以了.为什么？第二步,对6105和2146重复第一步的做法，6105=2146×2+1813，同理6105和2146的最大公约数也是2146和1813的最大公约数.完整的过程:8251=6105×1+21466105=2146×2+18132146=1813×1+3331813=333×5+148333=148×2+37148=37×4+0显然37是148和37的最大公约数，也就是8251和6105的最大公约数.所谓辗转相除法，就是对于给定的两个数，用较大的数除以较小的数.若余数不为零，则将余数和较小的数构成新的一对数，继续上面的除法，直到大数被小数除尽，则这时较小的数就是原来两个数的最大公约数.（1）辗转相除法（2）算法步骤第一步,输入两个正整数m,n(m>n).第二步,计算m除以n所得的余数r.第三步,m=n,n=r.第四步,若r＝0,则m,n的最大公约数等于m；否则转到第二步.第五步,输出最大公约数m.（3）程序框图（4）程序INPUTm,nDOr=mMODnm=nn=rLOOPUNTILr=0PRINTmEND开始输入m，n求m除以n的余数rm=nn=rr=0？是输出m结束否更相减损术算理：可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也，以等数约之.第一步：任意给定两个正整数，判断它们是否都是偶数.若是，则用2约简；若不是则执行第二步.第二步：以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数.继续这个操作，直到所得的数相等为止，则这个数（等数）或其与约简的数的乘积就是所求的最大公约数.更相减损术（1）算理：所谓更相减损术，就是对于给定的两个数，用较大的数减去较小的数，然后将差和较小的数构成新的一对数，再用较大的数减去较小的数，反复执行此步骤，直到差数和较小的数相等，此时相等的两数便为原来两个数的最大公约数.（2）算法步骤第一步,输入两个正整数a,b(a>b);第二步,若a不等于b,则执行第三步；否则转到第五步；第三步,把a-b的差赋予r;第四步,如果b>r,那么把b赋给a,把r赋给b;否则把r赋给a，执行第二步；第五步,输出最大公约数b.（3）程序框图开始输入a，bb>r？a=b是输出b结束a≠b？r=a-b是否b=ra=r否（4）程序INPUT“a,b=“;a,bWHILEa≠br=a-bIFb>rTHENa=bb=rELSEa=rENDIFWENDPRINTbEND例1用更相减损术求98与63的最大公约数.解：由于63不是偶数，把98和63以大数减小数，并辗转相减,98－63＝3563－35＝2835－28＝728－7＝2121－7＝1414－7＝7所以，98和63的最大公约数等于7.秦九韶算法的基本思想对于求n次多项式的值，在我国古代数学中有一个优秀算法，即秦九韶算法，我们将对这个算法作些了解和探究.思考1:对于多项式f(x)=x5+x4+x3+x2+x+1，求f(5)的值.若先计算各项的值，然后再相加，那么一共要做多少次乘法运算和多少次加法运算？4+3+2+1=10次乘法运算，5次加法运算.思考2:在上述问题中，若先计算x2的值，然后依次计算x2·x，(x2·x)·x，((x2·x)·x)·x的值，这样每次都可以利用上一次计算的结果，再将这些数与x和1相加，那么一共做了多少次乘法运算和多少次加法运算？4次乘法运算，5次加法运算.思考3:利用后一种算法求多项式f(x)=anxn+an-1xn-1+…+a1x+a0的值，这个多项式应写成哪种形式？f(x)=anxn+an-1xn...
VIP
