C++刷题 搜索与回溯法解素数环（搜索与回溯算法）

【问题描述】将1～n这n个数字首尾相连，形成一个圆环，要求圆环上任意两个相邻的数字之和都是一个素数，请编程输出符合条件的素数环。

输入

输入数据仅一行，包含一个正整数n（n<=20）。

输出

输出数据最多包括20行，每行由n个整数组成，表示前十个符合条件的素数环（不足20个时全部输出）。所有素数环第一个元素必须是1，且按照从小到大的顺序排列。

样例输入 样例输出

【算法分析】

很明显，这是一道回溯的题目。从1开始，每个空位有n种可能，只要填进去的数满足以下条件：与前面的数不相同并且与左边相邻的数的和是一个素数。第n个数还要判断和第1个数(本题要求第1个数为1)的和是否素数

【算法流程】

1、数据初始化； 2、递归填数：判断第i个数填入是否合法；

A、符合要求：填数；判断是否到达目标（n个已填完）：是，打印结果；不是，递归填下一个；

B、不符合要求：选择下一种可能；

【参考程序】

#include<bits/stdc++.h>
using namespace std;
int search(int k) ;
bool b[21]={0};
int a[21]={0};
int n,num=0;
int main()
{
	int i,j;
	cout<<"请输入:";
	cin>>n;
	a[1]=1;//首位固定为1
	if(n%2==0) //只有偶数个数才可能构成素数环
		search(2);
	return 0;
}

bool isprime(int x,int y) //判素数
{
	if(x+y<2)
		return 0;
	for(int i=2;i<=sqrt(x+y);i++)
	{	
		if((x+y)%i==0)
			return 0;
	}	
	return 1;
}

int search(int k) // 回溯
{
	if(num>=20||k>n)//如果超过20种方案退出
		return 0;
	for(int i=2;i<=n;i++)//从2到n可以选择
	{
		if(!b[i]&&isprime(a[k-1],i))// 判断相邻数为是否素数、该数是否可用并从小到大排序
		{
			a[k]=i;
			b[i]=1;
			if(k==n)
			{
				if(isprime(a[n],a[1]))
				{
					num++;
					for(int j=1;j<=n;j++)
						cout<<a[j]<<' ';
					cout<<endl;
				}
			}		
			else
				search(k+1);
			b[i]=0;
		}
	}
}