学案7 案例1.doc

绵阳中学实验学校高2012级数学学案7 必修3 第一章 算法初步学案七：辗转相除法、更相减损术与秦九韶算法一、知识精要：（一）求最大公约数的方法（1）短除法 求两个正整数的最大公约数的步骤：先用两个数公有的质因数连续去除，一直除到所得的商是两个互质数为止，然后把所有的除数连乘起来.（2）穷举法（也叫枚举法） 穷举法求两个正整数的最大公约数的解题步骤：从两个数中较小数开始由大到小列举，直到找到公约数立即中断列举，得到的公约数便是最大公约数.（3）辗转相除法（又叫欧几里得算法） 辗转相除法就是对于给定的两个正整数，用大数除以小数，若余数不为0，则将小数和余数构成新的一对数，继续上面的除法，反复执行此步骤，直到大数被小数除尽，则这时较小的数就是原来两个数的最大公约数。其算法步骤为： 第一步，给定两个正整数m，n. 第二步，求余数r：计算m除以n，将所得余数存放到变量r中. 第三步，更新被除数和余数：m=n，n=r. 第四步，判断余数r是否为0，若余数为0，则输出结果；否则执行第二步；如此循环，直到得到结果为止.九章算术-中国（4）更相减损术 更相减损术就是对于给定的两个正整数，若它们都是偶数，则将它们反复除以2(假设进行了k次)，直到它们至少有一个不是偶数后，将大数减小数，然后将差和较小的数构成一对新数，继续上面的减法，反复执行此步骤，直到差和较小的数相等，此时相等的数再乘以原来约简的即为所求两数的最大公约数，其算法步骤为：第一步，任意给定两个正整数，判断是否都是偶数，若是，用2约简；若不是，执行第二步. 第二步，以较大的数减去较小的数，再把差与较小的数比大小，并以大数减小数，如此循环，直到所得的数相等为止，则这个数（等数）或这个数与约简的数的乘积就是所求的最大公约数.怎样求多项式f(x)=x5+x4+x3+x2+x+1当x=5时的值呢？（二）求多项式值的方法（1）法一：把5代入多项式f(x)，计算各项的值，然后把它们加起来，这时，我们一共做了1+2+3+4=10次乘法运算，5次加法运算；（2）法二：先计算x2的值，然后依次计算x2x，（x2x）x，（x2x）x）x的值，这样每次都可以利用上一次计算的结果，这时，我们一共做了4次乘法运算，5次加法运算.数书九章-秦九韶-南宋 （3）法三：秦九韶算法设设(先改写为如下形式，再由内向外逐层计算这样求n次多项式的值就转化为求n个一次多项式的值.当多项式中有些项不存在时，可将这几项看做，补齐后再利用秦九韶算法计算.对于一个n次多项式，只需做n次乘法和n次加法运算即可.（三）算法比较：（1）辗转相除法与更相减损术1.都是求最大公约数的方法，计算上辗转相除法以除法为主，更相减损术以减法为主，计算次数上辗转相除法计算次数相对较少，特别当两个数字大小区别较大时计算次数差异较明显2.从结果体现形式来看，辗转相除法体现结果是以相除余数为0则得到，而更相减损术则以减数与差相等而得到（2）秦九韶算法 直到今天，这种算法仍是多项式求值比较先进的算法，运算步骤少，程序性强。二、范例模仿：例1 用辗转相除法求8 251与6 105的最大公约数,写出算法分析，画出程序框图，写出算法程序.算法如下，思考：为什么37是8 251与6 105的最大公约数？ 算法：第一步，给定两个正整数m，n.第二步，计算m除以n所得的余数为r.第三步，m=n，n=r.第四步，若r=0，则m，n的最大公约数等于m；否则，返回第二步算法：8 251=6 1051+2 1466 105=2 1462+1 8132 146=1 8131+333，1 813=3335+148，333=1482+37，148=374.类比扩展：一般化 辗转相除法求最大公约数的算法变式一：程序：INPUT m,nDO r=m MOD n m=n n=rLOOP UNTIL r=0PRINT mENDEND请修改左边程序变式二：请添加：比较m，n大小的步骤请研读程序，指出其算法功能INPUT “m，n=”；m，nWHILE mnIF mn THENm-nELSEm=n-mEND IFWENDPRINT mEND例2 用更相减损术求98与63的最大公约数.点评：更相减损术与辗转相除法的比较：尽管两种算法分别来源于东、西方古代数学名著，但是二者的算理却是相似的，有异曲同工之妙主要区别在于辗转相除法进行的是除法运算，即辗转相除；而更相减损术进行的是减法运算，即辗转相减，但是实质都是一个不断的递归过程 算法：98-63=3563-35=2835-28=728-7=2121-7=1414-7=7变式：分别用辗转相除法和更相减损术求1 734，816的最大公约数例3 已知多项式函数f(x)=2x55x44x3+3x26x+7，求当x=5时的函数的值.解析：把多项式变形为：f(x)=2x55x44x3+3x26x+7 = (2x5)x4)x+3)x6)x+7.算法：v0=2；v1=255=5；v2=554=21；v3=215+3=108；v4=10856=534；v5=5345+7=2 677.程序：INPUT “n=”；nINPUT “an=”；aINPUT “x=”；xv=ai=n-1WHILE i=0 PRINT “i=”；i INPUT “ai=”；a v=v*x+a i=i-1WENDPRINT vEND 类比扩展：一般化 循环结构为算法：第一步，输入多项式次数n、最高次的系数an和x的值.第二步，将v的值初始化为an，将i的值初始化为n-1.第三步，输入i次项的系数ai.第四步，v=vx+ai,i=i-1.第五步，判断i是否大于或等于0.若是，则返回第三步；否则，输出多项式的值v.秦九韶算法 求多项式值点评：如果多项式函数中有缺项的话，要以系数为0的项补齐后再计算三、反思强化：1.（05.北京.理）已知n次多项式Pn(x)=a0xn+a1xn-1+an-1x+an，如果在一种算法中，计算（k=2，3，4，n）的值需要k1次乘法，计算P3(x0)的值共需要9次运算（6次乘法，3次加法），那么计算P10(x0)的值共需要_次运算.下面给出一种减少运算次数的算法：P0(x)=a0,Pk+1(x)=xPk(x)+ak+1（k0，1，2，n1）利用该算法，计算P3(x0)的值共需要6次运算，计算P10(x0)的值共需要_次运算.2.已知f(x)=3x5+