算法分析与设计：搜索（素数环）

时间限制(普通/Java):1000MS/3000MS          运行内存限制:65536KByte 总提交:178            测试通过:35

描述

 

将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 
        
         using namespace std;int a[20],n;int used[20];int is_prime(int x){    int i;    for(i=2;i
         
          >n)    {        memset(used,0,sizeof(used));        used[1]=1;a[1]=1;                cout<<"Case "<
          
           <<":"<
          
         
        

#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;

}