追溯法应用举例1-素数环

UVA524

模拟全排列过程即可。

注意：由于输出要求是从1开始，所以排列递归的第一层其实只允许填入1，这个操作节省了相当庞大的举例过程。

具体代码如下：

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #include<math.h>
 5 using namespace std;
 6 int isp[50];
 7 int aim[20];
 8 int kase;
 9 int isprime(int n)
10 {
11     if(n==1)return 0;
12     if(n==2)return 1;
13     for(int i=2;i<=sqrt(n);i++)
14         if(n%i==0)return 0;
15     return 1;
16 }
17 
18 int pre()//预先处理，方便查找
19 {
20     memset(isp,0,sizeof(isp));
21     for(int i=1;i<50;i++)
22         if(isprime(i))isp[i]=1;
23     return 0;
24 }
25 
26 int solve(int n,int cur)
27 {
28     if(n==cur&&aim[0]==1&&isp[aim[n-1]+1])
29     {//最后元素与第一个元素的和是否为素数
30         //
31         printf("%d",aim[0]);
32         for(int i=1;i<n;i++)
33             printf(" %d",aim[i]);
34         printf("
");
35     }
36     else
37     {
38         for(int i=1;i<=n;i++)
39         {
40             if(cur==0&&i!=1)continue;//要求第一层只允许填入1这个数字
41             int ok=1;
42             for(int k=0;k<cur;k++)
43                 if(aim[k]==i){ok=0;break;}
44             if(ok&&cur!=0&&(!isp[i+aim[cur-1]]))ok=0;//增加了一个判断
45             if(ok)
46             {
47                 aim[cur]=i;
48                 solve(n,cur+1);
49             }//if
50         }//for
51     }//else
52     return 0;
53 }
54 
55 int main()
56 {
57     int n;
58     int c=0;
59     pre();
60     while(~scanf("%d",&n))
61     {
62         if(c)printf("
");
63         c=1;
64         printf("Case %d:
",++kase);
65         memset(aim,0,sizeof(aim));
66         solve(n,0);
67     }
68     return 0;
69 }