n 個鍛子的點數(shù)

題目：把 n 個骰子扔在地上，所有骰子朝上一面的點數(shù)之和為 s。輸入 n，打印出 s 的所有可能的值出現(xiàn)的概率。

解題思路

解法一：基于通歸求解，時間效率不夠高。

先把 n 個骰子分為兩堆：第一堆只有一個，另一個有 n-1 個。單獨的那一個有可能出現(xiàn)從 1 到 6 的點數(shù)。我們需要計算從 1 到 6 的每一種點數(shù)和剩下的 n-1 個骰子來計算點數(shù)和。接下來把剩下的 n-1 個骰子還是分成兩堆，第一堆只有一個， 第二堆有 n-2 個。我們把上一輪那個單獨骰子的點數(shù)和這一輪單獨骰子的點數(shù)相加， 再和剩下的 n-2 個骰子來計算點數(shù)和。分析到這里，我們不難發(fā)現(xiàn)這是一種遞歸的思路，遞歸結束的條件就是最后只剩下一個骰子。

我們可以定義一個長度為“6n-n+1”的數(shù)組， 和為 s 的點數(shù)出現(xiàn)的次數(shù)保存到數(shù)組第 s-n 個元素里。

解法二：基于循環(huán)求解，時間性能好

我們可以考慮用兩個數(shù)組來存儲骰子點數(shù)的每一個總數(shù)出現(xiàn)的次數(shù)。在一次循環(huán)中， 第一個數(shù)組中的第 n 個數(shù)字表示骰子和為 n 出現(xiàn)的次數(shù)。在下一循環(huán)中，我們加上一個新的骰子，此時和為 n 的骰子出現(xiàn)的次數(shù)應該等于上一次循環(huán)中骰子點數(shù)和為 n-1 、n-2 、n-3 、n-4, n-5 與 n-6 的次數(shù)的總和，所以我們把另一個數(shù)組的第 n 個數(shù)字設為前一個數(shù)組對應的第 n-1 、n-2 、n-3 、n-4、n-5 與 n-6 之和。

代碼實現(xiàn)

public class Test43 {
    /**
     * 基于通歸求解
     *
     * @param number 色子個數(shù)
     * @param max    色子的最大值
     */
    public static void printProbability(int number, int max) {
        if (number < 1 || max < 1) {
            return;
        }
        int maxSum = number * max;
        int[] probabilities = new int[maxSum - number + 1];
        probability(number, probabilities, max);
        double total = 1;
        for (int i = 0; i < number; i++) {
            total *= max;
        }
        for (int i = number; i <= maxSum; i++) {
            double ratio = probabilities[i - number] / total;
            System.out.printf("%-8.4f", ratio);
        }
        System.out.println();
    }
    /**
     * @param number        色子個數(shù)
     * @param probabilities 不同色子數(shù)出現(xiàn)次數(shù)的計數(shù)數(shù)組
     * @param max           色子的最大值
     */
    private static void probability(int number, int[] probabilities, int max) {
        for (int i = 1; i <= max; i++) {
            probability(number, number, i, probabilities, max);
        }
    }
    /**
     * @param original      總的色子數(shù)
     * @param current       當前處理的是第幾個
     * @param sum           已經前面的色子數(shù)和
     * @param probabilities 不同色子數(shù)出現(xiàn)次數(shù)的計數(shù)數(shù)組
     * @param max           色子的最大值
     */
    private static void probability(int original, int current, int sum, int[] probabilities, int max) {
        if (current == 1) {
            probabilities[sum - original]++;
        } else {
            for (int i = 1; i <= max; i++) {
                probability(original, current - 1, i + sum, probabilities, max);
            }
        }
    }
    /**
     * 基于循環(huán)求解
     * @param number 色子個數(shù)
     * @param max    色子的最大值
     */
    public static void printProbability2(int number, int max) {
        if (number < 1 || max < 1) {
            return;
        }
        int[][] probabilities = new int[2][max * number + 1];
        // 數(shù)據初始化
        for (int i = 0; i < max * number + 1; i++) {
            probabilities[0][i] = 0;
            probabilities[1][i] = 0;
        }
        // 標記當前要使用的是第0個數(shù)組還是第1個數(shù)組
        int flag = 0;
        // 拋出一個骰子時出現(xiàn)的各種情況
        for (int i = 1; i <= max; i++) {
            probabilities[flag][i] = 1;
        }
        // 拋出其它骰子
        for (int k = 2; k <= number; k++) {
            // 如果拋出了k個骰子，那么和為[0, k-1]的出現(xiàn)次數(shù)為0
            for (int i = 0; i < k; i++) {
                probabilities[1 - flag][i] = 0;
            }
            // 拋出k個骰子，所有和的可能
            for (int i = k; i <= max * k; i++) {
                probabilities[1 - flag][i] = 0;
                // 每個骰子的出現(xiàn)的所有可能的點數(shù)
                for (int j = 1; j <= i && j <= max; j++) {
                    // 統(tǒng)計出和為i的點數(shù)出現(xiàn)的次數(shù)
                    probabilities[1 - flag][i] += probabilities[flag][i - j];
                }
            }
            flag = 1 - flag;
        }
        double total = 1;
        for (int i = 0; i < number; i++) {
            total *= max;
        }
        int maxSum = number * max;
        for (int i = number; i <= maxSum; i++) {
            double ratio = probabilities[flag][i] / total;
            System.out.printf("%-8.4f", ratio);
        }
        System.out.println();
    }
    public static void main(String[] args) {
        test01();
        test02();
    }
    private static void test01() {
        printProbability(2, 4);
    }
    private static void test02() {
        printProbability2(2, 4);
    }
}

運行結果

http://wiki.jikexueyuan.com/project/for-offer/images/61.png" alt="" />