1、第11章 算法初步11.4 算法案例第11章 算法初步 1.理解辗转相除法与秦九韶算法的含义，了解其执行过程.2.掌握用算法解决实际问题.栏目导引探究案讲练互动应用案巩固提升预习案自主学习第11章 算法初步1.辗转相除法所 谓 辗 转 相 除 法，就 是 对 于 给 定 的 两 个 正 整 数，用_ 除 以 _.若 余 数 不 为 零，则 将_构成新的一对数，继续上面的除法，直到大数被小数除尽，则这时_就是原来两个数的最大公约数.较大数较小数余数和较小数较小数栏目导引探究案讲练互动应用案巩固提升预习案自主学习第11章 算法初步伪代码如下：INPUT a，bDO ra MOD b ab brLO
2、OP UNTIL r0PRINT aEND栏目导引探究案讲练互动应用案巩固提升预习案自主学习第11章 算法初步2.秦九韶算法秦九韶算法其实质是通过一次式的反复计算，逐步得出高次多项式的值，对于一个 n 次多项式，最多只需做 n 次乘法和 n 次加法即可.伪代码如下：栏目导引探究案讲练互动应用案巩固提升预习案自主学习第11章 算法初步INPUT“n”；nINPUT“an”；aINPUT“x”；xvakn1WHILE k0PRINT“k”；kINPUT“ak”；avv*xakk1WENDPRINT vEND栏目导引探究案讲练互动应用案巩固提升预习案自主学习第11章 算法初步1.判断正误.(对的打“
3、”，错的打“”)(1)求两个正整数的最大公约数可以用辗转相除法.()(2)利用秦九韶算法计算时，乘法运算与加法运算次数相等.()栏目导引探究案讲练互动应用案巩固提升预习案自主学习第11章 算法初步2.用秦九韶算法计算多项式 f(x)3x64x55x46x37x28x1 当 x0.4 时的值时，需要做乘法和加法的次数分别是()A.6，6B.5，6C.5，5D.6，5答案：A栏目导引探究案讲练互动应用案巩固提升预习案自主学习第11章 算法初步3.“辗转相除法”与“更相减损术”有何区别？解：辗转相除法的操作过程是先用两个数中较大的数除以较小的数，得商和余数；再用除数除以余数，重复操作，直到出现余数为
4、零，则这个最小除数就是两个数的最大公约数；而更相减损术是用较大数减去较小数，再把差与较小数作为一对相减直至差相等为止，则这个等数就是所求的最大公约数.栏目导引探究案讲练互动应用案巩固提升预习案自主学习第11章 算法初步 辗转相除法 利用辗转相除法求 46，115 和 276 的最大公约数.【解】求三个数的最大公约数，可以先求两个数的最大公约数，然后求第三个数与前两个数的最大公约数.276211546，11524623，46232，所以 276 与 115 的最大公约数为 23.又 46 与 23 的最大公约数为 23，所以 46、115 和 276 的最大公约数为 23.栏目导引探究案讲练互动
5、应用案巩固提升预习案自主学习第11章 算法初步利用辗转相除法求给定的两个数的最大公约数，即利用带余除法，用数对中较大的数除以较小的数，若余数不为零，则将余数和较小的数构成新的数对，再利用带余除法，直到大数被小数除尽，则这时的较小数就是原来两个数的最大公约数.栏目导引探究案讲练互动应用案巩固提升预习案自主学习第11章 算法初步 1.378 与 90 的最大公约数为_.解析：辗转相除法：37890418，901850，所以 378 与 90 的最大公约数是 18.答案：18栏目导引探究案讲练互动应用案巩固提升预习案自主学习第11章 算法初步 二分法 写出用二分法求方程 x32x30 在区间1，2内
6、的一个近似解(误差不超过 0.001)的一个算法.栏目导引探究案讲练互动应用案巩固提升预习案自主学习第11章 算法初步【解】算法如下：S1：令 f(x)x32x3，a1，b2，c0.001；S2：取 x0ab2；S3：若|ab|c，则进入 S4；否则输出 x0 结束算法；S4：若 f(x0)0，则进入 S5；否则 xx0 就是方程的根，输出 x0，结束算法；S5：若 f(x0)f(a)0，则解在x0，b中，用 x0 替换 a；若 f(x0)f(a)0，则解在a，x0中，用 x0 替换 b，返回 S2.栏目导引探究案讲练互动应用案巩固提升预习案自主学习第11章 算法初步用二分法求方程的近似解的步
7、骤(1)画草图探索解所在的区间；(2)用二分法求符合限制条件的解；(3)编制伪代码用计算机完成.栏目导引探究案讲练互动应用案巩固提升预习案自主学习第11章 算法初步 2.写出用二分法求方程 x220 的一个正的近似解(误差不超过 0.005)的算法.解：算法如下：S1：令 f(x)x22，因为 f(1)0，所以令 a1，b2，c0.005；S2：取 x0ab2；栏目导引探究案讲练互动应用案巩固提升预习案自主学习第11章 算法初步S3：若|ab|c，则进入 S4；否则输出 x0 结束算法；S4：若 f(x0)0，则进入 S5；否则 xx0 就是方程的根，输出 x0，结束算法；S5：若 f(a)f
8、(x0)0，则解在x0，b，用 x0 替换 a；若 f(x0)f(a)0，则解在a，x0，用 x0 替换 b；返回 S2.栏目导引探究案讲练互动应用案巩固提升预习案自主学习第11章 算法初步 秦九韶算法 用秦九韶算法计算多项式 f(x)x612x560 x4160 x3240 x2192x64 当 x2 时的值.【解】将 f(x)改写为 f(x)(x12)x60)x160)x240)x192)x64.由内向外依次计算一次多项式当 x2 时的值，v01，v1121210，v21026040，v340216080，栏目导引探究案讲练互动应用案巩固提升预习案自主学习第11章 算法初步v4802240
9、80，v580219232，v6322640，所以 f(2)0，即 x2 时，原多项式的值为 0.栏目导引探究案讲练互动应用案巩固提升预习案自主学习第11章 算法初步秦九韶算法的步骤 栏目导引探究案讲练互动应用案巩固提升预习案自主学习第11章 算法初步 3.已知 f(x)x52x33x2x1，应用秦九韶算法计算当 x3 时，v3 的值为()A.27 B11 C.109 D36栏目导引探究案讲练互动应用案巩固提升预习案自主学习第11章 算法初步解析：选 D.将多项式改写成如下形式：f(x)(x0)x2)x3)x1)x1，由内向外依次计算：v01，v11303，v233211，v3113336.选
10、 D.栏目导引探究案讲练互动应用案巩固提升预习案自主学习第11章 算法初步1.辗转相除法是当大数被小数除尽时，结束除法运算，较小的数就是最大公约数.2.用秦九韶算法可大大降低乘法的运算次数，提高了运算速度.用此方法求值，关键是正确地将所给多项式改写，然后由内向外计算，由于后项计算需用到前项结果，故应认真、细心，确保结果的准确性.栏目导引探究案讲练互动应用案巩固提升预习案自主学习第11章 算法初步(1)求两个正数的公约数，当两数差别较大时，用辗转相除法，当两数差别不大时，用更相减损术较快.(2)利用秦九韶算法计算多项式值的关键是能准确地将多项式改写，然后由内向外逐次计算.由于后项计算用到前项的结
11、果，故应认真、细心，确保每项计算结果的准确性.栏目导引探究案讲练互动应用案巩固提升预习案自主学习第11章 算法初步1.用辗转相除法求 36 与 134 的最大公约数，第一步是()A.1343698 B13433626C.先除以 2，得到 18 与 67 D134363(余 26)解析：选 B.用辗转相除法求 36 与 134 的最大公约数的第一步是计算较大数 134 除以较小数 36 的余数.栏目导引探究案讲练互动应用案巩固提升预习案自主学习第11章 算法初步2.用秦九韶算法求多项式 f(x)4x5x22 当 x3 时的值时，需要进行的乘法运算和加减运算的次数分别为()A.4，2 B5，3C.
12、5，2 D6，2解析：选 C.f(x)4x5x22(4x)x)x1)x)x2，所以需要 5 次乘法运算和 2 次加减运算.栏目导引探究案讲练互动应用案巩固提升预习案自主学习第11章 算法初步3.已知多项式 p(x)3x59x4x3kx24x11，当 x3时值为 1 616，则 k_.解析：由秦九韶算法，得 p(x)(3x9)x1)xk)x4)x11.则当 x3 时，p(3)(541)3k)34)311(4953k4)311 9k1 508 1 616，所以 k12.答案：12栏目导引探究案讲练互动应用案巩固提升预习案自主学习第11章 算法初步4.运行下面的伪代码：INPUT m，nDO rm
13、MOD n mn nrLOOP UNTIL r0PRINT mEND当输入 168，72 时，输出的结果是_.栏目导引探究案讲练互动应用案巩固提升预习案自主学习第11章 算法初步解析：这个伪代码的作用是求 m，n 的最大公约数.故 16872224，72243.所以，168 与 72 的最大公约数是 24.答案：24栏目导引探究案讲练互动应用案巩固提升预习案自主学习第11章 算法初步5.已知一个一元五次多项式为 f(x)5x52x43.5x32.6x21.7x0.8，用秦九韶算法求这个多项式当 x5 时的值.栏目导引探究案讲练互动应用案巩固提升预习案自主学习第11章 算法初步解：f(x)5x52x43.5x32.6x21.7x0.8(5x2)x3.5)x2.6)x1.7)x0.8，v155227，v22753.5138.5，v3138.552.6689.9，v4689.951.73 451.2，v53 451.250.817 255.2.所以，当 x5 时，多项式的值等于 17 255.2.栏目导引探究案讲练互动应用案巩固提升预习案自主学习第11章 算法初步栏目导引探究案讲练互动应用案巩固提升预习案自主学习第11章 算法初步本部分内容讲解结束 按ESC键退出全屏播放
