杭電1016Prime Ring Problem

Prime Ring Problem

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)

Total Submission(s): 25319    Accepted Submission(s): 11301

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
        

此題要用到遞歸

代碼：

#include<stdio.h>

//此函數為判斷素數

int prime(int m)

{

    int n = 0 ;

    for(int i = 2 ; i < m ; i++)

    {

        if(m % i == 0 )

            n++;

    }

    if( n==0 )

        return 1;

    else

        return 0;

}

//遞歸

int a[100];

int flag[100] = {0};

void DFS(int x,int n)

{

    int i = 0 , j = 0 , m = 0 ;

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

    {

        int m = 0 ;

        m = prime(a[x-1]+i);

        if(m == 0 || flag[i])//判斷當兩個數相加不是素數并且這個數被标記

           continue;

        a[x] = i ;   

        flag[i] = 1;

        DFS(x+1,n);

        flag[i] = 0 ;

    }

    if(prime(a[x - 1]+1) == 1 && x == n)

    {

        for( i = 0 ; i < n-1 ; i++)

           printf("%d ", a[i]);

        printf("%d\n",a[n-1]);

        return ;

    }

}

int main()

{

    int n = 0 , b = 1 ;

    while(~scanf("%d",&n))

    {

        a[0] = 1 ;

        int x = 1 ;

        printf("Case %d:\n",b);

        DFS(x,n);

        printf("\n");

        b++;

    }

return 0;

}