導引
如果我們想輸出一個數的全排列，eg：1,2,3 的全排列
那么就有123,132,213,231,312,321，這六種，
那如何用代碼實作呢？
for (int a = 1; a <= 3; a++)
{
for (int b = 1; b <= 3; b++)
{
for(int c=1;c<=3;c++)
if (a != b && a != c && b != c)
{
printf("%d%d%d", a, b, c);
}
}
}
暴力列舉是一種，但是如果數字編的更多呢？
如1,2，3,4,5,6,7,8,9呢？
如果我們還是一個一個列舉出來，別說計算機你也不愿意，
深度優化搜素（dfs）
它的基本形式是：
void dfs(int step)
{
//判斷邊界
//嘗試每一種可能
for (int i = 1; i <= n; i++)
{
//繼續下一步
dfs(step+1)
}
//回傳;
}
再回到剛才的問題
給出了n個數（假設是三個）
那么我們可以看做，將三張牌放入三個盒子，一共有多少種不同的擺法；
首先我們定義一個陣列來表示牌，一個陣列來判斷是否目前這個牌有沒有在手上，
int book[10]，a[10]；
如果目前這個盒子沒有牌
依次列舉下去，將手上的安裝（先1，再2，后3）放入盒子
for (int i = 1; i <= n; i++)
{
if (book[i] == 0)//此時牌在手上
{
a[step] = i;
bool[i] = 1;
}
}
接著，我們以相同的方法來處理下一個盒子（函式的遞回呼叫）
void dfs(int step)
{
for (int i = 1; i <= n; i++)
{
if (book[i] == 0)//此時牌在手上
{
a[step] = i;
bool[i] = 1;
dfs(step + 1)
}
}
return；
}
這樣，一輪下來，我們已經得到一個a陣列，a[1]==1,a[2]==2,a[3]==3
這時候，我們依次退回上一個盒子，拿回剛才放進去的牌，
當退到第二個盒子拿回2的時候，我們手上現在就有了兩張牌2,3.由于剛才
我們在第二個盒子放的是2，那么，我們根據上面所寫的，（先1，再2，后3）這時，第二個盒子就一個放入3.第三個盒子放入2.
此時，我們又得到一個a陣列，a[1]==1,a[2]==3,a[3]==2.
void dfs(int step)
{
for (int i = 1; i <= n; i++)
{
if (book[i] == 0)//此時牌在手上
{
a[step] = i;
book[i] = 1;
dfs(step + 1);
book[i] = 0;//將盒子的牌識訓
}
}
return；
}
我們依次將a陣列列印出來，就得到他的全排序
完整代碼如下
#include <stdio.h>
int a[10], book[10], n;
void dfs(int step)
{
if (step == n + 1)
{
for (int i = 1; i <= n; i++)
{
printf("%d ", a[i]);
}
printf("\n");
return;
}
for (int i = 1; i <= n; i++)
{
if (book[i] == 0)//此時牌在手上
{
a[step] = i;
book[i] = 1;
dfs(step + 1);
book[i] = 0;//將盒子的牌識訓
}
}
return;
}
int main()
{
scanf("%d", &n);
dfs(1);//從第一個盒子開始
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/234245.html
標籤：其他
上一篇：資料結構前言