1457_other.cpp

把1到n的数放在一个环里,使相邻的2个数和是质数.用递归做

#include <iostream> 
using namespace std; 

bool primes[40]; 
int a[20][2]; 
int top; 
bool use[20]; 


void generatePrimeRing(int n) 
{ 

top=0; 
a[top][0]=1; 
a[top][1]=2; 
int i; 
for(i=0;i<n;i++) 
use[i]=false; 
use[0]=true; 
while(top!=-1) 
{ 

if(top==n-1) 
{ 
if(primes[a[top][0]]) 
{ 
for(i=0;i<n-1;i++) 
cout<<a[i][0]<<" "; 
cout<<a[n-1][0]; 
cout<<endl; 

} 
use[a[top][0]-1]=false; 
top--; 
use[a[top][0]-1]=false; 
top--; 
a[top][1]=a[top+1][0]+1; 
} 
else 
{ 
for(i=a[top][1];i<=n;i+=2) 
if(!use[i-1]&&primes[a[top][0]+i-1]) 
break; 
if(i<=n) 
{ 
a[top][1]=i+2; 
top++; 
a[top][0]=i; 
a[top][1]=i%2+1; 
use[i-1]=true; 
} 
else 
{ 
use[a[top][0]-1]=false; 
top--; 
} 
} 
} 

} 

int main() 
{ 
int testNumber=1,n; 
int i; 
for(i=0;i<40;i++) 
primes[i]=false; 
primes[1]=true; 
primes[2]=true; 
primes[4]=true; 
primes[6]=true; 
primes[10]=true; 
primes[12]=true; 
primes[16]=true; 
primes[18]=true; 
primes[22]=true; 
primes[28]=true; 
primes[30]=true; 
primes[36]=true; 
primes[38]=true; 

bool first=true; 
while(cin>>n) 
{ 


cout<<"Case "<<testNumber++<<":"<<endl; 
if(n%2==0) 
{ 
generatePrimeRing(n); 

} 
cout<<endl; 



} 
return 0; 
}