素数环
时间限制： 1000 ms | 内存限制： 65535 KB
难度： 2
- 描述
-
有一个整数n，把从1到n的数字无重复的排列成环，且使每相邻两个数（包括首尾）的和都为素数，称为素数环。
为了简便起见，我们规定每个素数环都从1开始。例如，下图就是6的一个素数环。
- 输入
- 有多组测试数据，每组输入一个n(0<n<20)，n=0表示输入结束。
- 输出
- 每组第一行输出对应的Case序号，从1开始。
如果存在满足题意叙述的素数环，从小到大输出。
否则输出No Answer。 - 样例输入
-
6 8 3 0
- 样例输出
-
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 Case 3: No Answer
思路：
深搜，如果n为奇数就不用搜了，因为如果n为奇数，则必有两个奇数在一块，和则为偶数；
还有1是除外的，1和自身成环，n最大19，所以最大和应为19+18=37，所以只需要找出37以内的素数就可以了，
还有就是，要想成环，必须是奇偶相间出现
import java.util.HashMap;
import java.util.Scanner;
public class Main {//深搜
static int a[];
static boolean ok[];
static HashMap<Integer, Boolean> map=new HashMap<Integer, Boolean>();
static boolean okk=true;
public static void main(String[] args) {
Scanner input=new Scanner(System.in);
F(map);
int e=1;
while(true){
okk=true;
int n=input.nextInt();
if(n==0)
break;
System.out.println("Case "+(e++)+":");
if(n==1){//1特殊，和自己成环
System.out.println(1);
continue;
}
if(n%2==1){//如果n为奇数，则必有两个奇数在一块，和则为偶数，不是素数
System.out.println("No Answer");
continue;
}
a=new int[n];
ok=new boolean[n+1];
a[0]=1;
ok[1]=true;
for(int i=2;i<=n;i+=2){
if(map.get(1+i)!=null){
ok[i]=true;
a[1]=i;
dfs(2,n);
ok[i]=false;
}
}
if(okk)
System.out.println("No Answer");
}
}
private static void dfs(int m, int n) {
if(m==n&&map.get(a[m-1]+1)!=null){
okk=false;
for(int i=0;i<n-1;i++)
System.out.print(a[i]+" ");
System.out.println(a[n-1]);
return;
}
//要满足素数环，必定是奇偶相交替出现
if(a[m-1]%2==0){
for(int i=3;i<=n;i+=2){
if(ok[i]){
continue;
}
if(map.get(a[m-1]+i)!=null){
ok[i]=true;
a[m]=i;
dfs(m+1,n);
ok[i]=false;
}
}
}
else{
for(int i=2;i<=n;i+=2){
if(ok[i]){
continue;
}
if(map.get(a[m-1]+i)!=null){
ok[i]=true;
a[m]=i;
dfs(m+1,n);
ok[i]=false;
}
}
}
}
private static void F(HashMap<Integer, Boolean> map) {
map.put(2, true);
map.put(3, true);
map.put(5, true);
map.put(7, true);
map.put(11, true);
map.put(13, true);
map.put(17, true);
map.put(19, true);
map.put(23, true);
map.put(29, true);
map.put(31, true);
map.put(37, true);
}
}