`
java-mans
  • 浏览: 11344153 次
文章分类
社区版块
存档分类
最新评论

HDU-1016-Prime Ring Problem

 
阅读更多

HDU-1016-Prime Ring Problem

http://acm.hdu.edu.cn/showproblem.php?pid=1016

基本的DFS,先打个素数表即可

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
int prime[50];
int visit[30];
int num[30];
int n;
void init()
{
    int i,j;
    memset(prime,0,sizeof(prime));  //标记0为素数,1为合数
    for(i=3;i<=25;i+=2)
    if(prime[i]==0)
    {
        for(j=3*i;j<=50;j+=2*i)
        prime[j]=1;
    }
    for(i=4;i<=50;i+=2)
    prime[i]=1;
}
void dfs(int x)
{
    int i;
    if(x==n+1&&prime[num[x-1]+1]==0)
    {
        for(i=1;i<=x-1;i++)
        printf(i==x-1?"%d\n":"%d ",num[i]);
        return;
    }
    for(i=2;i<=n;i++)
    if(!visit[i])
    {
        if(prime[num[x-1]+i]==0)
        {
            num[x]=i;
            visit[i]=1;
            dfs(x+1);
            visit[i]=0;
        }
    }
    return;
}
int main()
{
    int t=1;
    init();
    while(scanf("%d",&n)!=EOF)
    {
        printf("Case %d:\n",t++);
        if(n%2==1)
        {
            printf("\n");
            continue;
        }
        memset(visit,0,sizeof(visit));
        visit[1]=1;
        num[1]=1;
        dfs(2);
        printf("\n");
    }
    return 0;
}


分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics