人教A版必修3 1.3 算法案例 课件（30张）.ppt

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 第二步 较大 较小 较小 相等 预习评价 1 用 辗转相除法 求得459和357的最大公约数是 解析459 357 1 102 357 102 3 51 102 51 2 所以51是102和51的最大公约数 也就是459和357的最大公约数是51 答案51 2 用 更相减损术 求294和84的最大公约数时 需做减法的次数是 解析先用2约简得147 42 然后辗转相减得 147 42 105 105 42 63 63 42 21 42 21 21 故需经过4次减法运算 答案4 知识点2秦九韶算法 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 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 1b 2c 3d 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的最大公约数为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 规律方法求两个正整数的最大公约数的方法 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 20 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 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 方向1k进制化为十进制 例3 1 八进制数342 8 化为十进制数为 解析342 8 3 82 4 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的幂的乘积之和的形式 再按照十进制的运算规则计算出其结果 即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 倒着写 把各步得到的余数倒写 即从下到上排列 就是相应的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 4b 5c 6d 7解析110 2 1 22 1 21 0 20 6 答案c 3 1037和425的最大公约数是 a 51b 17c 9d 3解析 1037 425 2 187 425 187 2 51 187 51 3 34 51 34 1 17 34 17 2 即1037和425的最大公约数是17 答案b 4 16化为二进制数是 解析所以16 10000 2 答案10000 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 由内向外依次计算一次多项式当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 2826 2 v5 2826 2 5 0 8 14130 2 当x 5时 多项式的值等于14130 2 课堂小结 1 求两个正整数的最大公约数的问题 可以用辗转相除法 也可以用更相减损术 用辗转相除法 即根据a nb r这个式子 反复相除 直到r 0为止 用更相减损术 即根据r a b 这个