算法案例辗转相除法与更相减损术秦九韶算法与进位制第一课时课件-数学高一必修3第一章算法初步1.3人教A版.ppt

第一章 算法初步 1.3 算法案例 （辗转相除法与更相减损术 ,秦九韶算法与进位制） 1.理解辗转相除法与更相减损术求最大公约数的方法 . 2.理解秦九韶算法中求多项式的值的步骤原理 . 3.能利用除 k 取余法把十进制数化为 k 进制数 . 1.辗转相除法的算法步骤 第一步，给定两个正整数 m， n(mn). 第二步，计算 _除以 _所得的 _数 r. 第三步， m n， n r. 第四步，若 r 0，则 m， n 的最大公约数等于 _；否 则，返回第二步 . m n 余 n 2.更相减损术的算法步骤 第一步，任意给定两个正整数，判断它们是否都是偶数 .若 是用 2 约简；若不是，执行第二步 . 第二步，以较大的数减去较 小的数，接着把所得的差与 _比较，并以大数减小数 .继续这个操作，直到所得的数 _为止，则这个数 (等数 )或这个数与约简的数的乘积就 是所求的最大公约数 . 较小的数 相等 3.秦九韶算法 把一个 n次多项式 f(x) anxn an 1xn 1 a1x a0改写 成如下形式： (anxn 1 an 1xn 2 a1)x a0 f(x) anxn an 1xn 1 a1x a0 _ (anxn 2 an 1xn 3 a2)x a1)x a0 _. ( (anx an 1)x an 2)x a1)x a0 求多项式的值时，首先计算最内层括号内的一次多项式的 值，即 v1 anx an 1，然后由内向外逐层计算一次多项式的值， 即： n 这样，求 n 次多项式 f(x)的值就转化为求 _个一次多项 式的值 . v1 anx an 1， v2 _， v3 v2x an 3， vn _， v1x an 2 vn 1x a0 4.进位制 (1)k进制数 anan 1 a1a0(k)转化为十进制数为 _. (2)把十进制数化为 k 进制数用“ _”，即把所给 的十进制数除以 _，得到商数和余数，再用商数除以 k， 得到商数和余数，直到商数为 _ ，把上面各步所得的 _从右到左排列，即得到 k 进制数 . 除 k 取余 法 k 0 余数 ankn an 1kn 1 a1k a0 【 问题导思 】 1如何求 18与 54的最大公约数？ 【 提示 】 短除法 2 要求 6 750与 3 492的最大公约数，上述法还好用吗？ 【 提示 】 数值太大，短除法不方便用 知识 1 求两个正整数最大公约数的算法 (1)更相减损之术 (等值算法 ) 用两个数中较大的数减去较小的数，再用 和 构成新的一对数，对这一对数再用 减 ，以同样的操作一直做下去，直 到产生 ，这个数就是最大公约数 (2)辗转相除法 (欧几里得算法 ) 用较大的数除以较小的数所得的 和 _构成新的一对数，继续做上面的除法，直到 ，这个较小的数就是最大公约数 . 差数 较小的数 大 数 小数 一对相等的数 余数 较小的数 大数被小数除尽 【 问题导思 】 1怎样计算多项式 f(x) x5 x4 x3 x2 x 1当 x 5时 的值呢？统计所做的计算的种类及计算次数分别是什么？ 【 提示 】 f(5) 55 54 53 52 5 1 3 906.根据我 们的计算统计可以得出我们共需要 10次乘法运算， 5次加法 运算 知识 2 秦九韶算法 2我们把多项式变形为 f(x) x2(1 x(1 x(1 x) x 1， 再统计一下计算当 x 5时的计算的种类及计算次数分别是什 么？ 【 提示 】 从里往外计算仅需 4次乘法和 5次加法运算即 可得出结果 (1)把一元 n次多项式 P(x) anxn an 1xn 1 a1x a0 改写为 P(x) anxn an 1xn 1 a1x a0 (anxn 1 an 1xn 2 a1)x a0 (anxn 2 an 1xn 3 a2)x a1)x a0 ( (anx an 1)x an 2)x a1)x a0， 令 vk ( (anx an 1)x an (k 1)x an k， 则递推公式为 v 0 a n v k v k 1 x a n k 其中 k 1 ， 2 ， ， n. (2)计算 P(x0)的方法 先计算 ，然后 逐层计算， 直到 ，然后加上 最内层括号 由内向外 最外层括号 常数项 知识 3 进位制 进位制是一种记数方式，用有限的数字在不同的位置表示 不同的数值 .使用数字符号的个数称为基数，基数为 n，即称为 n 进位制，简称 n 进制 .现在最常用的是十进制，通常使用 10 个 阿拉伯数字 0 9 进行记数 . 例 1 .分别用辗转相除法和等值算法求 319和 261的最大公 约数 【 分析 】 使用辗转相除法可依据 m nq r，反复执行， 直到 r 0为止；用等值算法是根据 m n r，直到 n 1为 止 【 解析 】 辗转相除法： 319 261 1(余 58)， 261 58 4(余 29)， 58 29 2(余 0) 所以 319与 261的最大公约数是 29. 等值算法： 319 261 58， 261 58 203， 203 58 145， 145 58 87， 87 58 29， 58 29 29. 即 (319， 261)(261， 58)(203， 58)(145， 58)(87， 58)(58， 29)(29， 29) 所以 319与 261的最大公约数是 29. 1利用 “ 等值算法 ” 求给定的两个数的最大公约数， 即多次利用减法，用数对中较大的数减去较小的数，直到相 减的差与数对中较小的数相等为止 2更相减损之术的步骤： (1)判断两数是否都为偶数，若是，则都除以 2直到所得 两数不全为偶数 (2)用较大的数减去较小的数，将差和较小的数构成一对 新数，继续用较大数减去较小数，重复执行 (3)当差和较小数相等时，结束执行，此时差 (或较小数 ) 为不全为偶数的两数的最大公约数 用 “ 等值算法 ” (更相减损之术 )求下列两数的最大公约 数 (1)98， 280； (2)72， 168. 【 解 】 (1)(98， 280)(98， 182)(98， 84)(14， 84)(14， 70)(14， 56)(14， 42)(14， 28)(14， 14) 最大公约数为 14. (2)(72， 168)(72， 96)(72， 24)(48， 24)(24， 24) 最大公约数为 24. 例 2. 用秦九韶算法计算多项式 f(x) x6 12x5 60 x4 160 x3 240 x2 192x 64当 x 2时的值 【 分析 】 改写多项式 确定 v 0 依次计算 v i 求 f （ 2 ） 【 解析 】 将 f(x)改写为 f(x) (x 12)x 60)x 160)x 240)x 192)x 64， 由内向外依次计算一次多项式当 x 2时的值 v0 1， v1 1 2 12 10， v2 10 2 60 40， v3 40 2 160 80， v4 80 2 240 80， v5 80 2 192 32， v6 32 2 64 0. f(2) 0，即 x 2时，原多项式的值为 0. 1用秦九韶算法计算多项式的值时，要正确将多项式 的形式进行改写，然后由内向外依次计算当多项式函数中 间出现空项式，要以系数为零的齐次项补充 2秦九韶算法的步骤： 【 变式训练 】 利用秦九韶算法计算多项式 f(x) 11 5x 3x2 7x3 在 x 23 的值时，不会用到下列哪个值 ( ) D A.161 B.3772 C.86 641 D.85 169 解析： f(x) 11 5x 3x2 7x3 (7x 3)x 5x 11. 所以当 x 23时， v0 7； v1 7 23 3 161 3 164； v2 164 23 5 3772 5 3767； v3 3767 23 11 86 641 11 86 652. 例 3. 求 324， 243， 270三数的最大公约数 【 分析 】 先求 324和 243的最大公约数，再求这个数与 270的最大公约数 【 解析 】 (324， 243)(243， 81)(162， 81)(81， 81) 则 324与 243的最大公约数为 81. 又 (270， 81)(189， 81)(108， 81)(81， 27)(54， 27)(27， 27) 则 270与 81的最大公约数为 27， 故 324， 243， 270三数的最大公约数为 27. 求三个数的最大公约数，可先求两个数的最大公约数 a， 再求 a与第三个数的最大公约数 b，则 b为所求的三个数的最 大公约数该题的解法可推广到求 n个数的最大公约数 用更相减损之术求 27 090， 21 672， 8 127的最大公约 数 【 解 】 先求 27 090与 21 672的最大公约数 (27 090， 21 672)(21 672， 5 418)(16 254， 5 418)(10 836， 5 418)(5 418， 5 418) 27 090与 21 672的最大公约数是 5 418. 再求 5 418与 8 127的最大公约数 (8 127， 5 418)(2 709， 5 418)(2 709， 2 709) 5 418与 8 127的最大公约数为 2 709. 27 090， 21 672， 8 172的最大公约数为 2 709. 类型 4 进制数 之间的转化 例 4.(1)将 101 111 011(2)转化为十进制数； (2)将 1231(5)转化为七进制数 . 【 分析 】 k进制数 anan 1 a2a1a0(k)(0aik)转化为十进制数： anan 1 a2a1a0(k) an kn an 1 kn 1 a2 k2 a1 k a0 1.要将 k进制数转化为 n进制数 (n， k10)， 可先将 k 进制 数转化为十进制数 ， 然后再转化为所求的 n进制数 . 【 解析 】 (1)101 111 011(2) 1 28 0 27 1 26 1 25 1 24 1 23 0 22 1 21 1 20 379(10). (2)1231(5) 1 53 2 52 3 5 1 191(10)， 1231(5) 362(7). 【 变式训练 】 3.填空： 248 130 (1)11 111 000(2) _(10)； (2)154(6) _(7). 名称 辗转相除法 更相减损术 区别 以除法为主 两个整数的差较大 时，运算次数减少 余数为 0 时结束 以减法为主 两个整数的差较大时， 运算次数多 两数相等时结束 联系 都是求最大公约数的方法 都用到递推方法 都用循环结构来实现 1.辗转相除法与更相减损术求最大公约数的区别与联系 . 2.秦九韶算法的优点 . (1)减少乘法运算的次数 . (2)规律性强，便于利用循环语句实现 . (3)不用对 x 做幂的运算，每 次都是计算一个一次多项式的 值，提高了计算精度 . 3.进位制 对于任何一个数，我们可以用不同的进位制来表示 .比如： 十进数 57，可以用二进制表示为 111 001，也可以用八进制表 示为 71，用十六进制表示为 39，它们所代表的数值都是一样的 . 表示各种进制数时，一般要在数字右下角加注来表示 .如 111 001(2)表示二进制数， 34(5)表示五进制数 .电子计算机一般都 使用二进制 . 1 用更相减损之术可求得 78与 36的最大公约数是 ( ) A 24 B 18 C 12 D 6 【 解析 】 78 36 42， 42 36 6， 36 6 30， 30 6 24， 24 6 18， 18 6 12， 12 6 6， 6为 78与 36的 最大公约数 【 答案 】 D 2用秦九韶算法计算 f(x) 6x5 4x4 x3 2x2 x3 2x2 9x，需要加法 (或减法 )与乘法运算的次数分别为 ( ) A 5， 4 B 5， 5 C 4， 4 D 4， 5 【 解析 】 n次多项式当最高次项的系数不为 1时，需进 行 n次乘法；若各项均不为零，则需进行 n次加法，缺一项就 减少一次加法运算 f(x)中无常数项，故加法次数要减少一次， 为 5 1 4. 【 答案 】 D 3用更相减损之术求 81与 135的最大公约数时，要进行 _次减法运算 【 解析 】 135 81 54， 81 54 27， 54 27 27， 共进行了 3次减法运算 【 答案 】 3 4.将二进制数 101 101(2)化为八进制数，结果为 _ 【 解析 】 101 101(2) 1 25 0 24 1 23 1 22 0 2 1 32 8 4 1 45. 101 101(2) 55(8) 【 答案 】 55(8) 5求当 x 2时， f(x) x5 5x4 x3 1的函数值 【 解 】 f(x) x5 5x4 x3 1 (x 5)x 1)x 0)x 0)x 1，利用公式有 v0 1， v1 1 2 5 3， v2 ( 3) 2 1 5， v3 ( 5) 2 0 10， v4 ( 10) 2 0 20， v5 ( 20) 2 1 41， f(2) 41.