素数环(回溯)

转载请注明出处

题目描述

把1~N这N个整数摆成一个环，要求任意相邻两个数的和为素数。按字典序打印出以1开始的素数环

Input

一个整数N (<=10)

Output

每行一个素数环。每个数之间用一个空格隔开。
无解输出 No Solution

Sample Input

【样例输入1】
4

【样例输入2】
3

Sample Output

【样例输出1】
1 2 3 4
1 4 3 2

【样例输出2】
No Solution

Hint

为什么只要求以1开始的解。只有以1开始会漏掉其他可能的解吗？
优化：思考有哪些操作是不断要重复进行的，怎么优化。如何提高剪枝效率。

 1 /**
 2     回溯法
 3     网址：http://www.codeup.cn/problem.php?id=2908
 4     题目：2908: 素数环PrimeRing [3*]
 5     Accept
 6 */
 7 
 8 #include <stdio.h>
 9 
10 int flag[15];
11 int result[15];
12 int stack[15],top = 0;
13 int N;
14 int haveResult;
15 
16 int isprime(int n){
17     for(int i = 2; i <= n / 2; i++){
18         if(n % i == 0)
19             return 0;
20     }
21     return 1;
22 }
23 
24 void print(){
25     int i;
26     for(i = 0; i < N - 1; i++){
27         printf("%d ",result[i]);
28     }
29     printf("%d
",result[i]);
30 }
31 
32 void primeCircle(int cur){///cur将要填写的位置
33 
34     if(cur == N){
35         print();
36         haveResult = 1;
37         return ;
38     }
39 
40     for(int i = 2; i <= N; i++){///遍历每一个可填数字
41         if(flag[i - 1] == 0 && isprime(result[cur - 1] + i)){
42             ///最后一个数字与第一个数字1的和不是质数
43             if(cur == N - 1 && !isprime(i + 1)){
44                 break;
45             }
46             result[cur] = i;
47             flag[i - 1] = 1;
48             primeCircle(cur + 1);
49             ///返回上一层时，当前位置设置为未入选
50             if(flag[result[cur] - 1] == 1){
51                 flag[result[cur] - 1] = 0;
52             }
53         }
54     }
55 }
56 
57 int main(void){
58     result[0] = 1;
59     flag[0] = 1;
60     stack[top++] = 1;
61 
62     while(scanf("%d",&N) != EOF){
63         haveResult = 0;
64         primeCircle(1);
65         if(haveResult == 0)
66             printf("No Solution
");
67     }
68 
69     return 0;
70 }