蓝桥杯 --- (递归实现指数型枚举)

acwing92

递归实现指数型枚举(DFS + 递归 + 位运算)

1.实现数字的全排列

全排列就是输出所有不同顺序答案,答案个数没有限制; 答案排列顺序没有限制;

直接从1开始搜索,搜索完后就行递归回溯;

#include 

using namespace std;
int n;
bool vis[20];
int a[20];

void solve(int pos){
    if(pos == n + 1){
        for(int i = 1;i <= n;++ i)
            cout << a[i] << " ";
        cout << endl;
        return;
    }    
    for(int i = 1;i <= n;++ i){
        if(!vis[i]){
            vis[i] = true;
            a[pos] = i;
            solve(pos + 1);
            vis[i] = false;
        }
    }
    return;
}

int main(){
    cin >> n;
    solve(1);
    return 0;
}

2.从小到大输出数字的排列

有个数的限制; (通过一个for循环将个数限制从1到n)

排列顺序有限制; (改变每一次回溯后的i值,保证后面的每一个i都比刚存进去的值大)

当回溯到最后一次的时候已经结束了一轮;

#include 

using namespace std;
int n;
bool vis[20];
int a[20];

void solve(int pos,int idx,int end){
    if(pos == end + 1){
        for(int i = 1;i <= end;++ i)
            cout << a[i] << " ";
        cout << endl;
        return;
    }    
    for(int i = idx;i <= n;++ i){
        if(!vis[i]){
            vis[i] = true;
            a[pos] = i;
            solve(pos + 1,i + 1, end);
            vis[i] = false;
        }
    }
    return;
}

int main(){
    cout << endl;
    cin >> n;
    for(int i = 1;i <= n;++ i)
        solve(1, 1, i);
    return 0;
}

3.位运算进行优化

位运算二进制为分为0 , 1;对于每一个位置分为选与不选,如果选为1 ,不选为0;

则不需要但心按递增顺序排列;

#include 

using namespace std;
int n;

//pos表示现在选第几位的数,state表示第pos位是否被选,被选后该位置为1;
void solve(int pos,int state){
    if(pos == n){
        for(int i = 0;i < n;++ i){
            if(state >> i & 1)
                cout << i + 1<< " ";
        }
        cout << endl;
        return;
    }
    //选这个数
    solve(pos + 1,state | 1 << pos);
    //不选这个数
    solve(pos + 1,state);
}

int main(){
    cin >> n;
    //一位一位进行填充,开始什么都没有填充为0,被选的数状态为0;
    solve(0, 0);
    return 0;
}