全排列

发表于 更新于 分类于 Waline： 本文字数： 249 阅读时长 ≈ 1 分钟

P1706 全排列问题

终于要写c++的博客了~近期从搜索入手，将暴力算法+剪枝掌握熟练

对于全排列问题，我们使用dfs，将搜索的当前状态设定为当前位置，通过遍历1~n，若该数没有被使用过，便将该数填入，然后寻找下一位，直到n+1位跳出递归。

由此，我们可以大概抽象出dfs的基本步骤：

1
2
3
4
5
6
7
8
void dfs(当前状态){
    终止条件

    对于当前状态进行遍历，寻找下一可行状态
    改变下一状态相关参数
    dfs(下一状态)
    恢复“下一状态”（时则为本次状态）原样
}

代码实现：

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
#include<iostream>
#include<iomanip>
using namespace std;
int n;
int a[20],flag[20];
void dfs(int cur){
    if(cur==n+1) {
        for(int i=1;i<=n;i++) cout<<setw(5)<<a[i];
        cout<<endl;
        return ;
    }
    for(int i=1;i<=n;i++)
    {
        if(flag[i]==0){
            a[cur]=i;
            flag[i]=1;
            dfs(cur+1);
            a[cur]=0;
            flag[i]=0;
        }
    }
}
int main()
{
    cin>>n;
    dfs(1);
    return 0;
}