素数环问题---回溯

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 
 7 const int maxn =1e3;
 8 int isp[maxn];
 9 int A[maxn];
10 int n;
11 int ans=0;
12 
13 int is_prime(int x){
14     for( int i=2; i*i<=x; i++ ){
15         if(x%i==0) return 0;
16     }
17     return 1;
18 }
19 
20 int main(){
21     cin>>n;
22     for( int i=2; i<=n*2; i++ ) isp[i]=is_prime(i);/*生成素数表，加快后续判断*/
23     for( int i=0; i<n; i++ ) A[i]=i+1;
24     do{
25         int flag=1;
26         for(int i=0; i<n; i++ ){
27             if(!isp[A[i]+A[(i+1)%n]]){/*不是素数，这种排列方式行不通*/
28                 flag=0;
29                 break;
30             }
31         }
32         if(flag){
33             ans++;
34             for( int i=0; i<n; i++ ) cout<<A[i]<<" ";
35                 cout<<endl;
36         }
37     }while(next_permutation(A+1,A+n));/*第一个位置是1！*/
38     cout<<ans<<endl;
39     return 0;
40 }

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 using namespace std;
 5 
 6 const int maxn =1000;
 7 int vis[maxn];
 8 int A[maxn];
 9 int isp[maxn];
10 int n;
11 int ans=0;
12 
13 int is_prime(int x){
14     for( int i=2; i*i<=x; i++ ){
15         if(x%i==0) return 0;
16     }
17     return 1;
18 }
19 
20 void dfs(int cur){
21     if(cur==n&&isp[A[0]+A[n-1]]){
22         ans++;
23         for( int i=0; i<n; i++ ) cout<<A[i]<<" ";
24         cout<<endl;
25     }
26     else{
27         for(int i=2; i<=n; i++ ){
28             if(!vis[i]&&isp[i+A[cur-1]]){/*i这个数没被用过，并且符合前后两个数相加为素数的要求*/
29                 A[cur]=i;/*采用这个数*/
30                 vis[i]=1;/*设置使用标志*/
31                 dfs(cur+1);
32                 vis[i]=0;/*消除标志*//*回溯的本质*/
33             }
34         }
35     }
36 }
37 int main(int argc, char const *argv[])
38 {
39     cin>>n;
40     memset(vis,0,sizeof(vis));
41     for( int i=2; i<=n*2; i++ ) isp[i]=is_prime(i);
42     A[0]=1;/*题目中规定从1开始*/
43     dfs(1);
44     cout<<ans<<endl;
45 
46     return 0;
47 }