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...