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

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<stdio.h>
#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;
}