1.3.3算法案例--进位制

高二学案高二学案 1 3 3 算法案例算法案例 进位制进位制 课标要求 了解各种进位制与十进制之间转换的规律 会利用各种进位制与十进制之间的 联系进行各种进位制之间的转换 学习重点学习重点 各进位制表示数的方法及各进位制之间的转换 一 复习引入一 复习引入 在日常生活中 我们最熟悉 最常用的是十进制 据说这与古人曾以手指计 数有关 爱好天文学的古人也曾经采用七进制 十二进制 六十进制 至今我们 仍然使用一周七天 一年十二个月 一小时六十分的历法 今天我们来学习一下进 位制 二 研探新知二 研探新知 探究一探究一 进位制的概念进位制的概念 思考 1 进位制是为了计数和运算方便而约定的记数系统 如逢十进一 就是十进 制 每七天为一周 就是七进制 每十二个月为一年 就是十二进制 每 六十秒为一分钟 每六十分钟为一个小时 就是六十进制 等等 一般地 满进一 就是进制 其中称为进制的基数 那么是一个什么kkkkk 范围内的数 思考 2 十进制使用 0 9 十个数字 那么二进制 五进制 七进制分别使用哪些 数字 思考 3 在十进制中 10 表示十 在二进制中 10 表示 2 一般地 若是一个大于 1k 的整数 则以为基数的进制数可以表示为一串数字连写在一起的形式 kk 思考 4 十进制数 4528 表示的数可以写成 011knn aaaa 依此类比 二进制数 0123 108102105104 2 110011 八进制数 分别可以写成什么式子 8 7342 思考 5 一般地 如何将进制数 写成各数位上的数字与k 011knn aaaa 基数的幂的乘积之和的形式 k 思考 6 在二进制中 0 0 0 1 1 0 1 1 的值分别是多少 探究二探究二 进制化十进制的算法进制化十进制的算法k 思考 1 例 3 二进制数 110011 2 化为十进制数是什么数 思考 2 二进制数右数第 i 位数字化为十进制数是什么数 i a 思考 3 例 4 运用循环结构 把二进制数 化为十进制数 2 011 aaaaa nn b 的算法步骤如何设计 算法分析 算法分析 从例 3 的计算过程可以看出 计算 k 进制数 a 的右数第 i 位数字 ai与 ki 1的乘积 ai ki 1 再将其累加 这是一个重复操作的步骤 所以 可以 用循环结构来构造算法 算法步骤如下 第一步 输入 a k 和 n 的值 第二步 将 b 的值初始化为 0 i 的值初始化为 1 第三步 b b ai ki 1 i i 1 第四步 判断 i n 是否成立 若是 则执行第五步 否则 返回第三步 第五步 输出 b 的值 程序框图如右图 思考 6 该程序框图对应的程序如何表述 其中各个数位上的数字 n a 1 n a 的取值范围如何 1 a 0 a INPUT a k n a k n b 0 i 1 t a MOD 10 DO b b t k i 1 a a 10 t a MOD 10 i i 1 LOOP UNTIL i n PRINT b ENDEND 探究三 除探究三 除取余法取余法k 思考 1 二进制数 101101 2 化为十进制数是什么数 例 5 十进制数 89 化为二 进制数是什么数 解 解 根据二进制数 满二进一 的原则 可以用 2 连续去除 89 或所得商 然后取余 数 具体计算方法如下 因为 89 2 44 1 44 2 22 0 22 2 11 0 11 2 5 1 5 2 2 1 2 2 1 0 1 2 0 1 所以 89 2 2 2 2 2 2 1 1 0 0 1 2 2 2 2 22 1 1 0 0 1 1 26 0 25 1 24 1 23 0 22 0 21 1 20 1 011 001 2 思考 2 上述化十进制数为二进制数的算法叫做除除 2 2 取余法取余法 转化过程有些复杂 观察下面的算式你有什么发现吗 把上式中各步所得的余数从下到上排列 得到 89 1 011 001 2 思考 3 上述方法也可以推广为把十进制数化为 k 进制数的算法 称为除除取余法取余法 k 十进制数 191 化为五进制数是什么数 思考 4 根据上面分析 例 6 利用除取余法 将十进制数 a 化为进制数的算kk 法步骤如何设计 算法分析 算法分析 从例 5 的计算过程可以看出如下的规律 若十制数 a 除以 k 所得商是 q0 余数是 r0 即 a k q0 r0 则 r0是 a 的 k 进制 数的右数第 1 位数 若 q0除以 k 所得的商是 q1 余数是 r1 即 q0 k q1 r1 则 r1是 a 的 k 进制数 的左数第 2 位数 若 qn 1除以 k 所得的商是 0 余数是 rn 即 qn 1 rn 则 rn是 a 的 k 进制数的左 数第 1 位数 这样 我们可以得到算法步骤如下 第一步 给定十进制正整数 a 和转化后的数的基数 k 第二步 求出 a 除以 k 所得的商 q 余数 r INPUT a k a k b 0 i 0 DO q a k r a MOD k b b r 10 i i i 1 a q LOOP UNTIL q 0 PRINT b ENDEND 第三步 把得到的余数依次从右到左排列 第四步 若 q 0 则 a q 返回第二步 否则 输出全部余数 r 排列得到的 k 进制数 思考