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.
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.
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，但是又与前面的有些不同，首先我用了两个全局的数组，一个存值，一个是标记数组。
在后面DFS函数中，递归的时候，我运用了回溯。吴涛说那里用回溯，我一直没有想到怎么用，但是后来的后来，看了一些东西，有了感觉，理解了很多。每次递归，等递归的最后结束语句执行以后，都会进行回溯，将前面的值回溯出来，递归进去是从前往后，但是递归结束，进行回溯的时候是从后往前的。
View Code
1 #include<stdio.h>
2 #include<stdlib.h>
3 #include<math.h>
4 int pao[30], flag[25], n;
5
6 int prime( int x )
7 {
8 for( int i = 2; i <= sqrt( x ); i++ )
9 if( x % i == 0 )
10 return 0;
11 return 1;
12 }
13
14 void DFS( int x )
15 {
16 int i, j;
17 if( ( x == n ) && prime( pao[x] + pao[1] ) && prime( pao[x] + pao[x-1] ) )
18 {
19 for( i = 1; i <= n; i++ )
20 printf( i==1 ? "%d" :" %d", pao[i] );
21 puts("");
22 }
23 else
24 {
25 for( i = 2; i <= n; i++)
26 if( prime( pao[x]+i ) && !flag[i] )
27 {
28 flag[i] = 1;//标记
29 pao[x+1] = i;
30 DFS( x+1 );
31 flag[i] = 0;//回溯
32 }
33 }
34 }
35 int main()
36 {
37 int k = 1;
38 while( scanf( "%d", &n ) == 1 )
39 {
40 printf( "Case %d:\n", k++ );
41 for( int i = 0; i < n; i++ )
42 {
43 pao[i] = 0;
44 flag[i] = 0;
45 }
46 pao[1] = 1;
47 DFS( 1 );
48 puts( "" );
49 }
50 return 0;
51 }