`
阿尔萨斯
  • 浏览: 4106738 次
社区版块
存档分类
最新评论

HDU 1016 Prime Ring Problem(DFS回溯+素数判断)

 
阅读更多

HDU 1016 Prime Ring Problem(DFS回溯+素数判断)

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

题意:给你一个n,要求输出所有由1,2,3…n构成的素数环。所谓素数环就是该环中的任意相邻两个数的和是一个素数。且按字典序从小到大输出。

分析:本题在刘汝佳的入门经典里也有。

首先利用素数筛选法求出100以内的所有素数。

然后用dfs从小到大依次选取所有数字来构成环,注意当选完最后一个数的时候要用它和1(首位的数)判断是否他们的和是一个素数。

AC代码:

#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=100;
int n;
int prime[maxn];//prime[i]=0表i为素数,=1表i非素数
int ans[maxn],vis[maxn];
void get_prime()
{
    memset(prime,0,sizeof(prime));
    for(int i=2;i<maxn;i++)if(!prime[i])
    {
        for(int j=i*i;j<maxn;j+=i)
            prime[j]=1;
    }
}
void dfs(int pos)//当前正在构造ans素数环的第pos个位置
{
    if(pos==n)
    {
        if(prime[ans[0]+ans[n-1]]==0)//头+尾=素数
        {
            printf("%d",ans[0]);
            for(int i=1;i<n;i++) printf(" %d",ans[i]);
            printf("\n");
        }
    }
    else for(int i=1;i<=n;i++)if(!vis[i] && !prime[ans[pos-1]+i])
    {
        vis[i]=1;
        ans[pos]=i;
        dfs(pos+1);
        vis[i]=0;//回溯
    }
}
int main()
{
    get_prime();
    int kase=1;
    while(scanf("%d",&n)==1)
    {
        printf("Case %d:\n",kase++);
        memset(vis,0,sizeof(vis));
        ans[0]=1;//素数环第一个位置固定为1
        vis[1]=1;
        dfs(1);
        printf("\n");
    }
    return 0;
}


分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics