杭电1016Java实现

主环问题：
问题描述
如图所示，环由n个圆组成。将自然数1,2，…，n分别放入每个圆圈中，并且相邻两个圆圈中的数字总和应为素数。
注意：第一个圆圈的数量应该始终为1。
输入
n（0《n<20）。
输出
输出格式如下所示。每行代表从1开始顺时针和逆时针旋转的一系列圆圈数字。数字的顺序必须符合上述要求。按照字典顺序打印解决方案。

你要编写一个完成上述过程的程序。

在每个案例后打印一个空行。
Sample Input
6
8
Sample Output
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
思路：核心思路是使用dfs暴力破解，遍历所有能形成的可能性，然后输出满足条件的，优化的话可以考虑剪枝，还要用一些参数表示元素的个数和之前存储的元素，考虑的条件是元素和前一个元素的和是否为素数，如果到了最后一个数还要考虑第一个数。
代码如下：

import java.util.Scanner;
public class 杭电1016 { static boolean b[]=new boolean[21];//用于判断是否用过 static int time=0;//层数 public static void main(String[] args) { Scanner sc=new Scanner(System.in); int Case=1;//输入案例第几个 while(sc.hasNext()) { int m=sc.nextInt();//个数 int a[]=new int[m];//存储元素 a[0]=1; System.out.println("Case " Case   ":"); dfs(m,a); System.out.println(); //judgel(m);//判断素数 } } private static boolean judgel(int m) {//如果为素数返回真 for(int i=2;i<m;i  ) { if(m%i==0) {return false;} } return true; }
private static void dfs(int m, int[] a) { if(time==m-1) {for(int i=0;i<m;i   ) //知道长度满足，一定满足情况 {if(i==m-1)System.out.print(a[i]);else System.out.print(a[i] " ");}System.out.println();} else for(int i=2;i<m 1;i  ) { if(!b[i]) { if(time==m-2) { b[i]=true; if(judgel(i a[time])&&judgel(i 1)) { a[  time]=i; dfs(m,a); time--; } b[i]=false; } else { b[i]=true; if(judgel(i a[time])) { a[  time]=i; dfs(m,a); time--; } b[i]=false; } } } }
}
  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
  
44
  
45
  
46
  
47
  
48
  
49
  
50
  
51
  
52
  
53
  
54
  
55
  
56
  
57
  
58
  
59
  
60
 

新手小白，时间和复杂度都很高。。

文章来源: bigsai.blog.csdn.net，作者：Big sai，版权归原作者所有，如需转载，请联系作者。

原文链接：bigsai.blog.csdn.net/article/details/79835103