2012届高中数学 1.3算法案例课件 18页

1.3算法案例\n案例1求两个正整数最大公约数的算法\n35915[问题1]：在小学，我们已经学过求最大公约数的知识，你能求出18与30的最大公约数吗？183023∴18和30的最大公约数是2×3=6.先用两个数公有的质因数连续去除,一直除到所得的商是互质数为止,然后把所有的除数连乘起来.[问题2]:我们都是利用找公约数的方法来求最大公约数，如果公约数比较大而且根据我们的观察又不能得到一些公约数，我们又应该怎样求它们的最大公约数？比如求98与63的最大公约数?\n更相减损术\n我国早期也有解决求最大公约数问题的算法，就是更相减损术。更相减损术求最大公约数的步骤如下：用较大的数减去较小的数，接着把较小的数与所得的差比较，并以大数减小数。继续这个操作，直到所得的差与小数相等为止，则这个数（等值）就是所求的最大公约数。\n例1用更相减损术求98与63的最大公约数.解：把98和63以大数减小数，并辗转相减，即：98－63＝35;63－35＝28;35－28＝7;28－7＝21;21－7＝14;14－7＝7.所以，98与63的最大公约数是7。更相减损术又被称作“等值算法”\n练习：用更相减损术（等值算法）求两个正数84与72的最大公约数。\n2.辗转相除法:例2求两个正数8251和6105的最大公约数。分析：8251与6105两数都比较大，而且没有明显的公约数，如能把它们都变小一点，根据已有的知识即可求出最大公约数.解：8251＝6105×1＋2146显然8251与6105的最大公约数也必是2146的约数，同样6105与2146的公约数也必是8251的约数，所以8251与6105的最大公约数也是6105与2146的最大公约数。\n2.辗转相除法:例2求两个正数8251和6105的最大公约数。解：8251＝6105×1＋2146;6105＝2146×2＋1813;2146＝1813×1＋333;1813＝333×5＋148;333＝148×2＋37;148＝37×4＋0.则37为8251与6105的最大公约数。以上我们求最大公约数的方法就是辗转相除法。也叫欧几里德算法，它是由欧几里德在公元前300年左右首先提出的。\n第一步,给定两个正数m,n第二步,计算m除以n所得到余数r第三步,m=n,n=r第四步,若r=0,则m,n的最大公约数等于m;否则返回第二步辗转相除法求最大公约数算法：\n练习2：利用辗转相除法求两数4081与20723的最大公约数.20723=4081×5+318;4081=318×12+265;318=265×1+53;265=53×5+0.\n秦九韶算法案例2\n计算多项式ｆ(ｘ)=ｘ５＋ｘ４＋ｘ３＋ｘ２＋ｘ＋１当x=5的值的算法：算法1：因为ｆ(ｘ)=ｘ５＋ｘ４＋ｘ３＋ｘ２＋ｘ＋１所以ｆ(5)=5５＋5４＋5３＋5２＋5＋１=3125＋625＋125＋25＋5＋１=3906算法2：ｆ(5)=5５＋5４＋5３＋5２＋5＋１=5×(5４＋5３＋5２＋5＋１)＋１=5×(5×(5３＋5２＋5＋１)＋１)＋１=5×(5×(5×(5２+5+１)+１)+１)+１=5×(5×(5×(5×(5+１)+１)+１)+１)+１分析：两种算法中各用了几次乘法运算？和几次加法运算？\nf(x)=2x5-5x4-4x3+3x2-6x+7=(2x4-5x3-4x2+3x-6)x+7=((2x3-5x2-4x+3)x-6)x+7=(((2x2-5x-4)x+3)x-6)x+7=((((2x-5)x-4)x+3)x-6)x+7v0=2v1=v0x-5=2×5-5=5v2=v1x-4=5×5-4=21v3=v2x+3=21×5+3=108v4=v3x-6=108×5-6=534v5=v4x+7=534×5+7=2677所以,当x=5时,多项式的值是2677.这种求多项式值的方法就叫秦九韶算法.求多项式f(x)=2x5-5x4-4x3+3x2-6x+7当x=5时的值.\nf(x)=anxn+an-1xn-1+an-2xn-2+……+a1x+a0.我们可以改写成如下形式:f(x)=(…(anx+an-1)x+an-2)x+…+a1)x+a0.求多项式的值时,首先计算最内层括号内一次多项式的值,即v1=anx+an-1,然后由内向外逐层计算一次多项式的值,即一般地,对于一个n次多项式v2=v1x+an-2,v3=v2x+an-3,……,vn=vn-1x+a0.这样,求n次多项式f(x)的值就转化为求n个一次多项式的值.这种算法称为秦九韶算法.\n秦九韶算法是求一元多项式的值的一种方法.它的特点是:把求一个n次多项式的值转化为求n个一次多项式的值,通过这种转化,把运算的次数由至多n(n+1)/2次乘法运算和n次加法运算,减少为n次乘法运算和n次加法运算,大大提高了运算效率.\n练：已知一个五次多项式为用秦九韶算法求这个多项式当x=5的值。解：将多项式变形：按由里到外的顺序，依此计算一次多项式当x=5时的值：所以，当x=5时，多项式的值等于17255.2\n1、课堂练习P39例题《红对勾》2、作业