Doubeecat's Blog

“即便前路混沌,同她走过,才算人间。”

0%

ACwing 92 93 94 解题报告

递归实现指数型枚举

递归实现组合型枚举

递归实现排列型枚举

指数型:在 $1-n$ 这 $n$ 个整数中随机选取任意多个,输出所有可能的次序。

组合型:从 $1- n$ 这 $n$ 个整数中随机选出 $m$ 个,输出所有可能的选择方案。

排列型:把 $1-n$ 这 $n$ 个整数排成一行后随机打乱顺序,输出所有可能的次序。

解题思路:

这三题的思路大致一致,所以放在一起来写。

指数型:很明显,这个问题可以转化成:

有 $n$ 个整数,每个整数可以选可以不选,求总共有几种方案。

我们可以使用递归来求解问题,每次递归时,我们有两条路:“选”,”不选”

放在代码里就是这样:

1
2
3
4
5
v.push_back(p);//选择这个数
calc(x+1);//选择这个数的分支
v.pop_back();//还原现场

calc(x+1);//不选这个数的分支

而每次递归后,我们面对的问题规模(还剩几个数需要选)-1,变成一个规模更小的问题,所以可以用递归求解。

组合型:这个问题和上一个本质一样,我们只要加入更多的限制条件:

  1. 当当前选取的数数量大于 $m$ 时,不再选数。
  2. 当剩下的数全选也不够 $m$ 时,不再选数。

放在代码里就是这样:

1
if (v.size() > m || v.size + (n-x+1) < m) return ;

排列性:这里,我们的问题就变成了:

把 $n$ 个整数按照任意次序排列

递归中,我们每次选取一个数放在当前位置,问题就变成了:把 $n-1$ 个整数按照任意次序排列,所以可以用递归来做

放在代码里就是这样:

1
2
3
4
5
6
7
8
for (int i = 1;i <= n;++i) {
if (!chos[i]) {
ord[x] = i;
chos[i] = 1;
calc(x+1);
chos[i] = 1;
}
}

代码:

指数型:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int x;
vector <int> chosen;

void choice(int n) {
if (n == x+1) {
fp(i,0,chosen.size()) {
printf("%d ",chosen[i]);
}
printf("\n");
return ;
}
choice(n+1);
chosen.push_back(n);
choice(n+1);
chosen.pop_back();
}

int main() {
x = read();
choice(1);
return 0;
}

组合型:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

std::vector<int> v;

int n,m;

void c(int x) {
if (v.size() == m) {
for (size_t i = 0;i < v.size();++i) {
printf("%d ",v[i]);
}
puts("");
return ;
}
if (v.size() > m || v.size() + (n - x + 1) < m) {//判断边界,第一个是判断当前是否大于m个了,第二个判断是否选不够
return ;
}
v.push_back(x);
c(x+1);
v.pop_back();
c(x+1);

}

signed main() {
n = read(),m = read();
c(1);
return 0;
}

排列型:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
int n,ord[10];
bool chos[10];

void calc(int x) {
if (x == n+1) {
for (int i = 1;i <= n;++i) {
printf("%d ",ord[i]);
}
puts("");
return ;
}
for (int i = 1;i <= n;++i) {
if (!chos[i]) {
ord[x] = i;
chos[i] = 1;
calc(x+1);
chos[i] = 1;
}
}
}

signed main() {
n = read();
calc(1);
return 0;
}