hdoj 1016 Prime Ring Problem

Problem Description

A ring is compose of n circles as shown in diagram. Put natural number 1, 2, ..., n into each circle separately, and the sum of numbers in two adjacent circles should be a prime.

Note: the number of first circle should always be 1.

 

Input

n (0 < n < 20).

 

Output

The output format is shown as sample below. Each row represents a series of circle numbers in the ring beginning from 1 clockwisely and anticlockwisely. The order of numbers must satisfy the above requirements. Print solutions in lexicographical order.

You are to write a program that completes above process.

Print a blank line after each case.

 

Sample Input

6

8

 

Sample Output

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

 

题目大意：

给出一个数n,将从1到n的数全排列，将相邻两个数互为素数且第一个数为1，第一个数与最后一个数也互为素数的排列进行输出

 

#include <stdio.h>
#include <string.h>
int n;
int vis[30], a[30];//数组vis记录改点是否被访问过，数组a记录符合条件的数
int judge(int s)//判断s是否是素数
{
    int flag = 1;
    for(int i = 2; i <= s/2; i++)
    {
        if(s%i == 0)
        {
            flag = 0;
            break;
        }
    }
    return flag;
} 
void dfs(int s, int cnt)//利用深搜来解决该问题，cnt是将要往数组中放入第几个数，s是放入数组中的末端的数
{
    int i, j;
    if(cnt  == n+1 && judge(a[1]+a[n]))//当放入数组中的数（cnt-1)等于n时，且数组第一个数与最后一个数也互为素数时，进行输出
    {
        for(j = 1; j < n+1; j++)
        {
            if(j != 1)
                printf(" ");
            printf("%d", a[j]);
        }
        printf("
");
        return ;
    }
    for(i = 1; i <= n; i++)
    {
        if(judge(i + s) && !vis[i])//如果i与s互为素数并且i没有被访问过时，访问i,将i放入数组中
        {
            a[cnt] = i;
            vis[i] = 1;
            dfs(i, cnt + 1);//i进行与它上一个数相同的操作，将要往数组中放入第cnt+1个数
            vis[i] = 0;//返回后，要将i标记为未访问
            
        }
    }
    return ;
}
int main()
{
    int num = 1;
    while(~scanf("%d", &n))
    {
        printf("Case %d:
", num++);
        memset(vis, 0, sizeof(vis));
        vis[1] = 1;//将1标记为已访问
        a[1] = 1;//将1放入数组中
        dfs(1, 2);
        printf("
");
    }
    return 0;
}