HDU 1016 Prime Ring Problem【深搜练习】

旧城等待， 2022-06-05 05:45 101阅读 0赞

## Prime Ring Problem ##

Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)  
Total Submission(s): 55230 Accepted Submission(s): 24442

#### 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

#### 题意概括： ####

对于数字1~n，对其进行排序，要求是当前数和其后一个数之和必须是素数，并且1永远都在第一位并和最后一个数之和也为素数。

#### 解题分析： ####

其实就是用深搜对1~n的数列进行全排列，输出其中特定的序列。

#### AC代码： ####

#include<stdio.h>
    #include<string.h>
    #include<math.h>
    
    #define N 23
    
    int book[N], a[N] = {
       1}, n;
    
    int IsPrime(int m)//因为数据较小，也可以用一个数组来记录是否是素数
    {
        if(m == 1) return 0;
        int i, k = (int)sqrt(m);
        for(i = 2; i <= k; i++)
            if(m%i == 0) return 0;
        return 1;
    }
    
    void dfs(int step)
    {
        int i;
        if(step >= n){
            if(IsPrime(1+a[step-1])){
                printf("1");
                for(int j = 1; j < n; j++)
                    printf(" %d", a[j]);
                printf("\n");
            }
            return ;
        }
        for(i = 2; i <= n; i++){
            if(!book[i] && IsPrime(a[step-1]+i)){
                book[i] = 1;
                a[step] = i;
                dfs(step+1);
                book[i] = 0;
            }
        }
    }
    
    int main()
    {
        int i, t = 0;
        while(~scanf("%d", &n)){
            memset(book, 0, sizeof(book));
            printf("Case %d:\n", ++t);
            dfs(1);
            printf("\n");
        }
        return 0;
    }