《数学新设计同步人教A必修三课件：第一章 算法初步 1.3》由会员分享，可在线阅读，更多相关《数学新设计同步人教A必修三课件：第一章 算法初步 1.3（30页珍藏版）》请在金锄头文库上搜索。
1、1 3 算法案例 学习目标 1 理解辗转相除法与更相减损术的含义 了解其执行 过程 重点 2 理解秦九韶算法的计算过程 并了解它提高计算效 率的实质 重点 3 理解进位制的概念 能进行不同进位制间的转 化 重点 知识点1 辗转相除法与更相减损术 1 辗转相除法 1 辗转相除法 又叫欧几里得算法 是一种求两个正整数的 的古老而有效的算法 2 辗转相除法的算法步骤 第一步 给定两个正整数m n 第二步 计算m除以n所得的 r 第三步 m n n r 第四步 若 则m n的最大公约数等于m 否则 返回 第二步 最大公约数 余数 r 0 2 更相减损术 1 我国古代数学专著 九章算术 中介绍的一种求两
2、个正整数 的 的算法 2 运算过程 第一步 任意给定两个正整数 判断它们是否都是 若 是 用 约简 若不是 执行 第二步 以 的数减去 的数 接着把所得的差与 的数比较 并以大数减小数 继续这 个操作 直到所得的数 为止 则这个数 等数 或这个数与约简的数的乘积就 是所求的最大公约数 最大公约数 偶数 2 第二步 较大较小较小 相等 预习评价 1 用 辗转相除法 求得459和357的最大公约数是 解析 459 357 1 102 357 102 3 51 102 51 2 所以51 是102和51的最大公约数 也就是459和357的最大公约数是51 答案 51 2 用 更相减损术 求294和8
3、4的最大公约数时 需做减法的次数 是 解析 先用2约简得147 42 然后辗转相减得 147 42 105 105 42 63 63 42 21 42 21 21 故需经过4次减法运算 答案 4 知识点2 秦九韶算法 功能计算n次多项式f x anxn an 1xn 1 a1x a0的值 改写后 的形式 f x anxn an 1xn 1 a1x a0 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 的值就转化为求 的值
4、n个一次多项式 预习评价 已知f x x5 2x3 3x2 x 1 应用秦九韶算法计算x 3时 的值时 v3的值为 解析 将函数式化成如下形式 f x x 0 x 2 x 3 x 1 x 1 由内向外依次计算 v0 1 v1 1 3 0 3 v2 3 3 2 11 v3 11 3 3 36 答案 36 知识点3 进位制及进位制之间的转化 1 概念 进位制是为了 而约定的记数系统 约 定 满几进一 就是几进制 几进制的基数 大于1的整数 就是 2 不同进位制之间的转化 1 k进制化为十进制的方法 anan 1 a1a0 k an an 1 a1 a0 N 0 an k 0 an 1 a1 a0
5、k 2 十进制化为k进制的方法 计数和运算方便 几 an kn an 1 kn 1 a1 k a0 除k取余法 预习评价 把1010 4 化为十进制数为 解析 1010 4 1 43 0 42 1 41 0 40 68 答案 68 题型一 求最大公约数 例1 1 用辗转相除法计算60和48的最大公约数时 需要做 的除法次数是 A 1 B 2 C 3 D 4 解析 60 48 1 12 48 12 4 0 所以需要做的除法次数 为2 选B 答案 B 2 求325 130 270三个数的最大公约数 解 方法一 辗转相除法 因为325 130 2 65 130 65 2 所以325和130的最大公约
6、数为65 因为270 65 4 10 65 10 6 5 10 5 2 所以65和270的最大公约数为5 故325 130 270三个数的最大公约数为5 方法二 更相减损术 325 130 195 195 130 65 130 65 65 所以325和130的最大公约数是65 270 65 205 205 65 140 140 65 75 75 65 10 65 10 55 55 10 45 45 10 35 35 10 25 25 10 15 15 10 5 10 5 5 所以270与65的最大公约数为5 所以325 130 270的最大公约数为5 规律方法 求两个正整数的最大公约数的方法
7、1 利用辗转相除法求给定的两个数的最大公约数 即利用带余 除法 用数对中较大的数除以较小的数 若余数不为零 则将余 数和较小的数构成新的数对 再利用带余除法 直到大数被小数 除尽 则这时 的较小数就是原来两个数的最大公约数 2 利用更相减损术求两个正整数的最大公约数的一般步骤是 首先判断两个正整数是否都是偶数 若是 用2约简 也可以不除 以2 直接求最大公约数 这样不影响最后结果 训练1 用辗转相除法求80与36的最大公约数 并用更相减 损术检验 你的结果 解 80 36 2 8 36 8 4 4 8 4 2 0 即80与36的最大公约数是4 验证 80 2 40 36 2 18 40 2 2
8、0 18 2 9 20 9 11 11 9 2 9 2 7 7 2 5 5 2 3 3 2 1 2 1 1 1 2 2 4 所以80与36的最大公约数为4 题型二 秦九韶算法的应用 例2 用秦九韶算法求多项式f x x5 5x4 10 x3 10 x2 5x 1当x 2时的值 解 f x x5 5x4 10 x3 10 x2 5x 1 x 5 x 10 x 10 x 5 x 1 当x 2时 有 v0 1 v1 v0 x a4 1 2 5 3 v2 v1x a3 3 2 10 4 v3 v2x a2 4 2 10 2 v4 v3x a1 2 2 5 1 v5 v4x a0 1 2 1 1 故f
9、2 1 规律方法 1 秦九韶算法的步骤 2 应用秦九韶算法计算多项式的值应注意的问题 1 要正确将多项式的形式进行改写 2 计算应由内向外依次计算 3 当多项式函数中间出现空项时 要以系数为零的齐次项补 充 训练2 已知函数g x x3 2x2 5x 6 用秦九韶算法求 f 10 的值 解 由秦九韶算法 得 f x x3 2x2 5x 6 x2 2x 5 x 6 x 2 x 5 x 6 当x 10时 f 10 10 2 10 5 10 6 8 10 5 10 6 75 10 6 756 方向1 k进进制化为为十进进制 例3 1 八进制数342 8 化为十进制数为 解析 342 8 3 82 4
10、 81 2 80 226 答案 226 方向2 十进进制化为为k进进制 例3 2 将十进制数458分别转化为四进制数和六进制数 解 算式如下图 故458 13022 4 2042 6 方向3 两种非十进进制互化 例33 将八进制数127 8 化成二进制数 解 先将八进制数127 8 化为十进制数 127 8 1 82 2 81 7 80 64 16 7 87 再将十进制数87化成二进制数 所以87 1010111 2 所以127 8 1010111 2 规律方法 k进制数与十进制数互化的方法 1 k进制数转化为十进制数的方法 先把这个k进制数写成用各位上的数字与k的幂的乘积之和的形式 再按照十
11、进制的运算规则计 算出其结果 即anan 1 a2a1a0 k an kn an 1 kn 1 a2 k2 a1 k a0 需要注意的是 k的幂的 最高次数应是k进制数的位数减去1 然后逐个减小1 最后是0次 幂 2 十进制数转化为k进制数的方法 除k取余法 即先把十进制数a除以k 商为q0 余数为r0 再把q0 除以k 商为q1 余数为r1 反复进行这种除法 直到qn 1除 以k所得的商为0 余数是rn 即rn qn 1为止 此时将所有余数 按从右到左排列就得到所要求的k进制数rnrn 1 r0 k 除k取余法的注意事项 1 要连续除 用k连续去除十进制数或 所得的商 直到商为零为止 2 倒
12、着写 把各步得到的余数倒 写 即从下到上排列 就是相应的k进制数 训练3 若二进制数100y011和八进制数x03相等 求x y的 值 解 100y011 2 1 26 y 23 1 2 1 67 8y x03 8 x 82 3 64x 3 8y 67 64x 3 y可取0 1 x可以取1 2 3 4 5 6 7 y 0时 x 1 y 1时 64x 72无整数解 x y 1 课堂达标 1 更相减损术可解决下列问题中的 A 求两个正整数的最大公约数 B 求多项式的值 C 进位制的转化计算 D 排序问题 答案 A 2 把二进制数110 2 化成十进制数为 A 4 B 5 C 6 D 7 解析 11
13、0 2 1 22 1 21 0 20 6 答案 C 3 1 037和425的最大公约数是 A 51 B 17 C 9 D 3 解析 1 037 425 2 187 425 187 2 51 187 51 3 34 51 34 1 17 34 17 2 即1 037和425的最大公约数是17 答案 B 4 16化为二进制数是 解析 所以16 10 000 2 答案 10 000 2 5 已知一个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
14、 由内向外依次计算一次多项式当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 2 826 2 v5 2 826 2 5 0 8 14 130 2 当x 5时 多项式的值等于14 130 2 课堂小结 1 求两个正整数的最大公约数的问题 可以用辗转相除法 也可 以用更相减损术 用辗转相除法 即根据a nb r这个式子 反复相除 直到r 0为止 用更相减损术 即根据r a b 这个式子 反复相减 直到r 0为止 2 秦九韶算法的关键在于把n次多项式转化为一次多项式 注意 体会递推的实现过 程 实施运算时要由内向外 一步一步执行 3 把一个非十进制数转化为另一种非十进制数 通常是把这个数 先转化为十进制数 然后再利用除k取余法 把十进制数转化 为k进制数 而在使用除k取余法时要注意以下几点 1 必须除 到所得的商是0为止 2 各步所得的余数必须从下到上排列 3 切记在所求数的右下角标明基数
