[紫书]素数环 dfs回溯

06
2019/08

# [紫书]素数环 dfs回溯

## 题目描述

Prime Ring Problem

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.

### 样例输入

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

## 代码

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

百度已收录

Last modification：August 7th, 2019 at 02:03 pm

1. 小白白 QQ 8.0.8.4115 Android 9 中国 青海

注意 check里的ips 要加非 要判断的是 不是素数

2. 小米 9.3.2 Android 4.4.4 中国 山西 阳泉

素数少，所以1-12排合数总不会超时吧

1. Dxoca Google Chrome 74.0.3724.8 Windows 10 中国 青海
@灵

16的话 我的机器差不多2秒

2. Dxoca Google Chrome 74.0.3724.8 Windows 10 中国 青海
@灵

嗯嗯 差不多 现在 写出了bug 正在改