网站开发设计的技术路线,一流的龙岗网站设计,策划营销推广方案,建网站如果不买域名别人能不能访问题目
从 1∼ n n n 这 n n n 个整数中随机选取任意多个#xff0c;输出所有可能的选择方案。
输入格式
输入一个整数 n n n。
输出格式
每行输出一种方案。
同一行内的数必须升序排列#xff0c;相邻两个数用恰好 1 个空格隔开。
对于没有选任何数的方案#xff0c…题目
从 1∼ n n n 这 n n n 个整数中随机选取任意多个输出所有可能的选择方案。
输入格式
输入一个整数 n n n。
输出格式
每行输出一种方案。
同一行内的数必须升序排列相邻两个数用恰好 1 个空格隔开。
对于没有选任何数的方案输出空行。
本题有自定义校验器SPJ各行不同方案之间的顺序任意。
数据范围 1 ≤ n ≤ 15 1≤n≤15 1≤n≤15
输入样例
3输出样例 3
2
2 3
1
1 3
1 2
1 2 3思路
这等价于每个整数可以选可以不选所有可能的方案总数共有 2 n 2^n 2n 种。除了可以利用位运算求解还可以使用递归来求解在每次递归中分别尝试某个数 “选” 或 “不选” 两条分支将尚未确定的整数数量减少 1从而转化为一个规模更小的同类问题。
代码
递归
#include cstdio
#include vector
using namespace std;vectorint chosen; //被选择的数void cal(int n, int num) {if (num n 1) { //问题边界for (int i 0; i chosen.size(); i) {printf(%d , chosen[i]);}printf(\n);return ;}//不选num 分支cal(n, num 1);//选num 分支chosen.emplace_back(num); //记录num已被选择cal(n, num 1); //求解子问题chosen.pop_back(); //回溯到上一问题之前还原现场
}int main() {int n;scanf(%d, n);cal(n, 1);return 0;
}位运算
#include bits/stdc.h
using namespace std;void print_subset(int n, int s) {for (int i 1; i n; i) {if (s (1 i)) {printf(%d , i);}}printf(\n);
}int main() {int n;scanf(%d, n);for (int i 1; i (1 n 1); i 2) { //第0位不用所有的子集编码print_subset(n, i);}return 0;
}
