题目描述
从 1\sim n1∼n这 n (n \leq 16)(n≤16) 个整数中随机选取任意多个,输出所有可能的选择方案。
输入描述:
一个整数n。
输出描述:
每行一种方案。同一行内的数必须升序排列,相邻两个数用恰好1个空格隔开。对于没有选任何数的方案,输出空行。本题有自定义校验器(SPJ),各行(不同方案)之间的顺序任意。
这道题有多种解法,这里只介绍状态压缩版:
状态压缩的特性:
可以枚举所有选与不选的情况。
实例:
不难发现题目输出的结果都为2^n:
当n为2时输出:
000->/n
001->1
010->2
011->1 2
当n为3时输出:
000->/n
001->1
010->2
100->3
011->1 2
101->1 3
110->2 3
111->1 2 3
C++状压递归版:
#include <iostream> using namespace std; int N; void dfs(int n, int state)//n为当前枚举到的数,state是记录哪些数被选 { if (N == n) { for (int i = 0; i < n; i++) if (state >> i & 1) cout << i + 1 << " "; cout << endl; return; } dfs(n + 1, state);//不用n这个数 dfs(n + 1, state | (1 << n));//用n这个数 } int main() { cin >> N; dfs(0, 0); }
虽然题目是递归,但我从小就不是一个唯命是从的人
所以
C++状压非递归版:
#include <iostream> using namespace std; int main() { int n; cin >> n; //state表示每一种状态 for (int state = 0; state < (1 << n); state++) { //用i遍历整个state并输出 for (int i = 0; i < n; i++) if (state >> i & 1) cout << i + 1 << " "; cout << endl; } return 0; }
我觉得每到题不一定只有一种答案呢,以上只给出两种还有例如vector枚举来解的等等......