素数环 NOJ 1104

素数环

时间限制(普通/Java) : 1000 MS/ 3000 MS 运行内存限制 : 65536 KByte
总提交 : 1018 测试通过 : 154

题目描述

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

输入

输入正整数n，1<n≤16。

输出

输出素数环序列，从整数1开始逆时针排列。

样例输入

样例输出

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

分析：回溯法比枚举排列法快了很多很多，即使n=16速度也不错。该函数取名为dfs并非巧合，从解答树的角度讲，回溯法正是按照深度优先的顺序在遍历解答数。

实现代码：

#include<cstdio>
#include<cstdlib>
#include<string.h>
int n;
int *A=new int[16];
int *vis=new int[17];
int *isp=new int[34];
void dfs(int cur)
{
    if(cur==n&&isp[A[0]+A[n-1]])
    {
        for(int i=0;i<n;i++) if(i==0) printf("%d",A[i]); else printf(" %d",A[i]);
        printf("
");
    }
    else for(int i=2;i<=n;i++)
    {
        if(!vis[i]&&isp[i+A[cur-1]])
        {
            A[cur]=i;
            vis[i]=1;
            dfs(cur+1);
            vis[i]=0;
        }
    }
}
int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++)  A[i]=i+1;
    memset(vis,0,sizeof(vis));
    memset(isp,0,sizeof(isp));
    isp[2]=1,isp[3]=1,isp[5]=1,isp[7]=1,isp[11]=1,isp[13]=1,isp[17]=1,isp[19]=1;isp[23]=1,isp[29]=1,isp[31]=1;
    dfs(1);
}