hdoj--1016<dfs>

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1016

题目描述：1～n的整数排成一个环，首尾相连，相邻的两个数相加是素数，输出满足的排列，1开头输出，字典序；

题目要点：dfs

     本题安顺序dfs，可以满足字典序，对于每一个要放进去的数要考察两个，一、是否放过了。二、是否和前面相邻的数构成素数；

所以第一，开一个数组，记录该数是否被放过；第二，写一个判断素数的函数；

代码如下:

(当只有一个元素的时候比较特殊，要考虑到)

#include<stdio.h>
#include<string.h>
int n,b[25],a[25],t=1;//b数组用来放数；a数组用来记录；
int prime(int x)
{
        for(int i=2;i<x;i++)
        {
            if(x%i==0)
                return 0;
        }
        return 1;
}
void dfs(int cur)//cur记录的是这一次放大色是第几个数；
{
    if(cur>n)   //注意这里一直放到第n+1个，然后比较1和b【n】是否是素数；
    {  
        if(prime(1+b[n])){
         printf("%d",b[1]);
         for(int i=2;i<=n;i++)
         {
             printf(" %d",b[i]);
         }
         printf("
");
        }
    }
    else
    {
        for(int i=2;i<=n;i++)
        {
            if(a[i]==0&&prime(i+b[cur-1]))
            {
                b[cur]=i;a[i]=i;
                dfs(cur+1);a[i]=0;
            }

        }
    }
}
int main()
{
    while(scanf("%d",&n)!=EOF)
    {
        printf("Case %d:
",t++);
        memset(a,0,sizeof(a));
        b[1]=1;//一开头是固定的，直接赋值就好了。
        if(n==1)//如果只有一个数，算是符合要求直接输出就好；
        {
            printf("1

");
            continue;
        }
        dfs(2);//从2开始dfs
        printf("
");
    }
    return 0;
}