原题大意

如图,6个数收尾相连,任意两个相邻的数之和是质数.现在请你输入数字n,表示从1到n的整数,将它们排列成一个环,形成如图所示的质数环.

算法分析

用dfs遍历每种情况

代码程序

程序1

#include <stdio.h>
#include <math.h>
#include <memory.h>
#define N 20
int a[N],b[N];
int n;
int c=0;
int is_prime(int t)//判断是否是质数
{
    int i;
    if(t==1)    return 0;
    for(i=2;i<=sqrt(t);i++)
    {
        if(t%i==0)    return 0;    
    }
    return 1;    
}
int check(int t,int m)//检查有没有与之前的数重复
{
    int i;
    for(i=0;i<m;i++)
        if(t==b[i])
            return 0;
    return 1;
}
void ring(int num)
{
    int i;
    if(num==n&&is_prime(b[n-1]+1))    //最后要与第一个数连起来
    {
        for(i=0;i<n-1;i++)
            printf("%d ",b[i]);//!此处输出格式很重要
            printf("%d",b[i]);
        printf("\n");
    }
    else
    {
        for(i=1;i<n;i++)
            {
                if(check(a[i],num)&&is_prime(a[i]+b[num-1]))
                    {
                        b[num]=a[i];
                        ring(num+1);    
                    }    

            }
    }
}
int main()
{
    int i;
    while(scanf("%d",&n)!=EOF)
    {
        c++;
        printf("Case %d:\n",c);
        for(i=0;i<n;i++)
        {
            a[i]=i+1;
        }
        memset(b,0,sizeof(b));
        b[0]=1;
        ring(1);
        printf("\n");
    }
    return 0;
}

程序2

#include <stdio.h>
#include <math.h>
#include <memory.h>
#define N 20
int a[N];
int b[N]={0};//记录a中对应的数有没有被用过
int n;
int c=0;
int is_prime(int t)//同上
{
    int i;
    if(t==1)    return 0;
    for(i=2;i<=sqrt(t);i++)
    {
        if(t%i==0)    return 0;    
    }
    return 1;    
}
void ring(int num)//同上
{
    int i;
    if(num==n&&is_prime(a[num-1]+1))
    {
        for(i=0;i<n-1;i++)
        {
            printf("%d ",a[i]);
        }
            printf("%d",a[i]);
        printf("\n");
    }
    else
    {
        for(i=2;i<=n;i++)
        {
            if(!b[i]&&is_prime(i+a[num-1]))
                {
                    a[num]=i;
                    b[i]=1;
                    ring(num+1);
                    b[i]=0;//一定要改回来
                }
        }
    }
}
int main()
{
    int i;
    while(scanf("%d",&n)!=EOF)
    {
        c++;
        printf("Case %d:\n",c);
        memset(b,0,sizeof(b));
        a[0]=1;
        ring(1);
        printf("\n");
    }
    return 0;
}

注意事项

由于这是acm题,所以输入输出的格式很重要,我的代码里有一段是这样写的:

if(num==n&&is_prime(a[num-1]+1))
    {
        for(i=0;i<n-1;i++)
            printf("%d ",a[i]);
        printf("%d",a[i]);
        printf("\n");
    }

看上去很奇怪,因为一般我是这样写的:

if(num==n&&is_prime(a[num-1]+1))
{
    for(i=0;i<n;i++)
        printf("%d ",a[i]);
    printf("\n");
}

这是因为每行数据的最后一个输出的数后不用空格,否则就算格式不对.

总结

我写了两段代码,这两段代码都AC了,区别有两处:

检查重复的方法不一样,第一种是写了个函数,第二种是用数组保存.
第一种用了数组保存前n个数,第二种是边选边填.

所以,综合下来,第二段代码更好一些,占的内存和运行时间也更快.