A ring is composed of n (even number) circles as shown in diagram. Put natural numbers 
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 <= 16)
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.
You are to write a program that completes above process.
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
很經(jīng)典的深搜，啟發(fā)
1，預(yù)處理非常重要，
（1），先求出所有的prime數(shù)最大 16+16，bool isprime[32],
（2）由于已經(jīng)給出范圍，我們可以先求出1-19的每個數(shù)下一個可能的取值，例如15，下一個可以取2,4,------兩重for循環(huán)，可以避免搜索時重復(fù)判斷。
2，用一個數(shù)組記錄使輸出的有序，op[n]與dfs(int begin,int n)中n對應(yīng)
if( bp[t] )
{
op[o] = t ;
o ++ ;
bp[t] = false ;
dfs( t , n );//
o -- ;
bp[t] = true ;
}
posted on 2009-07-11 23:24
luis 閱讀(320)
評論(0) 編輯 收藏 引用 所屬分類:
搜索