当前课程知识点:程序设计基础 > 第三章 逻辑推理与枚举解题 > 3.6 谁是嫌疑犯——用二进制枚举 > 3.6.1 谁是嫌疑犯——用二进制枚举
我们解决这个作案问题的时候
用于枚举的for语句
我们用了一个多重的循环
写了很多条for语句
那现在这个问题中是6个嫌疑人
如果我有更多嫌疑人呢
那是不是我们的多重循环
就要写更多的这个for呢
有同学就问了说
那我能不能不写那样的多重循环
我不用那么多的for
我们应该是有办法的
大家还记得上一讲
徐明星老师提到的一个
猜数字的一个卡片吗
当时我们就学习了
一个整数可以用2进制来表示
2进制这种表示呢
它的每一个位可以是0或者是1
那我们现在也可以用类似的一个想法
只要我们给每一个嫌疑人
指定一个2进制的位
把所有的嫌疑人
是不是参与作案这个情况拼在一起
也就是说把每个人是0还是1拼在一起
这样就能拼成一个6位的2进制数了
大家请看
我们人为的把ABCDEF拼在一起
那假设我们现在说
我们要枚举的是B C和E作案了
ADF没有作案
那我们人为拼在一起
就能得到一个2进制数011010
那这个2进制数
我们可以计算它的十进制下的一个值
那么我们知道
我们可以数一下每个2进制位所对应的
具体的十进制的值
那我们实际上可以算出说
对于011010来讲
它的实际的十进制的值
是16加8加2等于26
那反过来
如果我们给了一个
6位的2进制数
那我们可以把指定的
2进制位上的是0还是1
去解释成说相应的每个嫌疑人
是不是参与了作案
大家请看
比如说有一个数是97
那我们如果把它写成2进制
我们发现说97=64+32+1
那么写成6位的2进制就是110001
好 我们把它对应成我们的
ABCDEF的作案情况
那根据我们的对应关系就得到了
ABF参与作案了
CDE没有参与作案
所以我们枚举每一个嫌疑人
是否作案的所有可能情况
就等价于枚举所有的
6位的2进制数
那当然也就等价于枚举
相应的十进制的数值
这个事情我们用一个for循环
就可以实现了
那具体来说就是
让循环变量
从2进制的000000
一直到2进制的111111
也就是说我们枚举从
十进制数的0到
2的6次方减1就可以了
那么在我们具体
写代码的时候
在我的循环体里面
怎么根据循环变量的值
得到每一个嫌疑人
是否作案的信息呢
我们人当然会手动来算
那么怎么让程序来算呢
怎么让程序去得到
一个数的2进制的
每一位的值呢
这时候就需要用到了
我们计算机中的
一种特殊的运算
称为位运算
位运算是在数的
2进制表示的意义下
所做的操作
位运算又包括
以下几种运算
第一是按位与
我们看到又出现一个与
这时候我们只用了
一个与的符号
刚才我们提到了说
如果是逻辑的这个运算与
是两个符号
按位的
这个位运算与是一个符号
这儿举了个例子
0101与上1100结果是0101
按位与实际上
从求值的意义上来讲
跟我们这个逻辑的与是类似的
那我们这儿是0和1
逻辑运算是true和false
而且从这个例子中间
其实我们可以总结
按位我与1的话
就能保持这个位上的值
我们看
不管你这一位上是0还是1
你只要和1做按位与
就能保持原来的值
如果你和0做按位与
那你就会变成0 清0
所以我们可以通过
这个按位与一个特定的值
就可以把一个2进制数的
某些位置成0
其他位不变
第二个位运算是或
那跟我们逻辑运算的
那个或也有点类似
不管你原来这个位上的值是什么
你只要跟1做或 都会变成1
你如果和0做或 就保持原来的值
所以呢我们通过或上
一个特定的2进制数
就可以让原来2进制数的
某些位变成1
其他位不变
第三个位运算我们称为
按位的异或
那所谓异或
就是参与运算的两个位
只有它们不同的时候
结果才是1
如果它们相同结果就是0
所以呢
原来的一个2进制数的位
如果我异或1的话
它就会变
0变1 1变0
如果我异或0
它会保持原来的这个值
所以通过我们异或
一个特定的2进制的数
也可以让原先这个
2进制的某些位变化
而其他位不变化
还有一个二进制的运算
我们称为按位取反
这个比较好理解
原来是0
那么按位取反就变成1
原来是1 就变成0
那还有最后
两个特殊的位运算
我们称为移位的运算
第一个是往右移位
它的意义是这样的
这个2进制数的所有的位
它是向右移
那最高位有点特殊
那我们简单说叫高位重复
大家看这个例子
如果我这个数是00011010
它往右移两位
那么首先是移过去
可是会空出两个位来
这两个位我们用
原先最高位的这个0来填充
所以结果是00000110
那如果原先
这个数是1开头的
10011010
它往右移两位会怎么样呢
首先也是往右移两位
移完以后空出来两位
我们用原先最高位的1去填充
这样就得到了11111010
这是往右移位
相反的我们还有
往左移位的运算
那往左空出来的怎么办
这个时候我们就是
简单的低位补0了
大家看原先的
一个数是10011010
往左移两位之后
空出来的两个位置填0就可以了
有了这些位运算
我们的for循环实际上可以这么去写
大家看
我们从0开始枚举
要枚举到2的6次方减1
所以实际上我并没有真的去算
2乘2乘2乘2 乘好几次
我写的是1左移六位
因为我们知道说
对于2进制来讲
每一位依次值是2 4 8
那么我移一位
就相当于每一位的值
原先的每一位上的数
乘以2了
所以我移N位就相当于
乘了2的N次方
既然我需要2的6次方
那我就让1移6位就可以了
那通过位运算
我们来操作2进制中特定的位
我们可以取特定位上的一个值
或者呢让特定位上
变成0或者变成1 或者反转 都可以了
所以现在我们就来研究一下
对于这个题
我们已经有了一个
ABCDEF拼出来的
一个2进制的值
我们怎么取得
具体每一个人对应的位是0还是1呢
那我们假设说
我们不知道D这个人到底作没作案
我们枚举他到底是
作案呢还是没作案呢
那我们通过位操作可以
这样去计算
首先呢
我们规定了说
D对应的是2进制里面的
这个01234数上去
第2这个位置
所以我们先让它向右移两位
把D对应的这个2进制的值
移到了我们说最低位上
那至于说空出来的两位
到底是填哪个呢
那当然我们是学过了说
到底这个空的位是怎么填
但我们这儿其实不关心
所以你看我这儿就直接打了两个横线
我不关心它的值是多少
因为我们后面的操作是什么
我们要把D上的这个值取出来
所以我和1做按位的与运算
也就是和000001按位与
这时候前面我不管它是什么值了
都被我置0了
只有D
原先在D这个位置的
这个位上的值
会计算出来
所以我们看到
对于D来讲
我们只要右移两位
并且再与1做与运算
就可以得到了
类似的
我们现在把ABCDEF
是这么拼起来的
分别是对应了543210的位
那么我们就可以用
这样的一系列的表达式
把A到F每个人 是不是作案的情况 给计算出来
那么用这样的表达式
去代替我们原先的
这个程序中的计算
就可以看到
现在我们就用了1重循环
一个for
但是对于这个循环变量取值
我们先通过位运算
把ABCDEF是不是作案
都计算出来
然后就跟原先一样
我们去检查
我们的破案线索是不是符合了
那这个时候
因为只用了1重的for循环
所以我们简单的一个break
就可以中断我们继续枚举了
那我们看到了
今天这两个题
都是计算机来解决
逻辑问题的
而且这个
我们说计算机确实是
有挺强大的逻辑分析功能的
但是这种能力
实际上是人通过程序
来赋予它的
那一些逻辑问题
必须转换成计算机能够
看得懂的表达式
并且我们要通过一系列的
一定的程序的指令
才能让计算机通过计算
来找出答案
在解题过程中
有些问题
本来没有办法直接计算
就是比如说他作案还是没作案
这种情况本来没法算
但是我们通过一些方法
把自然语言的描述
能转化成可以计算的表达式
这样就把一个本来
看起来不能算的问题
变得可算了
然后我们把可算的这些表达式
用程序语言组织起来
我们有顺序的去执行的
有if语句 去根据条件执行的
还有循环语句 去反复执行的
那通过这些
这个有序的一种组织
那我们就使得
解决问题成为可能
所以最后其实还是我们的人
赋予了计算机逻辑分析和推理的能力
-1.1 基础知识
-1.2 买菜问题
-1.3 数学运算
-1.4 补充说明
-1.5 总结
--1.5 总结
-程设论道
--程设论道
-师生问答
-第一章 编程初步--语法自测
-2.1 关于超级计算器的几点思考
-2.2 电子秤模拟 — 背景介绍及需求分析
-2.3 电子秤模拟 — 代码实现
-2.4 变量定义与变量类型
-2.5 猜数游戏与数据表示
-2.6 关于变量的讨论
--公告
-2.7 变量体现的计算思维
-程设论道
--程设论道
-师生问答
--师生问答
-第二章 变量与代数思维--语法自测
-3.1 谁做的好事——语义表示
-3.2 谁做的好事——真假检查
-3.3 谁做的好事——循环枚举
-3.4 谁是嫌疑犯——多重循环枚举
-3.5 谁是嫌疑犯——破案线索表示
-3.6 谁是嫌疑犯——用二进制枚举
-程设论道
--程设论道一
--程设论道二
--程设论道三
-师生问答
-第三章 逻辑推理与枚举解题--语法自测
-4.1 插花游戏
-4.2 筛法
-4.3 线性查找
-4.4 折半查找
--4.4.1 提问
-4.5 排序问题
-4.6 总结
--4.6.1 总结
-程设论道
--程设论道二:筛法
-师生问答
-第四章 筛法与查找--语法自测
-5.1 阶乘
-5.2 排序
-5.3 矩阵填充
-5.4 分书与八皇后
-5.5 青蛙过河
-程设论道
--程设论道一
--程设论道二
-师生问答
--师生问答一
--师生问答二
-第五章 分治思想与递归--语法自测
-6.1 兔子数列问题
-6.2 分鱼问题
-6.3 橱窗的插花问题
-6.4 最长公共子序列问题
-程设论道
--程设论道一
--程设论道二
-师生问答
--师生问答
-第六章 递推与动态规划--语法自测
-7.1 统计记录总数
-7.2 统计活跃用户数
-7.3 统计在线时长
--7.3.2 结构
-7.4 总结
--7.4.1 总结
-程设论道
--程设论道
-师生问答
--师生问答
-第七章 文本数据处理--语法自测
-8.1 将数据组织成链表
-8.2 提高链表访问效率 —— 哈希链表
-8.3 以二进制文件存储链表
-程设论道
--程设论道一
--程设论道二
-师生问答
--师生问答
-第八章 非文本数据处理--语法自测
-9.1 自动售卖程序
-9.2 配制水果信息
-9.3 指定界面语言
-程设论道
--程设论道
-师生问答
--师生问答
-第九章 可配置的程序设计--语法自测