【基础】枚举学习笔记

枚举形式

按照状态空间的规模大小，有如下几种常见的枚举和遍历形式：
1、多项式->循环，递推
2、指数->递归，位运算

//从1~n这n个数中随机取多个，输出可能的方案
vector<int>chosen;
void calc(int x){
    if(x==n+1){//问题边界
        for(int i = 0; i < chosen.size(); i++)
            cout<<chosen[i]<<' ';
        cout<<'\n';
        return ;
    }
    //不选x
    calc(x+1);
    //选x
    chosen.push_back(x);
    calc(x+1);
    chosen.pop_back();
}
int main(){
    calc(1);
}
  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
 

3、组合->递归+剪枝

//从1~n这n个数中随机选出m个，输出可能的方案
vector<int>chosen;
void calc(int x){
    //剪枝
    if(chosen.size()>m || chosen.size()+(n-x+1)<m){
        return ;
    }
    if(x==n+1){//问题边界
        for(int i = 0; i < chosen.size(); i++)
            cout<<chosen[i]<<' ';
        cout<<'\n';
        return ;
    }
    //不选x
    calc(x+1);
    //选x
    chosen.push_back(x);
    calc(x+1);
    chosen.pop_back();
}
int main(){
    calc(1);
}
  

 

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

4、排列->递归

//从1~n这n个整数随机打乱，输出所有可能的次序
int a[20], vis[20];
void calc(int k){
    if(k == n+1){
        for(int i = 1; i <= n; i++)
            cout<<a[i]<<' ';
        cout<<'\n';
        return ;
    }
    for(int i = 1; i <= n; i++){
        if(vis[i])continue;
        a[k] = i;
        vis[i] = 1;
        calc(k+1);
        vis[i] = 0;
        a[k] = 0;//可省略
    }
}
  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
 

文章来源: gwj1314.blog.csdn.net，作者：小哈里，版权归原作者所有，如需转载，请联系作者。

原文链接：gwj1314.blog.csdn.net/article/details/80461061