寒光博客

[紫书]素数环 dfs回溯
题目描述 输入正整数n,对1——n进行排列,要求相邻的两个数的和是一个素数。 输出时 从整数1开始 素数环按逆时...
扫描右侧二维码阅读全文
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.

输入正整数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;
    }
}
本文作者:Author:     文章标题:[紫书]素数环 dfs回溯
本文地址:https://dxoca.cn/Algorithm/225.html       百度已收录
版权说明:若无注明,本文皆为“Dxoca's blog (寒光博客)”原创,转载请保留文章出处。
Last modification:August 7th, 2019 at 02:03 pm
如果觉得我的文章对你有用,请随意赞赏

Leave a Comment

4 comments

  1. 小白白

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

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

    1. Dxoca
      @灵

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

    2. Dxoca
      @灵

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