CppBook

Appearance

Return to top
On this page

指数型枚举

从这个整数中随机选取任意多介，输出所有可能的方案。

想法一：

每个数有两种可能性，选或不选，则共有种可能性。这里最方便的方法是用后面的学习到的位运算方式一个for循环来实现。但这里我们用递归来实现

刚开始搞不清楚题目如何做，可以先把结果手动的写出来，比如数据是：1 2时，结果应该是

0 0
0 2
1 0
1 2
1
2
3
4

其中0表示相应位置的数没有选，如果用树来表示你每一步的选择,行成一棵搜索树如下

graph g {
    node[shape=circle fixedsize=true style=filled fillcolor=white colorscheme=accent8 ];
    root--{0,1}
    0 -- {02,2}
    1 -- {002,22}
    02,002[label=0]
    2,22[label=2]
}

思路：递归就是在树上不停的前进与回溯,每到达一个点，如果这个点是选的点就纪录这个数，如果是不选的点就记录0，边界条件是选到了第n+1个数

c
int choose[maxn];
void calc(int pos){
    if( pos == n+1){ //已经选到了n+1位，证明前n位已经选好了
        for(int i = 1;i<=n;i++) //输出结果
            if(choose[i]) printf("%d ",choose[i]);
        return;
    }

    choose[pos] = 0;
    calc(pos+1); //不选

    choose[pos] = a[i];
    calc(pos+1); //选
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

想法二：

如果我们不想用0来表示不选，直接写出结果

2
1
1 2
1
2
3

相当于直接把0去掉， 我们知道递归是建立在栈的基础上的，使用vector来模拟栈这种数据结构,当选一个数字的时候，就把它存入栈里，回溯时把它扔掉（此时这个数字一定在栈的顶部），这样我们就写出了一个更简单的写法如下：

代码2

c
vector<int> choose;
void calc(int pos){
    if( pos == n+1){ //已经选到了n+1位，证明前n位已经选好了
        for(int i = 0;i< choose.size();i++) //输出结果
            printf("%d ",choose[i]);
        return;
    }

    choose[pos] = 0; //不选

    choose.push_back(a[i]); //这里可以理解成模拟一个栈来存数据
    calc(pos+1); //选
    choose.pop_back(); //递归的回溯，要退出这个点了
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

组合型枚举

从这个整数中随机选取m个，输出所有可能的方案。

想法一：

挑数，从n个数里挑m个数，假如第一个数挑的是第i个数，为了保证不重复，下一数只能挑[i+1,n]范围的内的数

保证能实现组合，不重复,

cpp









 





int choose[maxn];
void calc(int x,int pre,int len){
    if( len == m+1){ //边界 成功了
        for( int i = 1;i<=m;i++)
            printf("%d ",choose[i]);
        printf("\n");
        return ;
    }
    if( x == n+1) return;
    for(int i = pre+1;i<=n;i++){//可以优化
        choose[len]  = a[i];
        calc(x+1,i,len+1);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

优化,注意高亮的那一行, 显然考虑每一次可选的数的范围

for(int i = pre+1;i<=n;i++) 替换成==> for(int i = pre+1; i<=n-(m-i)+1;i++)，为什么可以这样呢？ 想一想：你第i个选的数最多能选到哪里？显然后面至少要保留个位置，可以得到当前数最多选到

如下,从5个数里选3个

第i个数最多选到n-(m-i)+1
<
>
╔═══╦═══╦═══╦═══╦═══╗
║ 1 ║ 2 ║ 3 ║ 4 ║ 5 ║
╚═══╩═══╩═══╩═══╩═══╝

  ┌───────┐
  │       │
╔═══╦═══╦═══╦═══╦═══╗
║ 1 ║ 2 ║ 3 ║ 4 ║ 5 ║
╚═══╩═══╩═══╩═══╩═══╝

5个数字选3个

第1个可能选的数是:1 2 3

想法二：

更简单的方法是给代码2加上如下的剪枝

假如我们要从4个数里选3个数，选把4个数任意选的结果列出如下

plaintext
0 0 0 0
0 0 0 4
0 0 3 0
0 0 3 4
0 2 0 0
0 2 0 4
0 2 3 0
0 2 3 4
1 0 0 0
1 0 0 4
1 0 3 0
1 0 3 4
1 2 0 0
1 2 0 4
1 2 3 0
1 2 3 4
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
plaintext
0 0 0 0
0 0 0 4
0 0 3 0
0 0 3 4
0 2 0 0
0 2 0 4
0 2 3 0
0 [2 3 4]
1 0 0 0
1 0 0 4
1 0 3 0
[1 0 3 4]
1 2 0 0
[1 2 0 4]
[1 2 3] 0
1 2 3 4
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

显示从4个里选3个的结果（右）包含在任意选（左）的结果里，所以只要过滤出符合条件的结果即可

所以中要给上面的代码2加上一个剪枝条个如下

c
//加在 calc(int pos) 下
if( choose.size() > m || choose.size() + (n-pos+1) < m){
    return;
}
1
2
3
4

排列型枚举

求这个整数的全排列

遵循一个简单的原则：每次从剩下的未选数里选一个

c
bool vis[maxn];
int choose[maxn];
void calc(int pos){
    if( pos == n+1){
        return;
    }
    for(int i =1;i<=n;i++){
        if( vis[i]) continue;
        choose[pos]  = a[i];
        vis[i] = 1;
        calc(pos+1);
        vis[i] = 0;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

练习题目

  • luogu 分苹果

参考/引用