素数环问题---深度搜索遍历

1264: 素数环

时间限制: 1 Sec  内存限制: 128 MB

提交: 29  解决: 8

[提交][状态][讨论版]

题目描述

有一个长度为n的环形序列由1,2,3,...,n组成，环中相邻两个整数和均为素数。你需要找到所有满足条件的环。

输入

输入n表示环的长度（n<=16）

输出

输出从整数1开始的逆时针排列的所有环。

样例输入

6

样例输出

1 4 3 2 5 6 
1 6 5 2 3 4 

提示

来源

西安交通大学复试机试题

[提交][状态]

 

#include
#include<string.h>//20以内的数最大和40 
int prime[40]={ 1,1,0,0,1,0,1,0,1,1,1,0,1,0,1,1,1,0,1,0,1,1,1,0,1,1,1,1,1,0,1,0,1,1,01,1,1,0,1,1};
int visit[21];
int ring[21];/*
void Is_prime()
{int i,j;prime[0]=prime[1]=1;for(i=2;i<=6;++i)for(j=i*i;j<40;j+=i)prime[j]=1;
}
*/
void DFS(int k,int n)
{int i;if(k==n+1&&prime[ring[n]+ring[1]]==0){//printf("1");for(i=1;i<=n;++i)printf("%d ",ring[i]);//不处理格式问题printf("
");return;}for(i=1;i<=n;++i){if(!visit[i]&&!prime[i+ring[k-1]]){visit[i]=1;ring[k]=i;DFS(k+1,n);visit[i]=0;//还原!! 很重要!!!
        }}
}int main()
{int T,n;T=1;
//    Is_prime();while(scanf("%d",&n)!=EOF){//printf("Case %d:
",T++);if(n==1){printf("1 
");continue;}if(n&1){//printf("No Answer
");continue;}memset(visit,0,sizeof(visit));visit[1]=ring[1]=1;DFS(2,n);}return 0;
}