素数环（Prime Ring Problem，UVa 524）

题目链接：http://acm.hust.edu.cn/vjudge/contest/view.action?cid=84562#problem/C

题意：

输入正整数n，把整数1，2，3，...，n组成一个环，使得相邻两个整数之和均为素数。输出时从整数1开始逆时针排列。同一个环应恰好输出一次。n<=16。

案例：

Sample Input

Sample Output

      Case 1:
        1 4 3 2 5 6
        1 6 5 2 3 4

       Case 2:
       1 2 3 8 5 6 7 4
        1 2 5 8 3 4 7 6
        1 4 7 6 5 8 3 2
        1 6 7 4 3 8 5 2

分析：

每个环对应于1~n的一个排列，但排列数高达16的阶乘，生成测试法超时，考虑采用回溯法，从解答树角度来讲，回溯法正是按照深度优先的顺序在遍历解答树。

源代码：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cmath>
 4 #include<cstring>
 5 using namespace std;
 6 int a[20],b[20],n;
 7 int prime(int m)
 8 {   if(m<=3) return 1;//数据2、3为素数
 9     int x,k=int(sqrt(m));//判断m是否为素数
10     for(x=2;x<=k;x++)
11         if(m%x==0)     return 0;    
12     return 1;
13 }
14 void dfs(int j)
15 {   int i;
16     if(j==n&&prime(a[n-1]+a[0]))//递归边界：第一个数和最后一个数
17     {  
18         for(i=0;i<n-1;i++)//输出符合要求的排列
19            cout<<a[i]<<' ';
20         cout<<a[n-1]<<endl;
21     }
22     else
23     { 
24         for(i=2;i<=n;i++)//尝试放置每个数i
25         {   
26             if(!b[i]&&prime(a[j-1]+i))//判断i值是否使用过，并与前一个数之和为素数
27             {  a[j]=i;
28                b[i]=1;//设置使用标志
29                dfs(j+1);
30                b[i]=0;//清除标志
31             }
32         }
33     }
34 }
35 int main()
36 {
37     int ant=0;//案例
38     while(cin>>n)
39     {
40         if(ant++) cout<<endl;
41         memset(a,0,sizeof(a));//数组清零
42         memset(b,0,sizeof(b));
43         a[0]=1;
44         printf("Case %d:
",ant);//输出格式控制
45         dfs(1);    //测试数据，找出排列        
46     }
47     return 0;
48 }