5.5 真-白给题

算法设计与分析 5.5 真-白给题

题目描述

  给定1-n的一个排列，要求你将它们重排，使得任意两个相邻的数的和为质数。

输入格式

一个正整数 n ( 1 <= n <= 20 )

输出格式

输出一行一个1-n的排列，满足相邻的两个数相加为质数。

如果有多组解，输出字典序最小的那一个。

如果无解，输出-1。

样例输入1

2
1

样例输出1

1 2
1

样例输入2

3
1

样例输出2

1 2 3
1

参考代码1

回溯法

#include 
#include 
#define N 21
/*
* 独立集问题
* 回溯法
* 剑走偏锋，反正n才20，可以算出答案存到数组。
* 1
* 1 2
* 1 2 3
* 1 2 3 4
* 1 4 3 2 5
* 1 4 3 2 5 6
* 1 2 3 4 7 6 5
* 1 2 3 4 7 6 5 8
* 1 2 3 4 7 6 5 8 9
* 1 2 3 4 7 6 5 8 9 10
* 1 2 3 4 7 10 9 8 5 6 11
* 1 2 3 4 7 6 5 12 11 8 9 10
* 1 2 3 4 7 6 5 12 11 8 9 10 13
* 1 2 3 4 7 6 13 10 9 8 11 12 5 14
* 1 2 3 4 7 6 5 12 11 8 15 14 9 10 13
* 1 2 3 4 7 6 5 12 11 8 9 10 13 16 15 14
* 1 2 3 4 7 6 5 8 9 10 13 16 15 14 17 12 11
* 1 2 3 4 7 6 5 8 9 10 13 16 15 14 17 12 11 18
* 1 2 3 4 7 6 5 8 9 10 13 16 15 14 17 12 11 18 19
* 1 2 3 4 7 6 5 8 9 10 13 16 15 14 17 12 19 18 11 20
*/
bool a[N][N];
bool b[N];
int stack[N];
int n;
bool flag = false;

bool isPrime(int num) {
    for (int i = 2; i * i <= num; i++) {
        if (num % i == 0) {
            return false;
        }
    }

    return true;
}

void setAB() {
    for (int i = 1; i < N; i++) {
        for (int j = i; j < N; j++) {
            a[i][j] = a[j][i] = isPrime(i + j);
        }
        b[i] = true;
    }
}

void find(int i) {
    for (int j = 1; j <= n; j++) {
        if (a[stack[i - 1]][j] && b[j]) {
            stack[i] = j;
            b[j] = false;
            if (i == n) {
                flag = true;
                return;
            }
            find(i + 1);
            if (flag) {
                return;
            }
            else {      // 回退
                b[j] = true;
            }
        }
    }
}


int main()
{
    std::cin >> n;
    if (n <= 1) {
        std::cout << (n==1)?1:-1;

        return 0;
    }

    setAB();
    stack[1] = 1;
    b[1] = false;
    find(2);

    if (flag) {
        for (int i = 1; i <= n; i++) {
            std::cout << stack[i] << ' ';
        }
    }
    else {
        std::cout << -1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97

参考代码2

读表法

#include 
/*
* 独立集问题
* 回溯法
* 剑走偏锋，反正n才20，可以算出答案存到数组。
* 1
* 1 2
* 1 2 3
* 1 2 3 4
* 1 4 3 2 5
* 1 4 3 2 5 6
* 1 2 3 4 7 6 5
* 1 2 3 4 7 6 5 8
* 1 2 3 4 7 6 5 8 9
* 1 2 3 4 7 6 5 8 9 10
* 1 2 3 4 7 10 9 8 5 6 11
* 1 2 3 4 7 6 5 12 11 8 9 10
* 1 2 3 4 7 6 5 12 11 8 9 10 13
* 1 2 3 4 7 6 13 10 9 8 11 12 5 14
* 1 2 3 4 7 6 5 12 11 8 15 14 9 10 13
* 1 2 3 4 7 6 5 12 11 8 9 10 13 16 15 14
* 1 2 3 4 7 6 5 8 9 10 13 16 15 14 17 12 11
* 1 2 3 4 7 6 5 8 9 10 13 16 15 14 17 12 11 18
* 1 2 3 4 7 6 5 8 9 10 13 16 15 14 17 12 11 18 19
* 1 2 3 4 7 6 5 8 9 10 13 16 15 14 17 12 19 18 11 20
*/
int main()
{
    int n;
    scanf("%d", &n);

    if (n < 1) {
        printf("-1");
        return 0;
    }
    char s[21][51] = { "0",
    "1",
    "1 2",
    "1 2 3",
    "1 2 3 4",
    "1 4 3 2 5",
    "1 4 3 2 5 6",
    "1 2 3 4 7 6 5",
    "1 2 3 4 7 6 5 8",
    "1 2 3 4 7 6 5 8 9",
    "1 2 3 4 7 6 5 8 9 10",
    "1 2 3 4 7 10 9 8 5 6 11",
    "1 2 3 4 7 6 5 12 11 8 9 10",
    "1 2 3 4 7 6 5 12 11 8 9 10 13",
    "1 2 3 4 7 6 13 10 9 8 11 12 5 14",
    "1 2 3 4 7 6 5 12 11 8 15 14 9 10 13",
    "1 2 3 4 7 6 5 12 11 8 9 10 13 16 15 14",
    "1 2 3 4 7 6 5 8 9 10 13 16 15 14 17 12 11",
    "1 2 3 4 7 6 5 8 9 10 13 16 15 14 17 12 11 18",
    "1 2 3 4 7 6 5 8 9 10 13 16 15 14 17 12 11 18 19",
    "1 2 3 4 7 6 5 8 9 10 13 16 15 14 17 12 19 18 11 20"
    };

    printf("%s", s[n]);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60