【问题描述】
一个大小为N(N<=17)的质数环是由1到N共N个自然数组成的一个数环，数环上每两个相邻的数字之和为质数。如下图是一个大小为6的质数环。为了方便描述，规定数环上的第一个数字总是1。如下图可用1 4 3 2 5 6来描述。若两个质数环，数字排列顺序相同则视为本质相同。现在要求你求出所有本质不同的数环。
【算法分析】
简单DFS回溯实现，注意当N为奇数时直接退出程序，否则当N=17时会超时。
1 #include<iostream> 2 #include<cstring> 3 #include<cmath> 4 using namespace std; 5 int n,a[20]; 6 bool b[20]; 7 bool pd(int x,int y){ 8 int k=2; int i=x+y; 9 while (k<=floor(sqrt(i))&&i%k) k++; 10 if (k>floor(sqrt(i))) return 1; 11 return 0; 12 } 13 void print(){ 14 for (int i=1;i<=n;++i) cout<<a[i]<<" "; 15 cout<<endl; 16 } 17 void DFS(int t){ 18 if (t>n&&pd(a[n],a[1])) { 19 print(); 20 return; 21 } 22 for (int i=2;i<=n;++i) 23 if (b[i]&&(a[t-1]+i)%2&&pd(a[t-1],i)){ 24 a[t]=i; b[i]=0; 25 DFS(t+1); b[i]=1; 26 } 27 } 28 int main(){ 29 cin>>n; a[1]=1; 30 if (n%2) return 0; 31 memset(b,1,sizeof(b)); 32 DFS(2); 33 return 0; 34 }
声明：本博文为博主原创博文，未经允许请勿转载。
原文：http://www.cnblogs.com/Double680/p/5207405.html