20个数排成一个圈???

来源：百度知道 编辑：UC知道 时间：2024/06/22 14:32:20
把1-20这20个数排成一个圈,使得相邻的两个数之和是素数.
不知道用回溯法解行不行?
若行,请编写出相应的C++程序.

请大家来这里发表高见!!!

#include<iostream.h>
using namespace std;
bool IsPrime(int k) //判断是不是素数，针对本题目
{
int a[] = {3,5,7,11,13,17,19,23,29,31,37};
for(int i=0;i<12;i++)
{
if(a[i]==k)
return true;
}
return false;
}
bool InSolve(int k,int *a,int m) //判断数k是不是已经插入到环中了
{
for(int i=0;i<m;i++)
{
if(k==*(a+i))
return true;
}
return false;
}
void out(int *a,int m) //测试用输出函数
{
for(int i=0;i<m;i++)
{
cout<<a[i]<<" ";
}
cout<<endl;
}
bool Solve(int n,int *a) //递归求解
{
if(n==20) //开始
{
*a = 20; //把20插入到环中
return Solve(n-1,a); //递归
}
for(int i=19;i>0;i--) //把剩下的数插入到环中
{
if(!InSolve(i,a,20-n)) //如果i没在环中
{
if(IsPrime(i+*(a+20-n-1))) //符合题目要求
{
*(a+20-n) = i;
out(a,20-n+1);
if(Solve(n-1,a)) //递归
return true;