第一种：DFS法
#include<stdio.h>
int num[21],mark[21],n; int prime_num[12]={2,3,5,7,11,13,17,19,23,29,31,37}; 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",num[n]); } int dfs(int pre,int post,int flag) { //如果不符合，直接返回 if(!is_prime(pre+post)) return 0; num[flag]=post; if(flag==n&&is_prime(post+1))//判断长度是否达到n且最后一个数加上环的起点1是否是素数 { print_num(); printf("\n"); return 1; } mark[post]=0;//把这个数字标记成0表示已经用过了 for(int i=2;i<=n;i++)//开始搜索下一位 if(mark[i]!=0&&dfs(post,i,flag+1)) break; mark[post]=1;//标记位回复原状，因为没用上 return 0; } int main() { int ca=1; while(scanf("%d",&n)!=EOF&&n) { printf("Case %d:\n",ca++); for(int i=1;i<=n;i++) mark[i]=1;//初始化标记数组 num[1]=1; if(n==1) printf("1\n"); else if(n%2)//不存在长度大于1的奇数环 printf("No Answer\n"); else { for(int i=2;i<=n;i++) dfs(1,i,2);//(前面的数，之后的数，序数（长度）) } } return 0;}
第二种 回溯法
#include<iostream>#include<string.h>#define N 25#define M 40using namespace std;bool is_prime[M],Visited[N];int n,test,ans[N];bool prime(int n){ if(n==1) return false; if(n==2||n==3) return true; int i; for(i=2;i<n;i++) if(n%i==0) return false; return true;}void work(int k){ int i; if(k==n+1)//搜索到了足够的元素，结束并输出。 { if(!is_prime[ans[n]+ans[1]]) return ; for(i=1;i<=n-1;i++) cout<<ans[i]<<" "; cout<<ans[i]<<endl; return; } for(i=2;i<=n;i++) { if(!Visited[i]&&is_prime[ans[k-1]+i]) { Visited[i]=true;//把这个数字标记成true表示已经用过了 ans[k]=i; work(k+1); Visited[i]=false;//标记恢复原状，因为没用上 } } } int main() { int i; test=1; for(i=1;i<M;i++) is_prime[i]=prime(i); while(cin>>n) { ans[1]=1; memset(Visited,false,sizeof(Visited)); cout<<"Case "<<test<<":"<<endl; work(2); test++; cout<<endl; } return 0; }
