当前课程知识点:程序设计基础 >  第三章 逻辑推理与枚举解题 >  3.6 谁是嫌疑犯——用二进制枚举 >  3.6.1 谁是嫌疑犯——用二进制枚举

返回《程序设计基础》慕课在线视频课程列表

3.6.1 谁是嫌疑犯——用二进制枚举在线视频

3.6.1 谁是嫌疑犯——用二进制枚举

下一节:程设论道一

返回《程序设计基础》慕课在线视频列表

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.1.1 什么是程序?什么是语言?

--1.1.2 什么是程序设计?

--1.1.3 计算机发展史

-1.2 买菜问题

--1.2.1 问题描述

--1.2.2 程序的基本结构

-1.3 数学运算

--1.3.1 数学运算符

--1.3.2 数学函数

-1.4 补充说明

--1.4.1 编程环境的下载与安装

--1.4.2 程序基本结构中的含义

--1.4.3 格式与风格

-1.5 总结

--1.5 总结

-程设论道

--程设论道

-师生问答

--师生问答一:怎样学好程序设计

--师生问答二:语言选择

--师生问答三:关于函数

-第一章 编程初步--语法自测

第二章 变量与代数思维

-2.1 关于超级计算器的几点思考

--2.1.1 关于超级计算器的几点思考

-2.2 电子秤模拟 — 背景介绍及需求分析

--2.2.1 电子秤模拟 — 背景介绍及需求分析

-2.3 电子秤模拟 — 代码实现

--2.3.1 电子秤模拟 — 代码实现

-2.4 变量定义与变量类型

--2.4.1 变量定义与变量类型

-2.5 猜数游戏与数据表示

--2.5.1 猜数游戏与数据表示

-2.6 关于变量的讨论

--2.6.1 变量的初始值

--2.6.2 变量类型

--2.6.3 变量内存单元地址

--2.6.4 存“变量地址”的变量——指针

--2.6.5 指针的 读/写 操作

--2.6.6 指针的 加/减 操作

--公告

-2.7 变量体现的计算思维

--2.7.1 变量体现的计算思维

-程设论道

--程设论道

-师生问答

--师生问答

-第二章 变量与代数思维--语法自测

第三章 逻辑推理与枚举解题

-3.1 谁做的好事——语义表示

--3.1.1 谁做的好事——语义表示

-3.2 谁做的好事——真假检查

--3.2.1 谁做的好事——真假检查

-3.3 谁做的好事——循环枚举

--3.3.1 谁做的好事——循环枚举

-3.4 谁是嫌疑犯——多重循环枚举

--3.4.1 谁是嫌疑犯——多重循环枚举

-3.5 谁是嫌疑犯——破案线索表示

--3.5.1 谁是嫌疑犯——破案线索表示

-3.6 谁是嫌疑犯——用二进制枚举

--3.6.1 谁是嫌疑犯——用二进制枚举

-程设论道

--程设论道一

--程设论道二

--程设论道三

-师生问答

--师生问答一:字符与ASCII码表

--师生问答二:其他循环语句、运算符优先级与变量作用域

-第三章 逻辑推理与枚举解题--语法自测

第四章 筛法与查找

-4.1 插花游戏

--4.1.1 问题提出(求素数)

--4.1.2 函数初探

--4.1.3 运行演示

-4.2 筛法

--4.2.1 筛法思路

--4.2.2 数组的定义

--4.2.3 代码翻译

--4.2.4 运行演示

--4.2.5 小朋友数人数

--4.2.6 运行演示

--4.2.7 韩信点兵

-4.3 线性查找

--4.3.1 扑克查找问题

--4.3.2 扑克查找问题代码翻译

--4.3.3 最小值问题

--4.3.4 最小值问题代码翻译

-4.4 折半查找

--4.4.1 提问

--4.4.2 折半查找思路

--4.4.3 折半查找代码翻译

--4.4.4 折半查找运行演示

-4.5 排序问题

--4.5.1 插入排序

--4.5.2 选择排序

--4.5.3 函数写法

--4.5.4 运行演示

-4.6 总结

--4.6.1 总结

-程设论道

--程设论道一:数组与编码思维

--程设论道二:筛法

-师生问答

--师生问答一:函数与面向过程编程

--师生问答二:数组的下标越界

-第四章 筛法与查找--语法自测

第五章 分治思想与递归

-5.1 阶乘

--5.1.1 阶乘问题

--5.1.2 递归解法

--5.1.3 递归小结

-5.2 排序

--5.2.1 归并排序——总体思路

--5.2.2 归并排序——思路分解

--5.2.3 归并排序——代码解说

--5.2.4 快速排序——总体思路

--5.2.5 快速排序——代码解说

--5.2.6 排序总结

-5.3 矩阵填充

--5.3.1 矩阵填充问题

--5.3.2 代码解说

-5.4 分书与八皇后

--5.4.1 问题描述

--5.4.2 问题分析——共性

--5.4.3 问题分析——区别

--5.4.4 解题准备——二维数组

--5.4.5 解题准备——递归设计

--5.4.6 代码解说——分书问题

--5.4.7 代码解说——八皇后问题

-5.5 青蛙过河

--5.5.1 问题描述

--5.5.2 问题分析——简单情况

--5.5.3 问题分析——复杂情况

--5.5.4 问题分析——一般情况

-程设论道

--程设论道一

--程设论道二

-师生问答

--师生问答一

--师生问答二

-第五章 分治思想与递归--语法自测

第六章 递推与动态规划

-6.1 兔子数列问题

--6.1.1 问题描述

--6.1.2 按大小兔子分别递推

--6.1.3 按总数递推

--6.1.4 不用数组递推

-6.2 分鱼问题

--6.2.1 问题描述

--6.2.2 从A到E递推

--6.2.3 从E到A递推

-6.3 橱窗的插花问题

--6.3.1 问题描述

--6.3.2 题意理解与分析

--6.3.3 用枚举思想解题

--6.3.4 采用递推的优化算法

--6.3.5.1 采用动态规划算法—优化分析

--6.3.5.2 采用动态规划算法—递推代码

--6.3.5.3 采用动态规划算法—计算过程

--6.3.5.4 采用动态规划算法—输出方案

--6.3.6 动态规划总结

-6.4 最长公共子序列问题

--6.4.1 问题描述与理解

--6.4.2 问题分析

--6.4.3.1 动态规划解题(1)

--6.4.3.2 动态规划解题(2)

--6.4.3.3 动态规划代码

-程设论道

--程设论道一

--程设论道二

-师生问答

--师生问答

-第六章 递推与动态规划--语法自测

第七章 文本数据处理

-7.1 统计记录总数

--7.1.1 问题分析

--7.1.2 读文件操作

-7.2 统计活跃用户数

--7.2.1 问题分析

--7.2.2 字符串

--7.2.3 程序翻译与演示

-7.3 统计在线时长

--7.3.1 问题分析

--7.3.2 结构

--7.3.3 程序翻译与演示

--7.3.4 写文件操作

-7.4 总结

--7.4.1 总结

-程设论道

--程设论道

-师生问答

--师生问答

-第七章 文本数据处理--语法自测

第八章 非文本数据处理

-8.1 将数据组织成链表

--8.1.1 链表的基本概念

--8.1.2 代码讲解

--8.1.3 链表遍历与释放

-8.2 提高链表访问效率 —— 哈希链表

--8.2.1 简单的哈希算法

--8.2.2 算法实现

-8.3 以二进制文件存储链表

--8.3.1 二进制文件的操作方法

--8.3.2 代码讲解

-程设论道

--程设论道一

--程设论道二

-师生问答

--师生问答

-第八章 非文本数据处理--语法自测

第九章 可配置的程序设计

-9.1 自动售卖程序

--9.1.1 提出问题与初步设计

--9.1.2 细化实现订单处理

--9.1.3 使程序更健壮

-9.2 配制水果信息

--9.2.1 提出问题与设计文件格式

--9.2.2 实现订单处理功能

-9.3 指定界面语言

--9.3.1 提出问题与命令行参数

--9.3.2 实现程序功能

-程设论道

--程设论道

-师生问答

--师生问答

-第九章 可配置的程序设计--语法自测

3.6.1 谁是嫌疑犯——用二进制枚举笔记与讨论

也许你还感兴趣的课程:

© 柠檬大学-慕课导航 课程版权归原始院校所有,
本网站仅通过互联网进行慕课课程索引,不提供在线课程学习和视频,请同学们点击报名到课程提供网站进行学习。