素數(shù)環(huán)是一個計算機(jī)程序問題，指的是將從1到n這n個整數(shù)圍成一個圓環(huán)，
若其中任意2個相鄰的數(shù)字相加，結(jié)果均為素數(shù)，那么這個環(huán)就成為素數(shù)環(huán)。
問題描述：將從1到n這n個整數(shù)圍成一個圓環(huán)，若其中任意2個相鄰的數(shù)字相加，結(jié)果均為素數(shù)，那么這個環(huán)就成為素數(shù)環(huán)。n=20時，下面的序列就是一個素數(shù)環(huán)：
1 2 3 4 7 6 5 8 9 10 13 16 15 14 17 20 11 12 19 18
英文名：Prime Ring Problem
算法思想：采用回溯法實現(xiàn)，遍歷全部可能的情況,最終答案：有6309300中可能情況。

算法優(yōu)化：由于相鄰兩個數(shù)為素數(shù)，則必然一奇一偶，所以要是n=奇數(shù)時必然無解
如下代碼：

image.png

package me.ice.practice;

/**
 * time     5/24/2017
 * auther   ice
 * description:
 * <p>
 * 素數(shù)環(huán)是一個計算機(jī)程序問題，指的是將從1到n這n個整數(shù)圍成一個圓環(huán)，
 * 若其中任意2個相鄰的數(shù)字相加，結(jié)果均為素數(shù)，那么這個環(huán)就成為素數(shù)環(huán)。
 * <p>
 * 問題描述：將從1到n這n個整數(shù)圍成一個圓環(huán)，若其中任意2個相鄰的數(shù)字相加，結(jié)果均為素數(shù)，那么這個環(huán)就成為素數(shù)環(huán)。
 * n=20時，下面的序列就是一個素數(shù)環(huán)：
 * 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>
 * 算法思想：采用回溯法實現(xiàn)，遍歷全部可能的情況
 */
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;

        //如果是奇數(shù)，則無解
        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) {

        //如果是負(fù)數(shù)當(dāng)做正數(shù)來進(jì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]);
        //    }
        //}
    }
}