ACM-DFS之Prime Ring Problem——hdu1016

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



   這是一道dfs（深搜）題目（廢話。。），
題意就是求一個素數環，使得相鄰兩個數之和均為素數，
當然第一個與最後一個相加也要是素數，因為它是環嘛。
言歸正傳，
這道題解法就是建立兩個數組，一個存數，一個用來判斷某個數是否使用過，
還需要一個輔助數組，不能每一次都判斷兩個數相加的和是否為素數，每次都用函數算一遍，肯定逾時的啦，
是以建立一個數組把前40的數字是否為素數狀态存儲起來，需要判斷的時候，隻需要讀相應下标所對應的數就可以了，
每次搜尋都周遊一遍，當然剪枝也減一下，
最後注意一下格式問題，最後一個數後面木有空格= =。


          
#include <iostream>

using namespace std;

// 該數組用來存儲，數組下标數字是否為素數狀态，1則是素數
int prim[]={0,0,1,1,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,0,0,0,0,1,0,1,0,0,0,0,0,1,0,0,0};
int arr[21],brr[21],n;


void dfs(int js)
{
    int i;
    
	// 剪枝，計數器不能大于輸入的n
    if(js>n)    return;

	// 若相等，則輸出，注意輸出格式
    if(js==n)
    {
        for(i=0;i<n-1;++i)
            cout<<brr[i]<<" ";
        cout<<brr[n-1]<<endl;

        return;
    }

    for(i=2;i<=n;++i)
    {
        if(arr[i]==1)    continue;

        if(js+1==n)
        {
            if(prim[brr[js-1]+i]==1 && prim[1+i]==1)
            {
                brr[js]=i;
                arr[i]=1;
                dfs(js+1);
                arr[i]=0;
            }
        }
        else 
        {
            if(prim[brr[js-1]+i]==1)
            {
                brr[js]=i;
                arr[i]=1;
                dfs(js+1);
                arr[i]=0;
            }
        }
    }
    return;
}

int main()
{
    int xh=1;
    while(cin>>n)
    {
		// 初始化兩個數組
        memset(brr,0,sizeof(brr));
        memset(arr,0,sizeof(arr));

        arr[0]=brr[0]=1;
        cout<<"Case "<<xh<<":"<<endl;
        dfs(1);
        cout<<endl;
        ++xh;
    }
    return 0;
}