搜索算法之素数环

ゝ一纸荒年。 2022-06-02 03:52 242阅读 0赞

### 题目描述 ###

有一个整数n，把从1到n的数字无重复的排列成环，且使每相邻两个数（包括首尾）的和都为素数，称为素数环。

为了简便起见，我们规定每个素数环都从1开始。例如，下图就是6的一个素数环。

![20120315192417_81102.gif][]

### 输入 ###

有多组测试数据，每组输入一个n(0<n<20)，n=0表示输入结束。

### 输出 ###

每组第一行输出对应的Case序号，从1开始。
    如果存在满足题意叙述的素数环，从小到大输出。
    否则输出No Answer。

### 样例输入 ###

复制

6
    8
    3
    0

### 样例输出 ###

复制

Case 1:
    1 4 3 2 5 6
    1 6 5 2 3 4
    Case 2:
    1 2 3 8 5 6 7 4
    1 2 5 8 3 4 7 6
    1 4 7 6 5 8 3 2
    1 6 7 4 3 8 5 2
    Case 3:
    No Answer

### 提示 ###

无

### 来源 ###

nyoj

#include <stdio.h>
    
    #include <string.h>
    int n, flag=0;
    int primehuan[20], mark[20];//标记作用;
    int isprime(int n)//判断是否为素数
    {
        int i,flag=1;
        if(n==1)
            return 0;
        for(i=2; i<n; i++)
            if(n%i==0)
            {
                flag=0;
                break;
            }
        return flag;
    }
    void f(int a)
    {
        int i;
        if(a==n)//递归终止条件
        {
            if(isprime(primehuan[n-1]+1))//如果，最后一个数加1为素数，可构成素数环然后输出
            {
                for(i=0; i<n; i++)
                    printf("%d ",primehuan[i]);
                printf("\n");
                flag++;
            }
        }
        else
        {
            for(i=1; i<n; i++)
            {
                if(mark[i]==0&&isprime(primehuan[a-1]+i+1))//未标记，且当前数与前一个数相加可构成素数
                {
                    mark[i]=1;
                    primehuan[a]=i+1;
                    f(a+1);
                    mark[i]=0;
                }
            }
        }
    }
    int main()
    {
        int c=1;
        while(scanf("%d",&n)!=EOF)
        {
            if(n==0)
                break;
            memset(primehuan,0,sizeof(primehuan));
            memset(mark,0,sizeof(mark));
            printf("Case %d:\n",c++);
            primehuan[0] = 1;//素数环起始位置为1
            mark[0] = 1;//标记数组相应标记
            if(n == 1)//若n为1，直接输出1即可
            {
                printf("1\n");
                continue;//此处不能为break否则直接结束程序
            }
            if(n%2==1)//奇数无法构成素数环
            {
                printf("No Answer\n");
                continue;
            }
            f(1);
            if(flag==0)
                printf("No Answer\n");
        }
        return 0;
    }

[20120315192417_81102.gif]: http://oj.nyist.me/JudgeOnline/image/img/20120315192417_81102.gif