【题解】素数环

index

前言：

在学校信息队训练的时候布置了这一道题目，但是只求一次。然后上洛谷发现UVA题库求多次，因为方法一样只需嵌套，所以就做了一下（没有账号提交不了=m=）

信息队原题

原题图片

1.题目分析

题目要求将整数 $1$ 到 $n$ 组成一个环，使得相邻的两个整数之和均为素数。

我们需要找到所有满足条件的素数环，并按照要求输出。

由于 $n$ 的值不超过 $16$ ，我们可以使用回溯法来尝试所有可能的组合。

2.做题思路

判断当前取出的数字是否和前一个组成素数，这一步可以用一个 check函数来解决（num的值为两个数字的和）

1
`bool check(int num)
2
{
3
    if (num < 2)
4
    {
5
        return false;
6
    }
7
    for (int i = 2; i * i <= num; i++)
8
    {
9
        if (num % i == 0)
10
        {
11
            return false;
12
        }
13
    }
14
    return true;
15
}
16
`

在创建一个 back 函数用于回溯：

1
`void back(int cur)  // cur 表示当前位置
2
{
3
    if (cur == n)  // 检查最后一个数字和第一个数字之和是否为素数
4
    {
5
        if (check(arr[0] + arr[n - 1]))
6
        {
7
            for (int i = 0; i < n; i++)
8
            {
9
                cout << arr[i] << " ";
10
            }
11
            cout << endl;
12
        }
13
        return;
14
    }
15
    for (int i = 2; i <= n; i++)
16
    {
17
        if (!vis[i] && check(arr[cur - 1] + i))
18
        {
19
            vis[i] = true;
20
            arr[cur] = i;
21
            back(cur + 1);
22
            vis[i] = false;
23
        }
24
    }
25
}
26
`

在back函数中，首先判断是否已经放置了 $n$ 个数字。如果是，则检查最后一个数字和第一个数字之和是否为素数。如果是素数，则输出这个环。

然后，从数字 $2$ 到 $n$ 依次尝试将每个数字放在环的下一个位置。如果该数字没有被使用过，并且与前一个数字之和为素数，就将其放在环的下一个位置，并标记为已使用，然后继续递归放置下一个数字。

如果放置过程中出现相邻两个数字之和不是素数的情况，就回溯到上一个数字，重新选择下一个数字。

最后是 main 函数，在main函数中，读取输入的 $n$ ，初始化标记数组和环的第一个数字，然后调用 back 函数从数字 $1$ 开始回溯。

3.复杂度计算

时间复杂度：由于需要尝试所有可能的组合，时间复杂度为 $O(n!)$ ，其中 n 是输入的数字个数

空间复杂度：主要是使用了标记数组和环数组，空间复杂度为 $O(n)$

4.完整代码

1
`#include <bits/stdc++.h>
2
using namespace std;
3

4
const int MAXN = 16;
5
int n;
6
int arr[MAXN];
7
bool vis[MAXN];
8

9
// 判断一个数是否为素数
10
bool check(int num)
11
{
12
    if (num < 2)
13
    {
14
        return false;
15
    }
16
    for (int i = 2; i * i <= num; i++)
17
    {
18
        if (num % i == 0)
19
        {
20
            return false;
21
        }
22
    }
23
    return true;
24
}
25

26
// 回溯
27
// cur表示当前位置
28
void back(int cur)
29
{
30
    if (cur == n)  // 检查最后一个数字和第一个数字之和是否为素数
31
    {
32
        if (check(arr[0] + arr[n - 1]))
33
        {
34
            for (int i = 0; i < n; i++)
35
            {
36
                cout << arr[i] << " ";
37
            }
38
            cout << endl;
39
        }
40
        return;
41
    }
42
    for (int i = 2; i <= n; i++)
43
    {
44
        if (!vis[i] && check(arr[cur - 1] + i))
45
        {
46
            vis[i] = true;
47
            arr[cur] = i;
48
            back(cur + 1);
49
            vis[i] = false;
50
        }
51
    }
52
}
53

54
int main()
55
{
56
    cin >> n;
57
    memset(vis, false, sizeof(vis));
58
    vis[1] = true;
59
    arr[0] = 1;
60
    back(1);
61
    return 0;
62
}
63
`

洛谷UVA题库版

前面不是说了吗，UVA也有一个版本，是给出多个值，这里给出题目：

洛谷UVA题目

样例组

INPUT #1

OUTPUT #1

1
`Case 1:
2
1 4 3 2 5 6
3
1 6 5 2 3 4
4

5
Case 2:
6
1 2 3 8 5 6 7 4
7
1 2 5 8 3 4 7 6
8
1 4 7 6 5 8 3 2
9
1 6 7 4 3 8 5 2
10
`

其实就是多次输入，用 while 循环解决，终止条件为 n == EOF，所以可以这样写。

1
`while(n != EOF)
2
    {
3
        cin >> n;
4
        memset(vis, false, sizeof(vis));
5
        vis[1] = true;
6
        arr[0] = 1;
7
        back(1);
8
    }
9
`

现在是把刚才信息队版本的输入和操作套在了循环里，这就完了，是不是很简单？

其实没完，题目中说要在第 i 行添加上 Case i ，所以再搞一个变量就完事了！

1
`int idx = 1;  // 此处 idx 变量即 i 变量
2
while(n != EOF)
3
{
4
    cin >> n;
5
    cout << "Case " << idx++ << ":" << endl;  // 输出 Case i 因为 "++" 在后是先赋值再运算，所以可以这么写，就相当于先输出 idx 当前值再加
6
    memset(vis, false, sizeof(vis));
7
    vis[1] = true;
8
    arr[0] = 1;
9
    back(1);
10
}
11
`

最终代码

1
`#include <bits/stdc++.h>
2
using namespace std;
3

4
const int MAXN = 16;
5
int n;
6
int arr[MAXN];
7
bool vis[MAXN];
8

9
// 判断一个数是否为素数
10
bool check(int num)
11
{
12
    if (num < 2)
13
    {
14
        return false;
15
    }
16
    for (int i = 2; i * i <= num; i++)
17
    {
18
        if (num % i == 0)
19
        {
20
            return false;
21
        }
22
    }
23
    return true;
24
}
25

26
// 回溯
27
// cur表示当前位置
28
void back(int cur)
29
{
30
    if (cur == n)  // 检查最后一个数字和第一个数字之和是否为素数
31
    {
32
        if (check(arr[0] + arr[n - 1]))
33
        {
34
            for (int i = 0; i < n; i++)
35
            {
36
                cout << arr[i] << " ";
37
            }
38
            cout << endl;
39
        }
40
        return;
41
    }
42
    for (int i = 2; i <= n; i++)
43
    {
44
        if (!vis[i] && check(arr[cur - 1] + i))
45
        {
46
            vis[i] = true;
47
            arr[cur] = i;
48
            back(cur + 1);
49
            vis[i] = false;
50
        }
51
    }
52
}
53

54
int main()
55
{
56
    int idx = 1;
57
    while(n != EOF)
58
    {
59
        cin >> n;
60
        cout << "Case " << idx++ << ":" << endl;
61
        memset(vis, false, sizeof(vis));
62
        vis[1] = true;
63
        arr[0] = 1;
64
        back(1);
65
    }
66
    return 0;
67
}
68
`

写在最后

到这里本片题解就结束了，UVA版本没提交，前面说了注册不起账号，但是代码应该没问题，有问题评论告知，谢谢支持🙏