11.4算法案例[学习目标]1.通过案例，进一步体会算法的思想；2.理解并能利用案例中的算法解决具体问题．[知识链接](1)20和30的最大公约数为10.(2)已知函数f(x)＝x2＋2x－1，计算f(1)的值时用了2次乘法和2次加法运算；当函数变为f(x)＝(x＋2)x－1，求f(1)时，用了1次乘法运算和2次加法运算．[预习导引]1．辗转相除法(1)辗转相除法，又叫欧几里得算法，是一种求两个正整数的最大公约数的古老而有效的算法．(2)辗转相除法的算法步骤S1：给定两个正整数a，b.S2：计算a除以b所得的余数r.S3:a＝b，b＝r.S4：判断r＝0是否成立，若成立，输出最大公约数a；否则返回S2.2．利用“二分法”求方程f(x)＝0在区间[a，b]上的近似解的步骤为：S1：确定解区间[a，b]和精度c；S2：取[a，b]的中点x0＝；S3：若|a－b|≥c，则进入S4；否则输出x0结束算法：S4：若f(x0)≠0，则进入S5；否则x＝x0就是方程的根，输出x0，结束算法；S5：若f(a)f(x0)>0，则解在[x0，b]，以x0替换a；若f(a)f(x0)<0，则解在[a，x0]，用x0替换b；返回S2.3．秦九韶算法把一个n次多项式f(x)＝anxn＋an－1xn－1＋…＋a1x＋a0改写成如下形式：f(x)＝(…((anx＋an－1)x＋an－2)x＋…＋a1)x＋a0，求多项式的值时，首先计算最内层括号内一次多项式的值，即v1＝anx＋an－1，然后由内向外逐层计算一次多项式的值，即v2＝v1x＋an－2，v3＝v2x＋an－3，…，vn＝vn－1x＋a0.这样，求n次多项式f(x)的值就转化为求n个一次多项式的值.要点一求两个正整数的最大公约数例1用辗转相除法求261和319的最大公约数．解319÷261＝1(余58)，261÷58＝4(余29)，58÷29＝2(余0)，所以319与261的最大公约数为29.规律方法1.利用辗转相除法求给定的两个数的最大公约数，用数对中较大的数除以较小的数，若余数不为零，则将余数和较小的数构成新的数对，再利用带余除法，直到大数被小数除尽，则这时的较小数就是原来两个数的最大公约数．2．求两个数的最大公约数也可以利用更相减损术．跟踪演练1用辗转相除法求80与36的最大公约数，并用更相减损术检验你的结果．解80＝36×2＋8，36＝8×4＋4,8＝4×2＋0，即80与36的最大公约数是4.验证：80÷2＝4036÷2＝1840÷2＝2018÷2＝920—9＝1111－9＝29－2＝77－2＝55－2＝33－2＝12－1＝11×2×2＝4所以80与36的最大公约数为4.要点二二分法例2写出用二分法求方程x2－2＝0的一个正的近似解(精度为0.005)的算法．解算法如下：S1：令f(x)＝x2－2，因为f(1)<0，f(2)>0，所以令a＝1，b＝2，c＝0.005；S2：取x0＝；S3：若|a－b|≥c，则进入S4；否则输出x0结束算法；S4：若f(x0)≠0，则进入S5；否则x＝x0就是方程的根，输出x0，结束算法；S5：若f(a)f(x0)>0，则解在[x0，b]，用x0替换a；若f(x0)f(a)<0，则解在[a，x0]，用x0替换b；返回S2.规律方法用二分法求方程的近似解的步骤：(1)画草图探索解所在的区间；(2)用二分法求符合限制条件的解；(3)编制程序用计算机完成．跟踪演练2写出用二分法求方程x3－2x－3＝0在区间[1,2]内的一个近似解(精度为0.001)的一个算法．解算法如下：S1：令f(x)＝x3－2x－3，a＝1，b＝2，c＝0.001；S2：取x0＝；S3：若|a－b|≥c，则进入S4；否则输出x0结束算法；S4：若f(x0)≠0，则进入S5；否则x＝x0就是方程的根，输出x0，结束算法；S5：若f(a)f(x0)>0，则解在[x0，b]，用x0替换a；若f(x0)f(a)<0，则解在[a，x0]，用x0替换b；返回S2.要点三秦九韶算法例3已知一个5次多项式为f(x)＝4x5＋2x4＋3.5x3－2.6x2＋1.7x－0.8，用秦九韶算法求这个多项式当x＝5时的值．解将f(x)改写为f(x)＝((((4x＋2)x＋3.5)x－2.6)x＋1.7)x－0.8，由内向外依次计算一次多项式当x＝5时的值：v0＝4；v1＝4×5＋2＝22；v2＝22×5＋3.5＝113.5；v3＝113.5×5－2.6＝564.9；v4＝564.9×5＋1.7＝2826.2；v5＝2826.2×5－0.8＝14130.2.∴当x＝5时，多项式的值等于14130.2.规律方法1.先将多项式写成一次多项式的形式，然后运算时从里到外，一步一步地做乘法和加法即可．这样比直接将x＝5代入原式大大减少了计算量．若用计算机计算，则可提高运算效率．2．注意：当多项式中n次项不存在时，可将n次项看作0·xn.跟踪演练3用秦九韶算法计...