主要内容 #

1. 问题描述
2. 计算方法
3. 参考代码

1. 问题描述 #

把整数{1,2,3，…，20}填到一个环中，要求每个整数只填写一次，并且相邻的两个整数之和是一个素数。例如，下图所示就是{1,2,3,4}对应的一个素数环。

2. 计算方法 #

算法分析
非常明显，只是一道回溯题目。从1开始，每个空位有20种可能，只要填进去的数合法；与之前的数不同；与左边相邻的数是一个素数；第20个数还要判断和第一个数的和是否是素数。
在填写第k个位置时，如果满足上述约束条件，则继续填写第k+1个位置；如果1~20都无法填写到第k个位置，则取消第k个位置的填写，回溯到第k-1个位置。
以四个数字的素数环为例，使用回溯法的解答树解答如下图所示：

算法流程

输入：要填写到环中的整数个数n输出：素数环的元素a【n】
1.将存储素数环的数组a】中所以元素初始化为0
2.将a【0】初始化为1，k初始化为1
3.while(k>=1)
    3.1a[k]=a[k]+1
    3.2 while(a[k]<=n)
        3.2.1如果a[k]满足约束条件，结束循环
        3.2.2如果a[k]不满足约束条件，a[k]=a[k]+1
    3.3如果a[k]=n，且k=n-1，输出素数环，结束程序
    3.4如果a[k]<=n，且k<n-1，k=k+1
    3.5否则，a[k]=0，k=k-1，即回溯。

3. 参考代码 #

#include < iostream >
#include < math.h >
using namespace std;

bool isPrime(int x)	//判断整数x是否是素数 
{
	int n = (int)sqrt(x);
	for(int i=2; i < =n; i++)
		if(x%i == 0) return false;
	return true;
}

bool isLegal(int k, int n, int a[])	//判断位置k填写是否满足约束条件 
{
	for(int i=0; i < k; i++)		//判断即将填写的值是否与填写过的重复 
		if(a[i] == a[k]) return false;
	if(!isPrime(a[k]+a[k-1])) return false;	//判断相邻数之和是否为素数
	if(k==n-1 && !isPrime(a[k]+a[0])) return false;	//判断第一个和最后一个之和是否为素数 
	return true;
}

void primeCircle(int n)
{
	int a[n];	//用数组a[]来存储素数环 
	for(int i=0; i < n; i++)	//将数组所有元素都初始化为0 
		a[i] = 0;
	
	a[0] = 1;
	int k = 1;
	while(k > =1)
	{
		a[k] = a[k]+1;
		while(a[k] < =n)
		{
			if(isLegal(k,n,a)) break;	//位置k可以填写整数a[k]
			else a[k] = a[k]+1;	//试探下一个数 
		}
		
		if(a[k] < =n && k==n-1)	//求解完毕，输出素数环 
		{
			for(int i=0; i < n; i++)
				cout << a[i] << " ";
			cout << endl;
			return;
		}
		
		if(a[k]<=n && k<n-1) k++;	//填写下一个
		else a[k--] = 0;	//回溯 
	}
}

int main()
{
	primeCircle(4);
	return 0;
}