素数环问题

素数环是一个计算机程序问题，指的是将从1到n这n个整数围成一个圆环，
若其中任意2个相邻的数字相加，结果均为素数，那么这个环就成为素数环。
问题描述：将从1到n这n个整数围成一个圆环，若其中任意2个相邻的数字相加，结果均为素数，那么这个环就成为素数环。n=20时，下面的序列就是一个素数环：
1 2 3 4 7 6 5 8 9 10 13 16 15 14 17 20 11 12 19 18
英文名：Prime Ring Problem
算法思想：采用回溯法实现，遍历全部可能的情况,最终答案：有6309300中可能情况。

算法优化：由于相邻两个数为素数，则必然一奇一偶，所以要是n=奇数时必然无解
如下代码：

image.png

package me.ice.practice;

/**
 * time     5/24/2017
 * auther   ice
 * description:
 * <p>
 * 素数环是一个计算机程序问题，指的是将从1到n这n个整数围成一个圆环，
 * 若其中任意2个相邻的数字相加，结果均为素数，那么这个环就成为素数环。
 * <p>
 * 问题描述：将从1到n这n个整数围成一个圆环，若其中任意2个相邻的数字相加，结果均为素数，那么这个环就成为素数环。
 * n=20时，下面的序列就是一个素数环：
 * 1 2 3 4 7 6 5 8 9 10 13 16 15 14 17 20 11 12 19 18
 * 英文名：Prime Ring Problem
 * <p>
 * <p>
 * 算法思想：采用回溯法实现，遍历全部可能的情况
 */
public class PrimeCircleProblem {

    public static int count = 0;

    public static void main(String[] args) {
        int[] a = new int[21];
        long start = System.currentTimeMillis();
        boolean ringProblem = getPrimeRingProblem(a);
        if (ringProblem) {
            long end = System.currentTimeMillis();
            System.out.println("总共用时:" + (end - start));
            System.out.println("总有" + count + "种可能");
        } else {
            System.out.println("此问题无解！");
        }

    }


    public static boolean getPrimeRingProblem(int a[]) {
        int k = 1;
        int n = a.length;
        a[0] = 1;

        //如果是奇数，则无解
        if ((n & 1) == 1) {
            return false;
        }

        while (k >= 1) {
            a[k]++;

            while (a[k] <= n) {
                if (check(a, k)) {
                    break;
                } else {
                    a[k]++;
                }
            }

            if (a[k] <= n && k == n - 1) {
                printArray(a);
            }

            if (a[1] == n + 1) {
                return true;
            }


            if (a[k] <= n && k < n - 1) {
                k += 1;
            } else {
                a[k--] = 0;
            }
        }

        return false;
    }

    private static boolean check(int[] a, int i) {

        if (!isPrime(a[i] + a[i - 1])) {
            return false;
        }

        //判断是否前面是否有跟它相同的值
        for (int j = 0; j < i; j++) {
            if (a[j] == a[i]) {
                return false;
            }
        }

        if (i == a.length - 1) {
            return isPrime(a[0] + a[a.length - 1]);
        }

        return true;
    }

    public static boolean isPrime(int n) {

        //如果是负数当做正数来进行处理
        if (n < 0) {
            n = -n;
        }

        if (n == 1 || n == 0) {
            return false;
        }
        int r = (int) Math.sqrt(n);
        for (int i = 2; i <= r; i++) {
            if (n % i == 0) {
                return false;
            }
        }
        return true;
    }


    private static void printArray(int[] array) {
        count++;
        //System.out.print("第" + (count++) + "个: ");
        //for (int i = 0; i < array.length; i++) {
        //    if (i < array.length - 1) {
        //        System.out.print(array[i] + "、");
        //    } else {
        //        System.out.println(array[i]);
        //    }
        //}
    }
}