高中数学 第一章 算法初步 1.3 算法案例课件 新人教A版必修3.ppt

1 3算法案例 知识提炼 1 辗转相除法与更相减损术 1 辗转相除法 辗转相除法 又叫 算法 是一种求两个正整数的 的古老有效的算法 欧几里得 最大公约数 程序inputm ndor m nn rloopuntilr 0printmend mmodn 2 更相减损术 我国古代数学专著 九章算术 中介绍的一种求两个正整数的 的算法 运算过程第一步 任意给定两个正整数 判断它们是否都是偶数 若是 若不是 执行第二步 最大公约数 用2约简 第二步 以较大的数减去较小的数 接着把所得的差与 比较 并以大数减小数 继续这个操作 直到所得的数 为止 则这个数 等数 或这个数与约简的数的乘积就是所求的最大公约数 较小的数 相等 2 秦九韶算法 n个一次多项式 3 进位制及进位制之间的互化 1 进位制 概念 进位制是为了 而约定的记数系统 满几进一 就是几进制 基数 几进制的基数就是 计数和运算方便 几 2 不同进位制之间的互化 k进制化为十进制的方法 anan 1 a1a0 k an an 1 a1 a0 n 0 an k 0 an 1 a1 a0 k 十进制化为k进制的方法 an kn an 1 kn 1 a1 k a0 除k取余法 即时小测 1 思考下列问题 1 实际应用更相减损术时要做的第一步工作是什么 提示 先判断a b是否为偶数 若是 都除以2再进行 2 任何进位制中都要用到的数字是什么 提示 0和1 2 将101111011 2 转化为十进制的数为 a 376 10 b 377 10 c 378 10 d 379 10 解析 选d 101111011 2 1 28 0 27 1 26 1 25 1 24 1 23 0 22 1 21 1 20 379 10 3 用更相减损术可求得78与36的最大公约数是 a 3b 4c 6d 12 解析 选c 78 39 2 36 18 2 39 18 21 21 18 3 18 3 15 15 3 12 12 3 9 9 3 6 6 3 3 因此最大公约数为2 3 6 4 利用辗转相除法求3869与6497的最大公约数时 第二步是 解析 第一步 6497 3869 1 2628第二步 3869 2628 1 1241 答案 3869 2628 1 1241 5 已知多项式f x 1 x 0 5x2 0 16667x3 0 04167x4 0 00833x5 用秦九韶算法求得f 0 2 解析 根据秦九韶算法 把多项式改写成如下形式 f x 0 00833x 0 04167 x 0 16667 x 0 5 x 1 x 1 按照从内到外的顺序依次计算一次多项式当x 0 2时的值 v0 0 00833 v1 0 00833 0 2 0 04167 0 040004 v2 0 040004 0 2 0 16667 0 1586692 v3 0 1586692 0 2 0 5 0 46826616 v4 0 46826616 0 2 1 0 906346768 v5 0 906346768 0 2 1 0 8187306464 所以当x 0 2时 多项式的值为0 8187306464 答案 0 8187306464 知识探究 知识点1辗转相除法与更相减损术观察如图所示的内容 回答下列问题 问题1 用辗转相除法求两数的最大公约数的原理是什么 问题2 用更相减损术求最大公约数应按照怎样的步骤进行 总结提升 1 辗转相除法的原理设m n是两个正整数 不妨设m n 1 用m除以n 若商为q1 余数为r1 0 r1 n 则m n q1 r1 显然若x是m和n的公约数 即x能整除m和n 则x也必然能整除r1 这样x也是n和r1的公约数 故求m和n的公约数就是求n和r1的公约数 2 用n除以r1 得n r1 q2 r2 0 r2n r1 r2 所以到某一步必然有ri ri 1 qi 2 即ri恰能被ri 1整除 这时ri 1是ri和ri 1的公约数 它也必然是ri 1和ri ri 2和ri 1 r1与r2 n和r1 m和n的最大公约数 2 更相减损术求最大公约数的程序设计 知识拓展 更相减损术与辗转相除法的区别与联系 知识点2秦九韶算法观察如图所示内容 回答下列问题 问题1 秦九韶算法的计数原理是怎样的 问题2 应按照怎样的步骤进行秦九韶算法 总结提升 1 秦九韶算法的计数原理秦九韶算法是按照从内到外的顺序依次计算求值的 设f x anxn an 1xn 1 a1x a0 则该算法先计算v1 anx an 1 再计算v2 v1x an 2 最后计算vn vn 1x a0 2 秦九韶算法的步骤 知识点3进位制观察如图所示内容 回答下列问题 问题1 进位制应如何表示 问题2 常见的进位制有哪些 总结提升 1 进位制的表示若一个数为十进制数 则其基数可以省略不写 若是其他进位制的数 在没有特别说明的前提下 其基数必须写出 常在数的右下角标明基数 2 常见的进位制 1 二进制 只使用0和1两个数字 满二进一 如1 1 10 2 2 八进制 使用0 1 2 3 4 5 6 7八个不同的数字 满八进一 如7 1 10 8 3 十六进制 使用0 1 2 3 4 5 6 7 8 9 a b c d e f这十六个不同的数码 其中a b c d e f分别代表十进制中的10 11 12 13 14 15 满十六进一 如f 1 2 e 10 16 题型探究 类型一求最大公约数 典例 1 2015 大同高一检测 用辗转相除法求378与90的最大公约数为 2 2015 衡水高一检测 用更相减损术求294与84的最大公约数时 需做减法的次数是 3 求104与65的最大公约数 解题探究 1 典例1中应将两数怎样进行相除 提示 应将294除以84 用较大的数除以较小的数依次进行 2 典例2中应用更相减损术时要做的第一步工作是什么 提示 由于294与84都是偶数 因此应先将两数都除以2再进行 3 典例3中如何探求两数的最大公约数 提示 可采用辗转相除法或更相减损术求两数的最大公约数 解析 1 378 90 4 18 90 18 5 0 所以378与90的最大公约数是18 答案 182 因为294与84是偶数 首先除以2得到147 42 再求147与42的最大公约数147 42 105 105 42 63 63 42 21 42 21 21 共做了4次减法 答案 4 3 方法一 辗转相除法 第一步 104 65 1 65 39第二步 65 1 39 26第三步 39 1 26 13第四步 26 2 13 0所以104和65的最大公约数为13 方法二 更相减损术 由于65不是偶数 把104和65以大数减小数 并辗转相减 即104 65 39 65 39 26 39 26 13 26 13 13 所以104和65的最大公约数为13 方法技巧 1 辗转相除法的算法步骤第一步 输入两个正整数m n m n 第二步 计算m除以n所得的余数r 第三步 m n n r 第四步 若r 0 则m n的最大公约数等于m 否则 返回第二步 第五步 输出最大公约数m 2 更相减损术的求解步骤第一步 给定两个正整数m n m n且m n不全是偶数 第二步 计算m n所得的差k 第三步 比较n与k的大小 其中大者用m表示 小者用n表示 第四步 若m n 则m n的最大公约数等于m 否则 返回第二步 拓展延伸 三个数的最大公约数的求解方法 1 从三个数中任取两个数 用辗转相除法或更相减损术求它们的最大公约数 2 根据辗转相除法或更相减损术求所求得的最大公约数和第三个数的最大公约数 3 求得的最大公约数即为这三个数的最大公约数 变式训练 1 用辗转相除法求225和135的最大公约数 2 用更相减损术求1734 816的最大公约数 解析 1 225 135 1 90 135 90 1 45 90 45 2 所以45是225和135的最大公约数 2 因为两数皆为偶数 首先除以2得到867 408 再求867与408的最大公约数 867 408 459 459 408 51 408 51 357 357 51 306 306 51 255 255 51 204 204 51 153 153 51 102 102 51 51 所以1734与816的最大公约数是51 2 102 类型二秦九韶算法的应用 典例 1 用秦九韶算法计算多项式f x 3x6 4x5 5x4 6x3 7x2 8x 1当x 2时的值时 需要做乘法和加法的次数分别是 a 6 6b 5 6c 5 5d 6 52 用秦九韶算法求多项式f x 8x7 5x6 3x4 2x 1 当x 2时的值 解题探究 1 典例1中多项式的最高次数是几 多少项相加 2 典例2中不含x5 x3及x2项怎么办 探究提示 1 典例1中多项式的最高次数是6 共7项相加 2 先把多项式f x 8x7 5x6 3x4 2x 1变形为f x 8x7 5x6 0 x5 3 x4 0 x3 0 x2 2x 1 解析 1 选a 由秦九韶算法将多项式改成如下形式 f x 3x 4 x 5 x 6 x 7 x 8 x 1 按由内到外的顺序 依次计算x 2时的值 v0 3 v1 3 2 4 10 v2 10 2 5 15 v3 15 2 6 36 v4 36 2 7 65 v5 65 2 8 138 v6 138 2 1 277 这样求多项式的值时 是通过求6个一次多项式的值得到的 故进行了6次乘法和6次加法 2 根据秦九韶算法 把多项式改写成如下形式 f x 8x7 5x6 0 x5 3 x4 0 x3 0 x2 2x 1 8x 5 x 0 x 3 x 0 x 0 x 2 x 1 而x 2 所以有v0 8 v1 8 2 5 21 v2 21 2 0 42 v3 42 2 3 87 v4 87 2 0 174 v5 174 2 0 348 v6 348 2 2 698 v7 698 2 1 1397 所以当x 2时 多项式的值为1397 延伸探究 典例2中需要做乘法和加法的次数是多少 解析 根据秦九韶算法 把多项式改写成如下形式 f x 8x7 5x6 0 x5 3 x4 0 x3 0 x2 2x 1 8x 5 x 0 x 3 x 0 x 2 x 1 而x 2 所以有v0 8 v1 8 2 5 21 v2 21 2 0 42 v3 42 2 3 87 v4 87 2 0 174 v5 174 2 0 348 v6 348 2 2 698 v7 698 2 1 1397 所以当x 2时 多项式的值为1397 这样求多项式的值时 是通过求7个一次多项式的值得到的 故进行了7次乘法和7次加法 方法技巧 应用秦九韶算法计算多项式的值应注意的问题 1 要正确将多项式的形式进行改写 2 计算应由内向外依次计算 3 当多项式函数中间出现空项时 要以系数为零的齐次项补充 变式训练 1 已知f x x5 2x3 3x2 x 1 应用秦九韶算法计算当x 3时 v2的值为 a 27b 11c 109d 362 2015 福州高一检测 用秦九韶算法写出当x 3时f x 2x5 4x3 3x2 5x 1的值 解析 1 选b 将多项式改写成如下形式 f x x 0 x 2 x 3 x 1 x 1 由内向外依次计算 v0 1 v1 1 3 0 3 v2 3 3 2 11 2 因为f x 2x 0 x 4 x 3 x 5 x 1 v0 2 v1 2 3 0 6 v2 6 3 4 14 v3 14 3 3 45 v4 45 3 5 130 v5 130 3 1 391 所以f 3 391 类型三进位制及其转化 典例 1 2015 抚顺高一检测 把二进制数101101 2 化为十进制数为 2 将十进制数458转化为四进制数为 3 比较85 9 和210 6 的大小 解题探究 1 典例1中二进制数右数第i位数字ai化为十进制数是什么数 提示 ai 2i 1 2 典例2中应按照怎样的方法将458转化为四进制的数 提示 用4连续去除该十进制数得到商 直到商为零为止 然后把每次所得的余数倒着排成一个数 就是相应的四进制数 3 典例3中比较85 9 和210 6 的大小的关键是什么 提示 比较这两个数的关键是统一进位制 可将两个数转化为十进制数进行比较 解析 1 101101 2 1 25 0 24 1 23 1 22 0 21 1 20 32 8 4 1 45 所以二进制数101101 2 转化为十进制的数为45 答案 45 2 458 13022 4 答案 13022 4 3 因为85 9 5 8 9 77 210 6 0 1 6 2 62 78 而78 77 所以210 6 85 9 延伸探究 1 改变问法 把典例2中的数转化成六进制的数 结果如何 解析 458 2042 6 2 改变问法 把典例2中的数转化成八进制的数 结果如何 解析 所以458 712 8 方法技巧 十进制数转化为其他进制数的方法步骤 补偿训练 将235 7 转化为八进制数 解题指南 先将非十进制数转化为十进制数 再向其他k进制数转化 注意十进制数的中间作用 解析 235 7 2 72 3 7 5 70 124 10 所以124 10 174 8 即235 7 174 8 延伸探究 1 变换条件 若将 235 7 变为 235