深搜 dfs 手算到機算 入門 排列數
總目錄：從手算到機算 算法競賽入門篇
1.洛谷 P1706 全排列問題
AC代碼(标準代碼)如下：
#include <bits/stdc++.h>
int n,a[20],vis[20];
void dfs(int step){
int i;
if(step==n+1){
int j;
for(j=1;j<=n;j++)printf("%5d",a[j]);
printf("\n");
return;
}
for(i=1;i<=n;i++)
if(!vis[i]){
vis[i]=1;
a[step]=i;
dfs(step+1);
vis[i]=0;
}
}
int main(){
scanf("%d",&n);
dfs(1);
return 0;
}
上述 标準代碼 執行樣例 的手算過程 如下：
輸入：
3
輸出：
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
初始：
數組vis位置1 2 3
數組vis數值0 0 0
數組a位置 1 2 3
數組a數值 0 0 0
第1次執行完畢：
數組vis位置1 2 3
數組vis數值1 0 0
數組a位置 1 2 3
數組a數值 1 0 0
第2次執行完畢：
數組vis位置1 2 3
數組vis數值1 1 0
數組a位置 1 2 3
數組a數值 1 2 0
第3次執行完畢：
數組vis位置1 2 3
數組vis數值1 1 1
數組a位置 1 2 3
數組a數值 1 2 3
列印: 1 2 3
第4次執行完畢：
數組vis位置1 2 3
數組vis數值1 0 1
數組a位置 1 2 3
數組a數值 1 3 3
第5次執行完畢：
數組vis位置1 2 3
數組vis數值1 1 1
數組a位置 1 2 3
數組a數值 1 3 2
列印: 1 3 2
第6次執行完畢：
數組vis位置1 2 3
數組vis數值0 1 0
數組a位置 1 2 3
數組a數值 2 3 2
第7次執行完畢：
數組vis位置1 2 3
數組vis數值1 1 0
數組a位置 1 2 3
數組a數值 2 1 0
第8次執行完畢：
數組vis位置1 2 3
數組vis數值1 1 1
數組a位置 1 2 3
數組a數值 2 1 3
列印: 2 1 3
以下依次類推......
以下代碼為針對n=3時的循環代碼寫法，有助于了解深搜dfs的實作過程。
#include <bits/stdc++.h>
int n,a[20],vis[20];
int main(){
int i1,i2,i3;
n=3;
for(i1=1;i1<=n;i1++)//對應dfs中step=1的情況
if(!vis[i1]){
vis[i1]=1;
a[1]=i1;
for(i2=1;i2<=n;i2++)//對應dfs中step=2的情況
if(!vis[i2]){
vis[i2]=1;
a[2]=i2;
for(i3=1;i3<=n;i3++){//對應dfs中step=3的情況
if(!vis[i3]){
vis[i3]=1;
a[3]=i3;
for(int j=1;j<=n;j++)printf("%5d",a[j]);
printf("\n");
vis[i3]=0;
}
}
vis[i2]=0;
}
vis[i1]=0;
}
return 0;
}
2.洛谷 P1008 三連擊
AC代碼如下：
#include <stdio.h>
#include <string.h>
int a[10];
int visited[10];
int n=9;
void dfs(int step){
int b,c,d;
int i;
b=a[1]*100+a[2]*10+a[3];
c=a[4]*100+a[5]*10+a[6];
d=a[7]*100+a[8]*10+a[9];
if(step==n+1){
if(c==2*b&&d==3*b)
printf("%d %d %d\n",b,c,d);
return;
}
for(i=1;i<=9;i++)
if(visited[i]==0){
a[step]=i;
visited[i]=1;
dfs(step+1);
visited[i]=0;
}
}
int main(){
memset(visited,0,sizeof(visited));
dfs(1);
return 0;
}
3.洛谷 P1618 三連擊（更新版）
AC代碼如下：
#include <stdio.h>
#include <string.h>
int A,B,C;
int a[10],vis[10];
int count=0;
void dfs(int step){
int i;
int b1,b2,b3;
if(step==10){
b1=a[1]*100+a[2]*10+a[3];
b2=a[4]*100+a[5]*10+a[6];
b3=a[7]*100+a[8]*10+a[9];
if(b1*B*C==b2*A*C&&b2*A*C==b3*A*B){
count++;
printf("%d %d %d\n",b1,b2,b3);
}
}
for(i=1;i<=9;i++)
if(vis[i]==0){
vis[i]=1;
a[step]=i;
dfs(step+1);
vis[i]=0;
}
}
int main(){
memset(vis,0,sizeof(vis));
scanf("%d%d%d",&A,&B,&C);
dfs(1);
if(count==0)
printf("No!!!\n");
return 0;
}
4.洛谷 P1036 選數
AC代碼如下：
#include <stdio.h>
int a[25],b[25],cnt,n,k;
int isPrime(int x){
if(x==1)return 0;
if(x==2)return 1;
for(int i=2;i*i<=x;i++)
if(x%i==0)return 0;
return 1;
}
void dfs(int step){
int i;
if(step==k+1){
int j,sum=0;
for(j=1;j<=k;j++)sum+=a[b[j]];
if(isPrime(sum))cnt++;
return ;
}
for(i=b[step-1]+1;i<=n;i++)
b[step]=i,dfs(step+1);
}
int main(){
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
b[0]=0,dfs(1);
printf("%d\n",cnt);
return 0;
}