算法系列之二进制位+回溯递归
算法系列之二进制位+回溯递归
公众号guangcity
发布于 2020-06-17 16:34:58
发布于 2020-06-17 16:34:58
1.算法系列之二进制位+回溯递归
题目：从 1~n 这 n 个整数中随机选取任意多个，输出所有可能的选择方案。输入：n 输出：多种方案 同一行内的数必须升序排列，相邻两个数用恰好1个空格隔开。
数据范围
1≤n≤15
输入样例：
3
输出样例：
3
2
2 3
1
1 3
1 2
1 2 3
数据范围15，2^15次方是可以的，也就是递归算法。
2.递归+回溯
我们直接递归的过程中记录下选择的数即可。
#include <iostream>
#include <vector>
using namespace std;
int n;
void dfs(int u, vector<int>& temp) {
if (u == n) {
for(int i=0;i<temp.size();i++) {
cout << temp[i]+1 << " ";
}
cout << endl;
return;
}
dfs(u+1, temp); // 不选
temp.push_back(u); // add
dfs(u+1, temp); // 选择
temp.pop_back(); // recover
}
int main() {
cin >> n;
vector<int> temp;
dfs(0,temp);
return 0;
}
3.递归+二进制位
针对每一个数，都有选与不选两种可能：假设n = 5 那么我们可以用二进制位表示每一位选择还是没有选择。
0 1 2 3 4
// 例如：选择数字4 5(分别对应第3、4位)
0 0 0 1 1 表示的数字就是11000
然后到了递归出口时，把这个数字从低位向高位遍历，&1判断是否是1，是1，那么该位是被选择了，也就是这个数字(该位+1)被选择了。
// 再比如：选择数字1
1 0 0 0 0 表示的数字就是1，出口的时候直接从低位遍历，此时就是index=0所代表的数字1。
具体实现如下：
#include <iostream>
using namespace std;
int n;
void dfs(int u, int state) {
if (u == n) {
for (int i = 0;i<n;i++) {
if(state>>i & 1) {
cout << i+1 << ' ';
}
}
cout << endl;
return;
}
dfs(u+1, state); // 不选
// <<与>>优先级大于|，&
dfs(u+1, state | (1 << u)); // 选择
}
int main() {
cin >> n;
dfs(0,0);
return 0;
}
3.非递归+二进制位
在递归实现中，我们是通过往下递归，直到找到出口，此时我们得到了一个状态，也就是二进制的数据串，例如：1010，然后从第0位开始到第n-1开始拿去该二进制数中是1所代表哪个数。
那对于非递归，我们可以知道所有的状态或者说二进制数总共有2^n种可能，可以直接遍历该2^n种可能性，再去从低位到高位，判断哪一位是1，进而确定具体选择的数字是多少。
int n;
cin >> n;
for (int state = 0; state < 1<<n; state++) {
for (int i=0;i<n;i++) {
// 右移拿到第i位的数，判断是否——是1
if (state>>i&1) cout << i+1 << " ";
}
cout << endl;
}本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2020-06-13，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录