1、第五讲 进位制问题 1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59 61 63 65 67 69 71 73 75 77 79 81 83 85 87 89 91 93 95 97 99 101 103 105 107 109 111 113 115 117 119 121 123 125 127 2 3 6 7 10 11 14 15 18 19 22 23 26 27 30 31 34 35 38 39 42 43 46 47 50 51 54 55 58 59 62
2、63 66 67 70 71 74 75 78 79 82 83 86 87 90 91 94 95 98 99 102 103 106 107 110 111 114 115 118 119 122 123 126 127 4 5 6 7 12 13 14 15 20 21 22 23 28 29 30 31 36 37 38 39 44 45 46 47 52 53 54 55 60 61 62 63 68 69 70 71 76 77 78 79 84 85 86 87 92 93 94 95 100 101 102 103 108 109 110 111 116 117 118 119
3、 124 125 126 127 8 9 10 11 12 13 14 15 24 25 26 27 28 29 30 31 40 41 42 43 44 45 46 47 56 57 58 59 60 61 62 63 72 73 74 75 76 77 78 79 88 89 90 91 92 93 94 95 104 105 106 107 108 109 110 111 120 121 122 123 124 125 126 127 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 48 49 50 51 52 53 54 55 56 57
4、 58 59 60 61 62 63 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 1
5、15 116 117 118 119 120 121 122 123 124 125 126 127 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 年龄表年龄表 1 年龄表年龄表 2 年龄表年龄表 3 年龄
6、表年龄表 4 年龄表年龄表 5 年龄表年龄表 6 年龄表年龄表 7 年龄表年龄表 这是一个按二进制原理制作的年龄表，只要知道一 个人的年龄在哪几张表格中出现，就能够求出此人的年 龄 按照类似想法，可以制作出生日表、姓氏表等，生 日表只要用到 31 个数，姓氏表则要用到 255 个数，把每 个姓氏对应到一个到中的整数 有这样一个笑话：请问“1 1”在什么样的情况下等于 10，答： “在算错的情况下 等于 10！ ” 笑话毕竟是笑话，现实生活中一般也不会出现把1 1算错的情况不过学 习完今天的知识，同学们就知道，不用算错，1 1也是可以等于 10！说起来很奇怪， 但在二进制中就是这样的说到这里，同
7、学们可能会有疑问，什么是二进制呢？那还得 从进位制说起 一、什么是进位制 所谓“进位制”就是指进位的法则在我们已经学过的加法运算中就有一条进位法 则逢十进一由于它规定逢十 进一，所以这一进位法则又称“十进制” 生活中最 常用的就是十进制，例如 10 分钱就是 1 角，10 角钱就是 1 元；10 毫米等于 1 厘米，10 厘米等于 1 分米，10 分米等于 1 米当然，生活中也并不总是“逢十进一”，比如时 间就是 60 进制的：60 秒等于 1 分钟，60 分钟等于 1 小时再比如西方国家常用的单位 “打” ，所谓一“打”就是指 12 个，这就是一种 12 进制我国古代重量单位“斤”和 “两”
8、就是 16 进制的，常说的“半斤八两”就是指半斤和八两相当，所以一斤就是 16 两像这样的例子有很多，大家不妨自己想想，还有没有别的进位制的例子 二、怎么表示进位制 这么多进位制，究竟怎么通过写法把它们区分开来呢？一般的，如没有特殊说明， 都 默认为 10 进制 如果要表示其他进制，就必须采用括号加脚标的形式例如 5 进制 中的 1234，我们就写成51234，2 进制的 101 就写成2101 在 n 进制中，恰好会用到 n 种数字：从 0 一直到1n这里请大家注意以下两点： （1）n进制中，不可能出现数字n以及比n更大的数：如 5 进制中不可能出现数 字 5、6、7、8、9 等；反过来，如
9、果一个数中出现了数字 5 或大于 5 的数字，这个数就 一定不会是 5 进制数，如 125，733 都不可能是 5 进制数； （2）n 进制中，出现的数字可能会超出 0 到 9 这十种数字，比如 16 进制，必须逢 16 才能进 1，所以从 0 开始数到 9 之后不能进位，必须仍然用一个字符来表示数学上 约定在 16 进制种，用字母A、B、C、D、E、F来表示等于 10 进制中的 10、11、 12、13、14、15 在 n 进制种，n 也称为该进位制的“基” 三、n 进位制化十进制 十进制： 32 21012 101 100 10 1 ； 三进制： 321 3 2101231 3031 ；
10、四进制： 321 4 2101241 4041 ； 五进制： 321 5 2101251 5051 ； 例1 （1） 581216 2013（_） （_） （_） （_） （2） 10 5 2012 （_） （3） 10 12 2012 （_） 分析分析把 10 进制的数转化为其他进制，一般采用的是短除求余法，就是把 10 进制数 不断的除以进制数，保留余数，直到余数为 0 为止，然后将余数倒序写出即可；其它进 制转化成 10 进制，可以用位值原理展开求解 练习 1、 10 12 3 2A （_） 10 16 ADD （_） 12 5 2012 （_） 12 8 2012 （_） 例2 （1）
11、把三进制数 12120120110110121121 改写为九进制，它从左向右数第 1 位数字是 多少？ （2） 48 2 111011001（_） （_） 分析分析 三进制数化为九进制数除了用前面说过的以十进制为桥梁进行转化， 是否有更 简单巧妙的办法呢？ 练习 2、 9 3 120011221 （_） 例3 7 77 54536245 （_） 分析分析这是一个七进制下的加法，记住严格遵循“逢七进一”的原则，你一定能得出 正确答案 练习 3、 例4 在 6 进制中有三位数abc，化为 9 进制为cba，这个三位数在十进制中是多少？ 分析分析 怎样把题目中的两个数统一在一个进位制下， 是十进制
12、还是二进制？你是否能 根据位置原理列出不同进制下的三位数展开形式呢？ 练习 4、在 7 进制中有三位数，化为 9 进制为，这个三位数在十进制中是多 少？ 例5 一个天平， 物品必须放在左盘， 砝码必须放在右盘， 那么为了能称出 1 克到 1000 克， 至少需要多少个砝码？ 分析分析 从最小的重量 1、 2、 3克开始推理， 注意已有砝码是可以累加在一起的 例6 一本书共有 2013 页，第一天看一页书，从第二天起，每天看的页数都是以前各天的 总和如果直到最后剩下的不足以看一次时就一次看完，共需多少天？ 分析分析根据题目要求逐一列出每天所看的页码数，不断总结计算纸质得出最后答案 cba abc
13、 5 55 123123 （_） 计算机与二进制 计算机（computer）俗称电脑，是一种用于高速计算的电子计算机器，可以进行数值计 算，又可以进行逻辑计算，还具有存储记忆功能是能够按照程序运行，自动、高速处理海 量数据的现代化智能电子设备 由硬件系统和软件系统所组成，没有安装任何软件的计算机 称为裸机可分为超级计算机、工业控制计算机、网络计算机、个人计算机、嵌入式计算机 五类，较先进的计算机有生物计算机、光子计算机、量子计算机等 计算机发明者约翰冯诺依曼计算机是 20 世纪最先进的科学技术发明之一，对人 类的生产活动和社会活动产生了极其重要的影响，并以强大的生命力飞速发展 二进制是计算技术
14、中广泛采用的一种数制二进制数据是用 0 和 1 两个数码来表示的 数它的基数为 2，进位规则是“逢二进一” ，借位规则是“借一当二” ，由 18 世纪德国数 理哲学大师莱布尼兹发现当前的计算机系统使用的基本上是二进制系统 二进制是一种非常古老的进位制，由于在现代被用于电子计算机中，而旧貌换新颜变得 身价倍增起来许多人从我国伟大而神秘的周易中发现了二进制 改革开放前， 大多数中国人不知道计算机是什么东西 1980 年， 美国人第一台 8086CPU 芯片个人计算机（PC，俗称电脑）上市，80 年代初，中国出现了进口电脑一台苹果机， 价格近两万元，是普通干部工人工资的数百倍，个人根本没有能力购买9
15、0 年代以后中国 有了互联网，电脑才逐步为中国人所熟悉 近几年电脑的体积越来越小，功能越来越强大，例如最近流行的平板电脑平板电脑是 一款无须翻盖、没有键盘、大小不等、形状各异，却功能完整的电脑其构成组件与笔记本 电脑基本相同，但它是利用触笔在屏幕上书写，而不是使用键盘和鼠标输入，并且打破了笔 记本电脑键盘与屏幕垂直的 J 型设计模式它除了拥有笔记本电脑的所有功能外，还支持 手写输入或语音输入，移动性和便携性更胜一筹 平板电脑由比尔盖茨提出，至少应该是 X86 架构，从微软提出的平板电脑概念产品上看，平板电脑就是一款无须翻盖、没有键盘、 小到足以放入女士手袋，但却功能完整的 PC 课 堂 内 外
16、 作业 1. 进制互化： （1）； （2）； （3）=； （4）=； （5）； （6） 2. （1） ； （2） 3. 一个十进制三位数，其中的 a、b、c 均代表某个数码，它的二进制表达式是一 个七位数，这个十进制的三位数是多少？ 4. 一个自然数用三进制和四进制表示都为三位数， 并且它的各位数字的排列顺序恰好相反， 这个自然数用十进制表示是多少？ 5. a、b 是自然数，a 进制数 47 和 b 进制数 74 相等，a 与 b 的和的最小值是多少？ 2 1abcabc 10 abc 555 21322 4 44 202323 916 157 49 11202 5 101248 16 103
17、120 10 16 1CA10 411202 第三讲第三讲 递推计数递推计数 例题例题 例1 答案：答案：927 详解详解：将作文数量与完成作文的方法数列成一张表格，如下所示： 下面解释一下这张数表是如何累加得到的写 1、2、3 篇作文的方法数可以枚举得到写 4 篇作文的完成方法数可以分三类去数：如果第一天写 1 篇，那么参考数表可得，剩下 3 篇有 4 种完成方法； 如果第一天写 2 篇， 同样参考数表可得， 剩下 2 篇有 2 种完成方法； 如果第一天写 3 篇， 那么剩下 1 篇还有 1 种完成方法因此 4 篇作文的完成方法总数 为1247，如上表箭头所示接着分析 5 篇作文的完成方法数
18、，仍然分三类：第 一天写 1 篇，那么参考数表可得，剩下 4 篇还有 7 种完成方法；第一天写 2 篇，那么剩 下 3 篇还有 4 种完成方法；第一天写 3 篇，那么剩下 2 篇还有 2 种完成方法因此 5 篇作文的完成方法数等于24713以此类推便可填满整张表格 例2 答案：答案：28 详解详解：我们同样可以列出一个递推数列，将其表示如下： 下面详细说明该问题的递推规律 覆盖 13、 23 和 33 方格表的方法数可以枚举得 到接着分析覆盖 43 的表格有几种覆盖方法如下图所示，左上角的阴影方格在覆 盖的时候有两种方法：竖着覆盖或横着覆盖当竖着覆盖时，余下部分恰好是一个 3 3 的方格表，覆
19、盖方法数为 2；当横着覆盖时，其下方的方格只能被横放的纸片盖住， 因此只剩下一个 13 的方格表需要覆盖，方法数为 1由此可得 43 表格的方法数为 2+1=3用同样的方法分析 53 的 方格表，可得其覆盖方法数等于43的方法数加上23的方法数，因此等于 314 接着以此类推即可 例3 答案：答案：5051 余下部分是3 3的方格表，覆盖方法有 2 种 阴影方格下方的格子只能用横放的纸片盖住，因此只剩下1 3的方格表需要覆盖 方格表大小 1 3 23 3 3 43 53 63 73 8 3 93 103 覆盖方法数 1 1 2 3 4 6 9 13 19 28 作文数 1 2 3 4 5 6
20、7 8 9 10 11 12 完成方法数 1 2 4 7 13 24 44 81 149 274 504 927 详解详解：我们同样可以列出一个递推数列，将其写为如下的一张数表： 下面详细说明该递推过程平面上有 1、2、3 条直线的情形画图即可解决，我们从第 4 条直线开始分析如右图所示，当画上第 4 条直线时，会把原有的区域一分为二（如编 号为 I、II、III、IV 的 4 个区域） ，因此会增加 4 个新区域而之所以能产生 4 个新区 域，就是由于第 4 条直线会与原有的 3 条直线产生 3 个交点，而这 3 个交点会把第 4 条直线分为 4 部分， 每一部分都会位于一个原有的区域中，
21、因此每一部分都就会把原有 的某个区域一分为二，因此直线被分为几部分，区域数量自然也就增加几部分上述逻 辑关系在下方右侧有明确的表示由此可得，增加到第 n 条直线就会增加 n 个新区域， 因此答案是22341005051 例4 答案：答案：1641 详解详解：本题的方法称为“传球法” 传球法在很多问题中有着广泛的应用如右侧表格 所示，除了第“0”行外，其余每一行的数量都是由上一 行的数量通过某种规则累加得到的比如第“1”行 A 下 方的 0，就是通过第“0”行 B、C、D 的数量相加得到的； 第“3”行 B 下方的 7，就是通过第“2”行 A、C、D 的数 量相加得到的；第“4”行 C 下方的
22、20，就是通过第“5” 行 A、B、D 的数量相加得到的；第“6”行 D 下方的 182， 就是通过第“5”行 A、B、C 的数量相加得到的之所以 有这样的累加规则，就是因为 A 想拿球，必须由 B、C、D 传球给他，所以他下方的数也必须由 B、C、D 累加给他 这就是传球规则决定累加规则传球规则决定累加规则依据这一累加规则， 我们不停地将数表向下累加，每传一次球就多累加一行， 最后得到第 “8” 行 这一行的四个数分别为 1641、 1640、 1640 和 1640他们分别表示 8 次传球后，由 A、B、C、D 拿球的传球方法数由于题 目要求最后球回到 A 手中，因此答案为 1641 种
23、第 4 条 I II III IV I II III IV 增加第 n 条直线 产生1n 个交点 第 n 条直线被分成 n 部分 直线的每一部分 都分出一个新区域 增加 n 个新区域 直线数量 1 2 3 4 5 100 平面被分成的区域2 4 7 11 16 5051 2 3 5 100 4 A B C D 0 1 0 0 0 1 0 1 1 1 2 3 2 2 2 3 6 7 7 7 4 21 20 20 20 5 60 61 61 61 6 183 182 182 182 7 546 547 547 547 8 1641 1640 1640 1640 例5 答答案案：1224 详解详解：
24、我们把这个七位数看作是 1、2、3 三个人之间传 6 次球的一个传球顺序，具体的传球规则是：1 能传球给 2、 3，但不能给自己；2、3 都能传球给 1、2、3依据“传球 规则决定累加规则” ，我们可以列出如右表所示的一张递推 表格表格的第“0”行是发球行，对应的是这个七位数的 首位数字由于 1、2、3 都能作首位，因此第“0”行写的 都是 1接着按照传球规则累加即可表格中第“6”行（最 后一行）中的三个数分别表示第六次传球后，球在 1、2、3 手中的方法数，对于七位数而言，就是表示分别以 1、2、3 结尾的符合题意的七位数有多少个所以最后答案应该把 它们全加起来，等于 328+448+448
25、=1224 例6 答案：答案：42 详解详解：我们依照连续偶数的次序进行递推累加 （1）圆周上有 2 个点，只有 1 种连法 （2）圆周上有 4 个点，只有 2 种连法 （3）圆周上有 6 个点 A1、A2、A3、A4、A5、A6（如下左图） ，那么与 A1相连 的点只能是 A2、A4或 A6依次分三类情况讨论：第一，A1连 A2，剩下 4 个点连法数为 2；第二，A1 连 A4，剩下 4 个点连法数为 1；第三，A1连 A4，剩下 4 个点连法数也为 2由此可得，6 个点共有 5 种不同的连法 （4）如果圆周上有 8 个点 A1、A2、A3、A4、A5、A6、A7、A8（如下右图） ，那么与
26、 A1 相连的点有四种可能，分别是 A2、A4、A6或 A8以此分四类讨论，共 14 种方法 （5）如果圆周上有 10 个点，同样考虑能与 A1相连的点，分五类讨论，如下图所示共 42 种方法 A3 A1 A2 A4 A5 A6 A1 A2 A3 A4 A5 A6 A7 A8 还剩 4 个点， 2 种方法 1 种方法 还剩 4 个点， 2 种方法 还剩 6 个点， 共 5 种方法 剩余42个 点，方 法数为 2 1 剩余42个 点，方 法数为 2 1 还剩 6 个点，共 5 种方法 6 个点个点 共共 5 种种方法方法 8 个点个点 共共 14 种种方法方法 1 2 3 0 1 1 1 1 2
27、 3 3 2 6 8 8 3 16 22 22 4 44 60 60 5 120 164 164 6 328 448 448 评析：本题虽然不像之前那样，只遵循一个简单的累加规则，但也仍然是一个由小求大的递推过程： 在求解 6 个点的方法数时，会用到 2 个、4 个点的方法数；在求解 8 个点的方法 数时，也会用到 2 个、4 个、6 个点的方法数；而在求解 10 个点的方法数时，则 会用到 2 个、4 个、6 个、8 个点的方法数由此可见“由小求大”应该说是 递推法真正的内涵我们再处理问题时，要有能力将数目较大的情形通过变形， 化归为数目较小的情形来解决 另外，请大家观察右图从 A 处出发，
28、每次只能向右或向上走一步，那么从 A 到 B、C、D、E、F 的最短路径分别有多少？大家不妨用标数法（参考四年级 上册第 16 讲加法原理与乘法原理 ）自己做一做，在把相应的结果与本题的结 果对照一下，你能发现其中的奥妙吗？ A1 A2 A3 A4 A5 A6 A7 A8 A9 A10 A1 A2 A3 A4 A5 A6 A7 A8 A9 A10 A1 A2 A3 A4 A5 A6 A7 A8 A9 A10 A1 A2 A3 A4 A5 A6 A7 A8 A9 A10 A1 A2 A3 A4 A5 A6 A7 A8 A9 A10 剩余 8 个点 共 14 种方法 剩余26个点 共1 5种方法
29、剩余44个点 共2 2种方法 剩余26个点 共1 5种方法 剩余 8 个点 共 14 种方法 A B C D E F 练习：练习： 练习 1、 答案：12 简答：仿照例题 1 进行分类讨论，列出如下数表进行累加即可，注意累加规则 练习 2、 答案：21 简答：仿照例题 2，找到左上角的方格，按照该方格是横着覆盖还是竖着覆盖分两类讨论即 可得递推规则 练习 3、 答案：1276 简答：本题与直线分平面的问题本质相同，因此与例题 3 类似进行递推即可如下表所示 练习 4、 答案：43 简答：本题的传球规则传球规则和例题 4 相同，都只能把球传给别人，因此累加规则累加规则也相同但最 后的拿球人不是发
30、球人这一点要注意！ 直线数量 1 2 3 4 5 50 圆被分成的区域2 4 7 11 16 1276 2 3 5 50 4 方格表大小 1 2 2 2 32 4 2 52 62 72 覆盖方法数 1 2 3 5 8 13 21 台阶数 1 2 3 4 5 6 7 8 9 10 11 12 上台阶方法数 0 1 1 1 2 2 3 4 5 7 9 12 作业：作业： 1. 答案：89 简答： 2. 答案：36 简答： 3. 答案：14 简答：略 4. 答案：3277 简答：如右表所示，用传球法列表解决传球规则是：0 不能发球，其它都可以发球；传球不能传给自己，只能 传给别人；总共传球传 6 次
31、 5. 答案：29 简答： 如下方左图所示， 和例题 2 类似， 找到某个方格， 依据这个方格是横着覆盖还是竖着覆盖分两种情况讨论情况一，横着覆盖：这类情况其实 就是的覆盖方法，利用练习 2 的分析方法和相关结论，可得答案为 21情况二，竖着 覆盖：在这类情况下，有另外四个格子的覆盖方法唯一确定，如下方右图中的虚线所示，剩 下需要覆盖的是一个的方格表，其方法数量也可参考练习 2 的分析方法和相关结论来 取得，答案为 8上述两种情况相加，可得答案为 21829 52 72 石子数 1 2 3 4 5 6 7 8 9 10 11 12 抓取方法数 0 1 1 2 2 4 5 8 11 17 24 36 蛋黄派数 1 2 3 4 5 6 7 8 9 10 吃的方法数 1 2 3 5 8 13 21 34 55 89 0 1 2 3 4 0 0 1 1 1 1 1 4 3 3 3 3 2 12 13 13 13 13 3 52 51 51 51 51 4 204 205 205 205 205 5 820 819 819 819 819 6 3276 3277 3277 3277 3277
