InTheBloodHorse

数据结构与算法(9) 二进制枚举

字数统计: 333阅读时长: 1 min
2019/01/09 Share

什么是二进制枚举

二进制枚举是用来枚举子集的。即把问题转化成二进制的思想,根据转化后的二进制每位的数字(0 | 1)来确定状态。
例:
现在要记录5名学生的期末成绩,1表示通过,0表示不通过,结果会有 2^n 次可能,用二进制表示的话就是从00000 ~ 11111(十进制下为数字 0~31)
TIM截图20190109142924.jpg

复杂度

在例子的5名学生中,运算了 32 * 5,所以复杂度为 N * 2^N
同样的,DFS也可以解决类似问题,复杂度差不多

位运算

在c语言中 << 代表左移 比如 1<<1 就由1(十进制1)得到结果10(十进制2),="">> 右移同理

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin >> n; //n代表几个人
for(int i=0;i< (1<<n) ;i++){ // 1<<n 代表有多少种情况
for(int j=0;j<n;j++){ //i表示当前状态
// i & 1<<j j代表第几位
// 结果得到 第j位的状态
if(i & 1<<j){ // 假如第j位为 1
cout << 1 << " ";
}else{ //假如第J位为 0
cout << 0 << " ";
}
}
}
}

题目

二进制枚举经常用来解决ACM题目。二进制枚举例题

CATALOG
  1. 1. 什么是二进制枚举
  2. 2. 复杂度
  3. 3. 位运算
  4. 4. 代码
  5. 5. 题目