描述

将1-n这n个数摆成一个环，要求相邻的两个数的和是一个素数，编程输出所有可能的解。

输入

包括多组数据，每组1个数n。n<20

输出

所有可能的解。

输出格式见样例。

样例输入

6 8

样例输出

Case 1: 1 4 3 2 5 6

            1 6 5 2 3 4
Case 2: 1 2 3 8 5 6 7 4

            1 2 5 8 3 4 7 6

            1 4 7 6 5 8 3 2

            1 6 7 4 3 8 5 2

#include <iostream>using namespace std;int a[20],n;int used[20];int is_prime(int x){    int i;    for(i=2;i<x;i++)    if(x%i==0) return 0;    return 1;}void dfs(int cur){    int i;    if(cur==n&&is_prime(a[1]+a[n]))    {        for(i=1;i<n;i++) cout<<a[i]<<" ";        cout<<a[n]<<endl;        return ;    }    for(i=2;i<=n;i++)    {        if(is_prime(a[cur]+i)&&used[i]==0)        {            a[cur+1]=i;used[i]=1;dfs(cur+1);used[i]=0;        }    }}int main(int argc, char *argv[]){    int c;    c=1;    while(cin>>n)    {        memset(used,0,sizeof(used));        used[1]=1;a[1]=1;                cout<<"Case "<<c++<<":"<<endl;        if(n%2==0)        dfs(1);        cout<<endl;            }    return 0;} 

View Code

#include <iostream>
using namespace std;
int a[20],n;
int used[20];
int is_prime(int x)
{
int i;
for(i=2;i<x;i++)
if(x%i==0) return 0;
return 1;
}
void dfs(int cur)
{
int i;
if(cur==n&&is_prime(a[1]+a[n]))
{
for(i=1;i<n;i++) cout<<a[i]<<" ";
cout<<a[n]<<endl;
return ;
}
for(i=2;i<=n;i++)
{
if(is_prime(a[cur]+i)&&used[i]==0)
{
a[cur+1]=i;used[i]=1;dfs(cur+1);used[i]=0;
}
}
}
int main(int argc, char *argv[])
{
int c;
c=1;
while(cin>>n)
{
memset(used,0,sizeof(used));
used[1]=1;a[1]=1;

cout<<"Case "<<c++<<":"<<endl;
if(n%2==0)
dfs(1);
cout<<endl;

}
return 0;
}