注：这里我的代码是以第一位为最大数n为首元素不动的
思路：
首先我们分析问题要以较小规模的样例进行分析，例如n=3时
第一步：深入搜索
我们先不管后面怎么样，当前的首要目标是先确定第一个元素的值，可知有三个选择：1，2，3
当我们从1这个分支开始时，我们也不管后面的怎么样，当前的首要目标是先确定第二个元素的值，可知此时有两个选择：2，3
当我们继续从2这个分支开始时，这时我们只剩一个确定选择：3
上诉所有的步骤就是深入搜索，即选了其中一个选择后，在该选择的分支下，继续选择
第二步：回溯
例如当我们a[0]选择1时，a[1]不是2就是3，选择2时，发现暂时还符合素数环条件，可以继续深入探索，选择3时，发现此时已经不符合素数环条件，我们就没必要继续深入搜索了，同时要退出a[1]=3的分支
也就是说
我们每进行一次选择，如果此时符合素数环的条件，就继续选择，如果当前选择已经不符合素数环的条件，则说明我们已经没必要在该选择的分支下继续选择了，因此我们就应该退出该选择，换一条选择的分支继续搜索
这就是回溯
第三步：实现深入搜索和回溯
一方面我们深入搜索后，如果发现符合相关条件，那么我们就继续深入搜索，如果发现不符合相关条件，那么我们就回溯，其思想几乎与递归非常相似，因此我们应该用递归实现深入搜索和回溯
第四步：实现相关条件的函数
我们的深入搜索不能没条件限制一直深入搜索下去，就像递归不能永远递归下去，不然就陷入死循环了。因此我们要设置相关条件，如果不符合条件就回溯，由题意我们可知，条件一共有三：
1.前后元素的和的值必须为素数
2.前面选择的值，后面不能重复
3.首尾的和也要为素数
实现这些代码就很简单了
答案（第一位固定为n）：
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<math.h>
int n = 0;
int* p;
bool ans = false;
bool isPrime(int x) //判断是否是素数
{
if (x < 2) //1不是素数
{
return false;
}
for (int i = 2; i <= sqrt(x * 1.0); i++) //优化算法
{
if (x % i == 0) //如果有其他因子
{
return false; //不是素数
}
}
return true; //是素数
}
bool exist(int p[], int begin, int end, int x) //寻找数组a[begin..end]已经存在过x,则返回flase;反之，返回true
{
for (int i = begin; i <= end; i++)
{
if (p[i] == x)
{
return false;
}
}
return true;
}
void prt(int p[], int n) //打印素数环
{
int i;
for (i = 0; i <= n - 1; i++)
{
printf("%d ", p[i]);
}
printf("\n");
return;
}
void fill(int k, int p[]) //求素数环函数
{
if (k == n) //如果是素数环的最后一位
{
if (isPrime(p[0] + p[k - 1])) //如果首尾也是素数
{
ans = true; //符合素数环要求
prt(p, n);
}
return;
}
for (int i = n; i >= 1 && !ans; i--) //从
{
if (isPrime(p[k - 1] + i) && exist(p, 0, k - 1, i)) //如果既符合前后和是素数 && 前面没出现重复
{
p[k] = i; //将这个符合条件的数填入
fill(k + 1,p); //深入搜索
}
}
return; //回溯
}
int main()
{
printf("请输入n的值：\n");
scanf("%d", &n);
p = (int*)calloc(n, sizeof(int)); //申请空间并且都初始化为0
p[0] = n; //让数组第一位为最大值
fill(1, p); //从1开始进入深入搜索
if (ans != true)
{
printf("无解\n");
}
free(p); //最后归还申请空间
return 0;
}
