1、11.4 算法案例算法案例 学习目标 1.通过案例， 进一步体会算法的思想； 2.理解并能利用案例中的算法解决具体问题 知识链接 (1)20 和 30 的最大公约数为 10. (2)已知函数 f(x)x22x1，计算 f(1)的值时用了 2 次乘法和 2 次加法运算；当函数变为 f(x) (x2)x1，求 f(1)时，用了 1 次乘法运算和 2 次加法运算 预习导引 1辗转相除法 (1)辗转相除法， 又叫欧几里得算法， 是一种求两个正整数的最大公约数的古老而有效的算法 (2)辗转相除法的算法步骤 S1：给定两个正整数 a，b. S2：计算 a 除以 b 所得的余数 r. S3:ab，br. S
2、4：判断 r0 是否成立，若成立，输出最大公约数 a；否则返回 S2. 2利用“二分法”求方程 f(x)0 在区间a，b上的近似解的步骤为： S1：确定解区间a，b和精度 c； S2：取a，b的中点 x0ab 2 ； S3：若|ab|c，则进入 S4；否则输出 x0结束算法： S4：若 f(x0)0，则进入 S5；否则 xx0就是方程的根，输出 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)anxnan1xn 1a 1xa0改写成如下形式
3、： f(x)(anxan1)xan2)xa1)xa0， 求多项式的值时，首先计算最内层括号内一次多项式的值，即 v1anxan1，然后由内向外 逐层计算一次多项式的值，即 v2v1xan2，v3v2xan3，vnvn1xa0. 这样，求 n 次多项式 f(x)的值就转化为求 n 个一次多项式的值. 题型一 求两个正整数的最大公约数 例 1 用辗转相除法求 261 和 319 的最大公约数 解 319 2611(余 58)， 261 584(余 29)， 58 292(余 0)， 所以 319 与 261 的最大公约数为 29. 规律方法 1.利用辗转相除法求给定的两个数的最大公约数，用数对中较
4、大的数除以较小的 数，若余数不为零，则将余数和较小的数构成新的数对，再利用带余除法，直到大数被小数 除尽，则这时的较小数就是原来两个数的最大公约数 2求两个数的最大公约数也可以利用更相减损术 跟踪演练 1 用辗转相除法求 80 与 36 的最大公约数，并用更相减损术检验你的结果 解 803628， 36844,8420， 即 80 与 36 的最大公约数是 4. 验证： 80 240 36 218 40 220 18 29 20911 1192 927 725 523 321 211 1224 所以 80 与 36 的最大公约数为 4. 题型二 二分法 例 2 写出用二分法求方程 x220 的
5、一个正的近似解(精度为 0.005)的算法 解 算法如下： S1：令 f(x)x22，因为 f(1)0，所以令 a1，b2，c0.005； S2：取 x0ab 2 ； S3：若|ab|c，则进入 S4；否则输出 x0结束算法； S4：若 f(x0)0，则进入 S5；否则 xx0就是方程的根，输出 x0，结束算法； S5：若 f(a) f(x0)0，则解在x0，b，用 x0替换 a；若 f(x0)f(a)0，则解在x0，b，用 x0替换 a；若 f(x0)f(a)0，则解在a，x0，用 x0替换 b； 返回 S2. 题型三 秦九韶算法 例 3 已知一个 5 次多项式为 f(x)4x52x43.5
6、x32.6x21.7x0.8，用秦九韶算法求这个 多项式当 x5 时的值 解 将 f(x)改写为 f(x)(4x2)x3.5)x2.6)x1.7)x0.8， 由内向外依次计算一次多项式当 x5 时的值： v04； v145222； v22253.5113.5； v3113.552.6564.9； v4564.951.72826.2； v52826.250.814130.2. 当 x5 时，多项式的值等于 14130.2. 规律方法 1.先将多项式写成一次多项式的形式，然后运算时从里到外，一步一步地做乘法 和加法即可这样比直接将 x5 代入原式大大减少了计算量若用计算机计算，则可提高运 算效率
7、2注意：当多项式中 n 次项不存在时，可将 n 次项看作 0 xn. 跟踪演练 3 用秦九韶算法计算多项式 f(x)6x54x4x32x29x，当 x5 时的值时， 需要 做加法(或减法)与乘法运算的次数分别为( ) A5,4 B5,5 C4,4 D4,5 答案 D 解析 n 次多项式需进行 n 次乘法；若各项均不为零，则需进行 n 次加法，缺一项就减少一 次加法运算f(x)中无常数项，故加法次数要减少一次，为 514.故选 D. 课堂达标 1有关辗转相除法下列说法正确的是( ) A它和更相减损之术一样是求多项式值的一种方法 B基本步骤是用较大的数 m 除以较小的数 n 得到除式 mnqr，直
8、至 rn 为止 C基本步骤是用较大的数 m 除以较小的数 n 得到除式 mqnr(0rn)反复进行，直到 r 0 为止 D以上说法皆错 答案 C 2两个整数 490 和 910 的最大公约数是( ) A2B10C30D70 答案 D 解析 9104901420,490420170,420706， 490 与 910 的最大公约数是 70. 3用秦九韶算法求多项式 f(x)7x66x53x22 当 x4 时的值时，先算的是( ) A4416B7428 C44464D74634 答案 D 解析 因为 f(x)anxnan1xn 1a 1xa0 (anxan1)xan2)xa1)xa0， 所以用秦九
9、韶算法求多项式 f(x)7x66x53x22 当 x4 时的值时， 先算的是 74634. 4用辗转相除法求得 375 和 85 的最大公约数为 答案 5 解析 37585435， 8535215， 351525， 15530. 375 与 85 的最大公约数为 5. 5用更相减损术求 36 与 134 的最大公约数，第一步应为 答案 先除以 2，得到 18 与 67 解析 36 与 134 都是偶数，第一步应为：先除以 2，得到 18 与 67. 课堂小结 1求两个正整数的最大公约数的问题，可以用辗转相除法，也可以用更相减损术用辗转相 除法，即根据 anbr 这个式子，反复相除，直到 r0 为止；用更相减损术，即根据 r|a b|这个式子，反复相减，直到 r0 为止 2秦九韶算法的关键在于把 n 次多项式转化为一次多项式，注意体会递推的实现过程，实施 运算时要由内向外，一步一步执行.