信息学奥赛一本通 2110：【例5.1】素数环

【题目链接】

ybt 2110：【例5.1】素数环

【题目考点】

1. 深搜回溯

2. 质数

【解题思路】

1~n的数字构成一个环，要求相邻数字加和必须是质数。
该题最终输出的是一个序列，只不过逻辑上序列最后一个数字的下一个数字就是序列的第一个数字。数值1一定在这个序列中，因此我们让序列第1个数字就是数值1。
而后使用深搜算法依次确定第2个数字，第3个数字。。。
在确定第k个数字时，首先该数字只能是1~n中的数字，其次该数字必须没有使用过，而且该数字和前一个数字（第k-1个数字）的加和必须是质数。将可能的满足以上条件的数字作为序列的第k个数字。
当k为n+1，也就是满足k>n时，已经确定了序列中的n个数字，此时如果第1个数字和第n个数字的加和也是质数，那么就确定了一个满足条件的质数环，将序列中的数字输出。
可以使用标志位isOver记录是否已经找到解。如果已经找到解，那么递归调用可以直接返回，不用继续进行搜索。

【题解代码】

解法1：深搜回溯

#include <bits/stdc++.h>
using namespace std;
#define N 35
int n, a[N];
bool vis[N], isOver;
bool isPrime(int x)//判断x是否是质数
{
	if(x < 2)
		return false;
	for(int i = 2; i*i <= x; ++i) if(x%i == 0)
		return false;
	return true;
}
void dfs(int k)
{
	if(isOver)
		return;
	if(k > n)
	{
		if(isPrime(a[n]+a[1]))
		{
			isOver = true;
			for(int i = 1; i <= n; ++i)
				cout << a[i] << ' ';
			cout << endl;
		}
		return;
	}
	for(int i = 1; i <= n; ++i)  if(!vis[i] && isPrime(a[k-1]+i))
	{
		vis[i] = true;
		a[k] = i;//选择数值i作为第k个数字
		dfs(k+1);
		vis[i] = false;
	}
}
int main()
{
	cin >> n;
	a[1] = 1;
	vis[1] = true;
	dfs(2);
	return 0;
}