dfs思想
思想是從一個頂點開始，沿著一條路一直走到底，如果發現不能到達目標解，那就回傳到上一個節點，然后從另一條路開始走到底，
全排列問題
題目
排列與組合是常用的數學方法，
先給一個正整數 ( 1 < = n < = 10 )
例如n＝3，所有組合,并且按字典序輸出：
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
輸入
輸入一個整數n( 1<=n<=10)
輸出
輸出所有全排列
每個全排列一行，相鄰兩個數用空格隔開（最后一個數后面沒有空格）
#include<bits/stdc++.h>
using namespace std;
const int N = 15;
int n;
int p[N];
bool vis[N];//判斷用沒用過
void dfs(int u) {
if(u == n) //u是從零開始
{
for(int i = 0; i < n; i ++)
cout<<p[i]<<" ";
printf("\n");//endl容易超時
return;
}
for(int i = 1;i <= n;i ++)
{
if(!vis[i]){
p[u] = i;
vis[i] = true;
dfs(u + 1);
vis[i] = false;//恢復現場
}
}
}
int main ()
{
cin>>n;
dfs(0);
return 0;
}
組合數問題
題目
排列與組合是常用的數學方法，其中組合就是從n個元素中抽出r個元素(不分順序且r < ＝ n)，我們可以簡單地將n個元素理解為自然數1，2，…，n，從中任取r個數，
現要求你不用遞回的方法輸出所有組合，
例如n ＝ 5 ，r ＝ 3 ，所有組合為：
1 2 3
1 2 4
1 2 5
1 3 4
1 3 5
1 4 5
2 3 4
2 3 5
2 4 5
3 4 5
輸入
一行兩個自然數n、r ( 1 < n < 21，1 < ＝ r < ＝ n )，
輸出
所有的組合，每一個組合占一行且其中的元素按由小到大的順序排列，所有的組合也按字典順序，
#include<bits/stdc++.h>
using namespace std;
const int N = 22;
int p[N];
bool vis[N];//標記
int n, r;
void dfs(int u) {
if (u == r)
{
for (int i = 0; i < r; i ++)
cout<<p[i]<<" ";
printf("\n");
return ;
}
for(int i = 1; i <= n; i ++) //** 法2：for(int i = p[u-1] + 1; i <= n; i ++)
{
if (!vis[i] && i > p[u-1]) //剪枝：要求是順序輸出 //法2：if(!vis[i])
{
p[u] = i;
vis[i] = true;
dfs(u + 1);
vis[i] = false;//恢復現場
}
}
}
int main()
{
cin>>n>>r;
dfs(0);
return 0;
}
記住每次遞回完后要恢復現場
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/274137.html
標籤：其他