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