[置頂] 深度優先搜索與全排列
來源：程序員人生 發布時間：2015-07-28 08:04:47 閱讀次數：3573次
做題進程中我們常常會遇到這樣的問題：
輸入1個數n,輸出1-n的全排列。可能很多人會想到枚舉暴力，這里給大家介紹1種算法：深度優先搜索
在這里舉個簡單的例子
假設有編號為1 、2、3 的3 張撲克牌和編號為l 、2 、3 的3 個盒子。
現在需要將這3 張撲克牌分別放到3 個盒子里面，并且每一個盒子有且只能放1張撲克牌。那末1共有多少種不同的放法呢？
首先 我們應當設置1個標志數組 book 記錄當前數字是不是被使用過。
然后用1個數組a 表示盒子并且初始化a[i]=i;
代碼以下：
#include<stdio.h>
int n,a[10],book[10];//特別說明c語言全局變量沒有賦值默許為 0,無需再次初始化；
void dfs(int step)//step 表示當前在第幾個位置
{
int i;
if(step==n+1)//如果step==n+1表示前n個數字已放好
{
//輸出1種全排列
for(i=1;i<=n;i++)
printf("%d",a[i]);
printf("
");
return;
}
//每次搜索都從1-n 逐一嘗試
for(i=1;i<=n;i++)
{
if(book[i]==0)//判斷次數字是不是用過
{
a[step]=i;//存儲當前位置的數字，以便滿足條件輸出
book[i]=1;//當前數字已用過，改變標志，以防重用
dfs(step+1);//放好當前位置數字以后，安排下1個數字
book[i]=0;//回溯，當滿足1種全排列后，進行下1種嘗試
}
}
return ;
}
int main()
{
scanf("%d",&n);//輸入只能為1⑼之間的整數，表示1-n的全排列
dfs(1);//從第1個位置開始
return 0;
}
同時總結了下基本模型，希望有用：
void dfs(int step)
{
判斷邊界
嘗試每種可能
for(i=1;i<=n;i++)
{
繼續下1步dfs(step+1);
}
返回
}
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
