详解（在注释里）

#include <bits/stdc++.h>
using namespace std;

int n, a[20] = {0, 1};
bool flag[20];

bool is_Prime(int x) // 判断素数（质数） 
{
	for (int i = 2; i < x; i++)
		if (x % i == 0)	return false; // 如果可以被整除，就不是质数 ,返回 false 
	return true;
}

void dfs(int step)
{
	if (step > n)
	{
		if (!is_Prime(a[n] + a[1])) return;	 // 剪枝，判断最后一个和第一个加起来是否为素数 
		for (int i = 1; i <= n; i++) cout << a[i] << " "; // 输出答案 
		cout << endl;
		return;
	}
	for (int i = 2; i <= n; i++) //第 1个数必须是 1，所以不用考虑 1， 那么就从 2开始，一直到n 
	{
		if (!flag[i] && is_Prime(i + a[step - 1])) // 没被标记且加起来为素数
		{	
			a[step] = i;
			flag[i] = 1;
			dfs(step + 1); 
			flag[i] = 0;
		}
	}
}

int main()
{
	cin >> n; // 读入n 
	dfs(2);
	return 0;
}

题意

$n$ 个数，范围 $1 \sim n$。$a_i + a_{i - 1}$ 和 $a_i + a_{i + 1}$ 需为素数^[1]，第 1 个数加第 n 个数也要为素数

思路

看起来是个环，实际上很简单。

把环剪开来看，要输出前再检查第 1 个加第 n 个是否为素数

代码

#include <bits/stdc++.h>
using namespace std;
int n;
int a[20] = {0,1};	// 必须 1 开头
bool f[20];
bool su(int x){	// 素数判断
	for (int i = 2;i < x;i++){
		if (x % i == 0)	return 0;
	}
	return 1;
}
void dfs(int u){
	if (u > n){
		if (!su(a[n] + a[1]))	return;	// 判断最后一个和第一个加起来是否为素数
		for (int i = 1;i <= n;i++){
			printf("%d ",a[i]);
		}
		cout << "\n";
		return;
	}
	for (int i = 2;i <= n;i++){	// 第 1 个数必须是 1，所以不用考虑 1
		if (!f[i] && su(i + a[u - 1])){	// 没被标记且加起来为素数
			a[u] = i;
			f[i] = 1;
			dfs(u + 1);
			f[i] = 0;
		}
	}
}
int main(int argc, char **argv){
	cin >> n;
	dfs(2);
	return 0;
}

有彩蛋

题意

从1到n取数,使前一个数与这个数和为质数

如果有,输出这段数

思路

递归+回溯(当然的)

• if(填完足够的数)

  • if(最后的与第一个是否和不为质数)

    • return;

  • 逐个输出

  • return;

• for循环(2~n)判断前一个数与这个数和是否为质数

  • 如果是
    • 加入数组
    • 标记
    • 递归
    • 回溯(恢复 犯罪 现场)

代码

#include<iostream>
using namespace std;
int zs[114514]={2,3,5,7,11,13,17,19,23,29,31,37};//质数(有彩蛋)
int s[114];//记录数组 
bool a[514];//标记数组 
int n;
bool check(int x)
{
	for(int i=0;i<12;i++)//质数检测
	{
		if(zs[i]==x)
		{
			return 1;
		}
	}
	return 0;
}
void dfs(int x)
{
	if(x==n)
	{
		if(!check(s[n-1]+1))return;//检查最后的与第一个是否和为质数(环)
		for(int i=0;i<n;i++)
		{
			cout<<s[i]<<" ";//输出
		}
		cout<<endl;
		return;//注意
	}
	for(int i=2;i<=n;i++)//可以从2开始
	{	
		if((!a[i]) && check(s[x-1]+i))//没被标记过与是否和为质数
		{
			s[x]=i;//进入
			a[i]=1;//标记
			dfs(x+1);//递归
			a[i]=0;//回溯
		}
	}
}
int main()
{
	cin>>n;//输入
	s[0]=1;//初始化
	a[1]=1;//标记
	dfs(1);//递归
	return 0;//完结散花
}

彩蛋

小学数学不过关

0WA的原因很简单

质数有两个写错了(13没写,29写成27)

害我调试了两年半(1个星期)

题意

输出一个环，使相邻数字之和为素数。

思路

非常通畅……

我们从1开始，对于没用过的数一个个是，如果和为素数，就搜索，否则回溯。

代码

这次题解 好快啊 好简洁啊！

#include<iostream>
using namespace std;
int n;
int a[20]={0,1};//从1开始
bool vis[20]={0,1};//从1开始
int main(){
	cin>>n;
	void dfs(int);
	dfs(2);//从2开始搜索
	return 0;
}
void dfs(int k){
	if(k>n){//如果遍历完输出
		void print();
		print();
		return;
	}
	for(int i=1;i<=n;i++)
		if(!vis[i]){
			bool check(int);//判断素数函数
			if(check(a[k-1]+i)){
				a[k]=i;
				vis[i]=1;//标记
				dfs(k+1);
				vis[i]=0;//回溯
			}
		}
	return;
}
void print(){
	bool check(int);
	if(check(a[1]+a[n])){//检查首尾相接是否为素数
		for(int i=1;i<=n;i++)
			cout<<a[i]<<" ";
		cout<<"\n";
	}
	return;
}
bool check(int n){//不必多言
	for(int i=2;i<n;i++)
		if(n%i==0)
			return 0;
	return 1;
}

注意

最后要判断首尾相接处