任务描述 本关任务:把从 1 到 n 这 n 个数摆成一个环,要求相邻的两个数的和是一个素数。 编程要求 请在右侧编辑器Begin-End处补充代码,完成本关任务,输出格式请参考测试集。 测试说明 平台会对你编写的代码进行测试,比对你输出的数值与实际正确数值,只有所有数据全部计算正确才能通过测试: 测试输入:20 预期输出:围成的圈是:1 2 3 4 7 6 5 8 9 10 13 16 15 14 17 20 11 12 19 18 开始你的任务吧,祝你成
时间: 2023-12-10 09:39:18 浏览: 45
```python
n = int(input()) # 输入 n
nums = [i for i in range(1, n + 1)] # 生成 1~n 的数列
res = [] # 用于存放结果
# 判断两个数的和是否是素数
def is_prime(num):
if num <= 1:
return False
for i in range(2, int(num ** 0.5) + 1):
if num % i == 0:
return False
return True
# 求解当前排列是否符合条件
def dfs(path):
if len(path) == n: # 如果已经排好了 n 个数
if is_prime(path[0] + path[-1]): # 判断首尾两个数的和是否是素数
res.append(path.copy()) # 如果是素数,将当前路径加入结果列表
return
for num in nums:
if num not in path and (len(path) == 0 or is_prime(path[-1] + num)): # 如果当前数未被使用且与上一个数的和是素数
path.append(num) # 将当前数加入路径中
dfs(path) # 继续搜索下一个数
path.pop() # 回溯,将当前数从路径中删除
dfs([]) # 从空路径开始搜索
# 输出结果
print("围成的圈是:", end=" ")
for r in res[0]:
print(r, end=" ")
print()
```
思路说明:
首先生成 1~n 的数列,然后采用回溯法进行搜索。
对于每个排列,判断首尾两个数的和是否是素数,如果是素数,则将该排列加入结果列表中。
最后输出结果列表中的第一个排列即可。
相关推荐
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)