欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Prime Ring 补充素数筛选表

程序员文章站 2024-03-15 15:06:53
...

素数环问题经单的深搜题目;

题意是这样的:

给你n个数(n<=20):1,2,3,4,5....n;把这n个数围成一个圈,每相邻的两个数之和为素数,而且,第一个数必须是1,以避免不必要的重复;

题意很简单,关键是程序的实现,这就用到了深搜;

先说什么是深搜,就是不撞南墙不回头,找准一个方向不达目的誓不罢休,也就是暴力枚举加上限制条件,再通过递归实现;

那么,说说这个题的思路:

假设n是6;

因为第一个必须是1,所以直接从第二个数找;把2放在第二个数的位置,判断1+2=3是素数,在找第三个,把3放在这里,判断2+3=5是素数;第四个放4,3+4=7是素数;第五个放5,4+5=9不是素数,第五个放6,4+6=10不是素数; 6后边没有数可用,再返回第四个,5放在第四个格子,3+=8不行;放6,3+6=9,不行,返回第三个格子,放4,2+4=6,不行;放5,2+5=7可以,再到第四个格子,注意前边已经放了1,2,5,所以这三个数不能用,放3,5+3=不行;放4,5+4=9不行,放6,5+6=11可以,第五个格子,放3,6+3=9不行,放4,6+4=10,不行,返回第五个格子,返回第四个格子,第四个格子已经试到6,返回第三个格子,放6,2+6=8不行,返回第二个格子,放3,1+3=4不行;放4,1+4=5可以,第三个格子,放2不行,放3可以;第四个格子放2可以,第五个放5可以,第六个放6可以,注意六个数虽然已经找完,但他是个环,所以还要判断最后一个和第一个的和:6+1=7可以,所以1,4,3,2,5,6是一种答案;

是不是已经看晕了呢?下面再看看这部分的实现代码:

void dsf(int step){  //step表示第几步,放第几个数;
    if(step==n+1){    //n个数放完,判断第一个和最后一个和是否为素数;
        if(prime[1+a[step-1]])
            print();
        return;
    }
    int i;

    for(i=2; i<=n; i++){

        if(prime[i+a[step-1]] && !book[i]){
            a[step]=i;
            book[i]=1;   //标记该数已使用;
            dsf(step+1);
            book[i]=0;//标记清除,一定不要忘记这一步;
        }
    }
    return;
}


其中有个素数的判断,因为范围不大,直接建个表,prime[40],是素数标记为1,反之标记为0;

void IsPrime(){//初始化prime数组全为1;
    int i, j;
    for(i=2; i<=40; i++)
        if(prime[i])//prime[i]==1,i是素数,则i的倍数不是素数,标记为0;
        for(j=i+i; j<=40; j+=i)
        prime[j]=0;
    return;
}



下面奉上全部代码:
#include 
#include 
int prime[45];
int book[45];
int a[25];
int n;
void IsPrime(){
    int i, j;
    for(i=2; i<=40; i++)
        if(prime[i])
        for(j=i+i; j<=40; j+=i)
        prime[j]=0;
    return;
}
void print(){
    int i;
    for(i=1; i<=n; i++){
        if(i==n)
            printf("%d\n",a[i]);
        else
            printf("%d ",a[i]);
    }
    return;
}
void dsf(int step){
    if(step==n+1){
        if(prime[1+a[step-1]])
            print();
        return;
    }
    int i;

    for(i=2; i<=n; i++){

        if(prime[i+a[step-1]] && !book[i]){
            a[step]=i;
            book[i]=1;
            dsf(step+1);
            book[i]=0;
        }
    }
    return;
}
int main(){
    int cnt=0;
    while((scanf("%d",&n))!=EOF){
        cnt++;
        int i;
        printf("Case %d:\n",cnt);
        for(i=2; i<=40; i++){
            prime[i]=1;
            book[i]=0;
        }
        IsPrime();
        a[1]=1;
        book[1]=1;
        dsf(2);
        printf("\n");
    }
    return 0;
}