题目地址：http://acm.hdu.edu.cn/showproblem.php?pid=1016
递归法：（简单但会超时。。。）
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
void swap(int& a,int& b)
{
int tmp;
tmp = a;
a = b;
b = tmp;
}
bool isPrime(int num)
{
for (int i=2;i<=sqrt(static_cast<double>(num));++i)
{
if (num%i==0)
{
return false;
}
}
return true;
}
bool isOK(const vector<int>& v)
{//判断是否是素数环
bool result = true;
for (int i=0;i<v.size()-1;++i)
{
if (isPrime((v[i]+v[i+1]))==false)
{
result = false;
break;
}
}
if (isPrime(v[0]+v[v.size()-1])==false)
{
result = false;
}
return result;
}
void Rerange(vector<int>& v,int m,int n)
{
if(m==n)
{
if (isOK(v))
{
for(int j=0;j<=m;++j)
{
if (j==m)
{
cout<<v[j]<<endl;
}
else
{
cout<<v[j]<<" ";
}
}
}
}
else
{
for(int i=m;i<=n;i+=2)
{
swap(v[m],v[i]);
Rerange(v,m+1,n);
swap(v[m],v[i]);
}
}
}
int main(int argc,char* argv[])
{
int n,i,curCase=1,tmp;
while (cin>>n)
{
cout<<"Case "<<curCase<<":"<<endl;
vector<int> numVector;
if (n%2==0)
{
for (i=0;i<n;++i)
{
numVector.push_back(i+1);
}
Rerange(numVector,1,numVector.size()-1);
}
cout<<endl;
curCase++;
}
return 0;
}
回溯法：
#include<iostream>
#include<cmath>
using namespace std;
int a[20],curCase=0,n;
bool isNotIn(int num,int end)
{//是否还未在环中出现过,num是待加入环尾的元素，end是当前环尾
int i;
for(i=1;i<=end-1;++i)
{
if(a[i]==num)return false;
}
return true;
}
bool isPrime(int num)
{//是否是素数
for (int i=2;i<=sqrt(static_cast<double>(num));++i)
{
if (num%i==0)
{
return false;
}
}
return true;
}
bool isPrimeCircl(int num,int end)
{//是否是素数环,num是待加入环尾的元素,end是当前环尾
if(end<n)
return(isPrime(num+a[end-1]));
else //此时要考虑头尾和是否是素数
return(isPrime(num+a[end-1])&&isPrime(num+a[1]));
}
void output()
{
int k;
cout<<a[1];
for(k=2;k<=n;k++)
cout<<' '<<a[k];
cout<<endl;
}
void back(int i)
{
int k;
for(k=1;k<=n;k++)
{
if(isNotIn(k,i)==true && isPrimeCircl(k,i)==true)
{
a[i]=k;
if(i==n)
output();
else
{
back(i+1);
a[i]=0;
}
}
}
}
int main()
{
int k;
for(k=1;k<=20;k++)
{
a[k]=0;
}
a[1]=1;
while(cin>>n)
{
curCase++;
cout<<"Case "<<curCase<<':'<<endl;
back(2);
cout<<endl;
}
return 0;
}
本文转自Phinecos(洞庭散人)博客园博客，原文链接：http://www.cnblogs.com/phinecos/archive/2008/01/04/1026200.html，如需转载请自行联系原作者
