企业官方网站地址,通了网站建设,网站排名软件利搜,企业logo设计合同一、子集问题 模板问题 给定一个序列[1,n],求这个序列的所有子集 输入描述#xff1a; 一个正整数n(1 n 12) 输出描述#xff1a; 每个子集一行#xff0c;输出所有子集。 输出顺序为#xff1a; #xff08;1#xff09;元素个数少的子集优先输出#xff1b;…一、子集问题 模板问题 给定一个序列[1,n],求这个序列的所有子集 输入描述 一个正整数n(1 n 12) 输出描述 每个子集一行输出所有子集。 输出顺序为 1元素个数少的子集优先输出 2元素个数相等的两个子集A和B若各自升序后满足前k−1项对应相同但有AkBk那么将子集A优先输出例如[1,5,9]比[1,5,10]优先输出。 在输出子集时子集内部按升序输出子集中的每个数之间用一个空格隔开行末不允许有多余的空格空集用空行表 示。不允许出现相同的子集。 #include iostream
#include cstdio
#include vector
#include cstring
#include algorithm
using namespace std;const int N 13;vectorvectorint ans;
vectorint temp;void dfs(int start, int n) {ans.emplace_back(temp); // 将当前子集添加到结果中for (int i start; i n; i) { // 修改循环条件为 以包含 ntemp.push_back(i);dfs(i 1, n);temp.pop_back();}
}bool compare(vectorint a,vectorint b) {if (a.size() ! b.size()) {return a.size() b.size();}else {return a b;}
}int main() {int n;scanf(%d, n);dfs(1,n);sort(ans.begin(), ans.end(), compare);for (int i 0; i ans.size(); i) {for (int j 0; j ans[i].size(); j) {printf(%d, ans[i][j]);if (j 1 ans[i].size()) {printf( );}}printf(\n);}return 0;
}变题 小晴来参加一个游园会。游园会中有n个游戏项目每个项目有且仅有一次参与机会如果成功完成了任意一个项目就能得到对应的积分如果失败了则积分不会发生变化。在游园会的出口可以用累计积分兑换奖品。小晴参与了所有项目问最后小晴的累计积分有哪些可能。 输入描述 第一行一个正整数n1≤n≤12表示游戏项目的个数。 第二行为n个不超过100的正整数表示每个游戏项目在成功完成后分别能获得多少积分。 输出描述 在一行内按升序输出所有不同的累计积分数字之间用一个空格隔开行末不允许有多余的空格。 同样是子集问题为什么可以这么理解呢因为对于小晴来说他赢了可以拿对应的分如果没有赢那么就不能选这个分加入结果这不就是子集问题吗
#include cstdio
#include vector
#include algorithm
#include set
using namespace std;const int N 13;
int a[N];
int n;
int path 0;
setint res;// 子集问题void dfs(int start) {res.insert(path); // 每次进入递归就把结果加入res中for (int i start; i n; i) {path a[i]; dfs(i1);path - a[i]; // 回溯}
}int main() {scanf(%d,n);for (int i 0; i n; i) {scanf(%d,a[i]);}dfs(0);int idx 0;for (setint::iterator it res.begin(); it ! res.end(); it) {printf(%d, *it);printf(idx 1 res.size() ? : \n);idx;}return 0;
}
二、排列问题 题目描述 给定一个正整数n假设序列S[1,2,3,…,n]求S的全排列。 输入描述 一个正整数n1≤n≤8。 输出描述 每个全排列一行输出所有全排列。 输出顺序为两个全排列A和B若满足前k−1项对应相同但有AkBk那么将全排列A优先输出例如[1,2,3]比[1,3,2]优先输出。 在输出时全排列中的每个数之间用一个空格隔开行末不允许有多余的空格。不允许出现相同的全排列。 #include cstdio
#include vector
using namespace std;const int MAXN 8 1;
vectorvectorint result;
vectorint path;
int n;
bool used[MAXN] {false};void DFS(int idx) {if (idx n 1) { result.push_back(path);return;}for (int i 1; i n; i) {if (!used[i]) { // 这个数还没有选过进行选择path.push_back(i);used[i] true;DFS(idx 1); // 此处的idx实际上是用来控制递归次数的used[i] false;path.pop_back();}}
}int main() {scanf(%d, n);DFS(1);for (int i 0; i result.size(); i) {for (int j 0; j result[i].size(); j) {printf(%d, result[i][j]);if (j ! result[i].size() - 1){printf( );}}printf(\n);}return 0;
} 变题: 题目描述 给定一个长度为n的序列其中有n个可能重复的正整数求该序列的所有全排列。 输入描述 第一行一个正整数n1≤n≤8表示序列中的元素个数。 第二行按升序给出n个可能重复的正整数每个正整数均不超过100。 输出描述 每个全排列一行输出所有全排列。 输出顺序为两个全排列A和B若满足前k−1项对应相同但有AkBk那么将全排列A优先输出例如[1,2,3]比[1,3,2]优先输出。 在输出时全排列中的每个数之间用一个空格隔开行末不允许有多余的空格。不允许出现相同的全排列。 看题目很明显还是排列问题但是在这题中会有重复数字比如我给出一个实例
输入1134
输出1(第一个1)1(第二个1)34 和 1(第二个1)1(第一个1)34,是同一个排列
那么我们就需要剪枝了
#include iostream
#include vector
#include algorithm
using namespace std;const int MAXN 8 1;
vectorvectorint result;
vectorint temp;
int n, a[MAXN];
bool used[MAXN] {false};void DFS(int idx) {if (idx n) {result.push_back(temp);return;}for (int i 0; i n; i) {if (i 0 a[i] a[i - 1] used[i - 1] false) {continue;}if (!used[i]) {temp.push_back(a[i]);used[i] true;DFS(idx 1);used[i] false;temp.pop_back();}}
}int main() {cin n; for (int i 0; i n; i) {cin a[i]; }DFS(0);sort(result.begin(), result.end());for (int i 0; i result.size(); i) {for (int j 0; j result[i].size(); j) {cout result[i][j]; if (j 1 result[i].size()) {cout ; } else {cout endl; }}}return 0;
}
三、组合问题 题目描述 给定两个正整数n、k假设序列S[1,2,3,…,n]求从S中任选k个的所有可能结果。 输入描述 两个正整数n、k1≤k≤n≤12。 输出描述 每个组合一行输出所有组合。 输出顺序为两个组合A和B若各自升序后满足前k−1项对应相同但有AkBk那么将组合A优先输出例如[1,5,9]比[1,5,10]优先输出。 在输出组合时组合内部按升序输出组合中的每个数之间用一个空格隔开行末不允许有多余的空格。不允许出现相同的组合 #include cstdio
#include vector
using namespace std;vectorvectorint result;
vectorint temp;
int n, k;void DFS(int idx) {if (temp.size() k) {result.push_back(temp);return;}for (int i idx; i n; i) {temp.push_back(i);DFS(i1);temp.pop_back();}
}int main() {scanf(%d%d, n, k);DFS(1);for (int i 0; i result.size(); i) {for (int j 0; j result[i].size(); j) {printf(%d, result[i][j]);printf(j 1 result[i].size() ? : \n);}}return 0;
} 变题 题目描述 给定n个互不相同的正整数从中选择若干个数每个数只能选一次使得这些数之和为定值K。求满足条件的方案数。 输入描述 第一行两个正整数n、K1≤n≤12、1≤K≤128分别表示整数个数与定值。 第二行按升序给出n个互不相同的正整数每个正整数均不超过128。 输出描述 输出满足条件的方案数。相同数字算作同一种方案例如{2,3}和{3,2}是同一个方案仅顺序不同。 这题显然是个组合问题只是再原有的组合问题的基础上又提出了新的要求即和要为定制k
可以按照组合问题的模板来套不过需要改变的是递归出口
#include cstdio
#include vector
using namespace std;int n,k;
const int N 13;
int a[N];
int curr 0;
int cnt;void dfs(int start) {if (curr k) {return;}if (curr k) {cnt;return;}for (int i start; i n; i) {curr a[i];dfs(i1);curr - a[i];}
}int main() {scanf(%d%d,n,k);for (int i 0; i n; i) {scanf(%d,a[i]);}dfs(0);printf(%d,cnt);return 0;}
