簡(jiǎn)單深搜。每次對(duì)第step個(gè)位置進(jìn)行測(cè)試，

for(i=2;i<=n;i++)

{

??????? if(第i個(gè)點(diǎn)沒(méi)有被訪問(wèn)過(guò)，并且和為質(zhì)數(shù))

??????? result[step]=i；???//則將這個(gè)數(shù)放入step的位置

????????visit[i]=1;???????????//并且對(duì)第 i ?個(gè)數(shù)進(jìn)行標(biāo)記，以后不再訪問(wèn)

???????? dfs(step+1);??????//對(duì)下一個(gè)點(diǎn)按相同規(guī)則進(jìn)行訪問(wèn)

?

}

我發(fā)現(xiàn)，深搜可以這樣理解：??????? 以某一個(gè)點(diǎn)為源點(diǎn)按確定的規(guī)則進(jìn)行搜索。如果他的下一個(gè)鄰接點(diǎn)可行（沒(méi)有被訪問(wèn)過(guò)，且符合規(guī)則），則記錄這個(gè)點(diǎn)，并標(biāo)記。 然后，重新以該點(diǎn)為新的源點(diǎn)進(jìn)行搜索。????????????? 如果不可行，則退回到上一步，繼續(xù)按規(guī)則進(jìn)行所示。?????????????????直到滿足結(jié)束條件。???

DFS即，每次一搜到底，不行就重新回溯。找一個(gè)方向或節(jié)點(diǎn)，再一搜到底。不行再回溯。

代碼：

#include<stdio.h>
#include<string.h>

int result[20];
bool isprime[]={0,0,1,1,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,0,0,0,0,1,0,1,0,0,0,0,0,1,0};
bool visit[20];
int n;
void dfs(int step)
{
?int i;
?if(step==n+1)
?{
??if(isprime[result[n]+1])???? //如果最后一個(gè)數(shù)（第n個(gè)數(shù)）和第一個(gè)數(shù)之和是質(zhì)數(shù)
??{
???for(i=1;i<=n;i++)
???{
????if(i==n) printf("%d\n",result[i]);
????else
????printf("%d ",result[i]);
???}
??}
??return ;
?}
?for(i=2;i<=n;i++)
?{
??if(!visit[i]&&isprime[i+result[step-1]])
??{
???result[step]=i;
???visit[i]=1;???????????? //訪問(wèn)過(guò)就進(jìn)行標(biāo)記
???dfs(step+1);
???visit[i]=0;
???
??}
?}
}
int main()
{
?int count=1;
?while(scanf("%d",&n)!=EOF)
?{
??memset(visit,0,sizeof(visit));
??result[1]=1;
??printf("Case %d:\n",count++);
??dfs(2);
??printf("\n");
?}
?return 0;
}

轉(zhuǎn)載于:https://www.cnblogs.com/zhangyabin---acm/archive/2012/03/04/2379093.html

總結(jié)

以上是生活随笔為你收集整理的第三道深搜-----------hdu1016的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。