本題鏈接：點擊打開鏈接

本題大意：

? ? ? ? 輸入一個數(shù)n表示須要查找的數(shù)有n個，而且這些數(shù)連成一個環(huán)，隨意兩個相鄰的數(shù)之和都為素數(shù)。

解題思路：

? ? ? ? 就是從1開始對每一個點進行查找，符合條件的點就存到一個數(shù)組中，標(biāo)記找過的點。查找完一次就進行輸出。然后取消標(biāo)記繼續(xù)查找，直至將1～n中的點從小到大均查找一次。詳細請參考代碼：

#include<stdio.h> #include<string.h> int mark[22]; int num[22]; int prime_num[12]={2,3,5,7,11,13,17,19,23,29,31,37}; int n; int is_prime(int a) {for(int i=0;i<12;i++)if(a==prime_num[i])return 1;return 0; } void print_num() {for(int i=1;i<n;i++)printf("%d ",num[i]);printf("%d\n",num[n]); } int dfs(int per,int post,int flag)//三個變量依次為此位置。與此位置相連的下一個位置，num數(shù)組中存放的位置 {if(!is_prime(per+post))//若此位置與下一位置之和不是素數(shù)，則不滿足條件。返回 return 0;num[flag]=post;//若滿足條件，記下“下一個位置”到num數(shù)組中 if(flag==n&&is_prime(post+1))//若已查找到了n個數(shù)，而且第n個數(shù)與最先的位置1之和也為素數(shù) {print_num();//則查找到一組，進行輸出 return 1;//結(jié)束此次查找 }mark[post]=1;//若還沒有查找完，則繼續(xù)查找，將已經(jīng)找過的點標(biāo)記 for(int i=2;i<=n;i++)if(!mark[i]&&dfs(post,i,flag+1))break;mark[post]=0;//查找完一次后。可能還存在其它序列，所以取消標(biāo)記，使后面可繼續(xù)進行查找 return 0; } int main() {int t=1;while(scanf("%d",&n)!=EOF){for(int i=1;i<=n;i++){mark[i]=0;//標(biāo)記該數(shù)是否使用過 }num[1]=1;//存放序列，1肯定在 printf("Case %d:\n",t++);if(n==1)printf("1\n");for(int i=2;i<=n;i++)//首先查找1的下一位 dfs(1,i,2);//2表示i在num數(shù)組中存放的位置 printf("\n");}return 0; }

總結(jié)

以上是生活随笔為你收集整理的hdu 1016 Prime Ring Problem(DFS)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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