题目描述
roblem Description
A ring is compose of n circles as shown in diagram. Put natural number 1, 2, ..., n into each circle separately, and the sum of numbers in two adjacent circles should be a prime.
Note: the number of first circle should always be 1.
Input
n (0 < n < 20).
Output
The output format is shown as sample below. Each row represents a series of circle numbers in the ring beginning from 1 clockwisely and anticlockwisely. The order of numbers must satisfy the above requirements. Print solutions in lexicographical order.
You are to write a program that completes above process.
Print a blank line after each case.
输入正整数n，对1——n进行排列，要求相邻的两个数的和是一个素数。
输出时 从整数1开始
素数环按逆时针排列，同一个素数环恰好之输出一次
请输出最多前5个个素数环的答案 以及生成素数环方案总数。
如果无解，输出"no solution!"
样例输入
10样例输出
<1> 1 2 3 4 7 6 5 8 9 10
<2> 1 2 3 4 7 10 9 8 5 6
<3> 1 2 3 4 9 8 5 6 7 10
<4> 1 2 3 8 5 6 7 4 9 10
<5> 1 2 3 8 5 6 7 10 9 4
96输入样例
6输出样例
<1>:1 4 3 2 5 6
<2>:1 6 5 2 3 4
2分析
利用DFS，进行回溯。 检查 本位+前位的是否素数以及本位是否重复 基本没啥大问题
记得回溯 很关键
代码
package BlueCup.Seven_recursion;
import java.util.Scanner;
public class Dfs5素数环 {
static int n;
static int[] rec;
public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
n = cin.nextInt();
rec = new int[n];
rec[0] = 1;
dfs(1);//第一个元素 1
if (count == 0)
System.out.println("no solution!");
else
System.out.println(count);
}
private static void dfs(int cur) {
if (cur == n && isP(rec[n - 1] + rec[0])) {//到达n个数 然后判断首+尾是否素数
count++;
if (count <= 5) {
print(rec);
System.out.println();
}
return;
}
for (int num = 2; num <= n; num++) {//放的数 从1开始 1初始化放了
if (check(num, rec[cur - 1])) {// 当前数组重复出现 且前面的数和本位和为素数
rec[cur] = num;//可以填
dfs(cur + 1);//填下一个数
rec[cur] = 0;//回溯
}
}
}
static int count = 0;
public static void print(int[] rec) {
System.out.print("<" + count + ">:");
for (int i = 0; i < rec.length; i++) {
System.out.print(rec[i] + " ");
}
}
/**
* 判断素数
*
* @param num
* @return
*/
private static boolean isP(int num) {
for (int i = 2; i * i <= num; i++)
if (num % i == 0) return false;
return true;
}
//判断重复
private static boolean check(int num, int cur) {
for (int e : rec) {
if (num == e || !isP(num + cur))//相等 不是素数->false
return false;
}
return true;
}
}本文地址：https://dxoca.cn/Algorithm/225.html 百度已收录
版权说明：若无注明，本文皆为“Dxoca's blog （寒光博客）”原创，转载请保留文章出处。
注意 check里的ips 要加非 要判断的是 不是素数
素数少，所以1-12排合数总不会超时吧
16的话 我的机器差不多2秒
嗯嗯 差不多 现在 写出了bug 正在改