基于骰子点数，时间效率不够高

话题：

将n个骰子扔在地上，所有骰子向上面的点数之和为s。 输入n，打印出s所有可能取值的概率。

分析：

n个骰子点数，最小值为n，最大值为6n。根据排列组合，n个骰子所有点的排列数为

，需要先统计每个点出现的次数，再除以

，可以计算出每个点出现的概率。

基于骰子点数，时间效率不够高

先把n个骰子分成两堆：第一堆有1，第二堆有n-1。 第一堆可能有1~6个，我们需要计算每一种1~6的点数和剩下的n-1个骰子的点数之和。 接下来，剩下的n-1个骰子还是分成两堆：第一堆有1，第二堆有n-2。 将上一轮个人骰子和本轮个人骰子的点数相加，再将剩余的n-2个骰子相加btc骰子概率计算器，计算点数总和。 这是一个递归的思路，递归终止的条件是最后还剩一个骰子。

定义一个长度为6n-n+1的数组，将和为s的点出现的次数放入下标为sn的位置。

基于循环查找骰子点，时间性能好

递归里面有很多重复的计算，理解起来比较困难。 我不明白。 我们使用循环来解决这个问题。

设f(n,k)表示n个骰子，某一个骰子的总和为k的次数，如果n个骰子的结果为k，这个结果与n-1个骰子的结果相关，则有6种情况，第n个骰子可能出现1~6，那么前n-1个骰子会分别出现k-1~k-6，所以f(n,k)=f(n-1,k -1)+ f(n-1,k-2)+f(n-1,k-3)+f(n-1,k-4)+f(n-1,k-5)+f(n-1, k-6), 其中 n>0, k≤6n。 当初是怎样的？ f(1,1)=f(1,2)=f(1,3)=f(1,4)=f(1,5)=f(1,6)=1。 用递归的思维去分析，用循环自下而上的解决代码。

解决方案：基于骰子点数，时间效率不够高

package com.wsy;

public class Main {
    public static int[] result;
    public static int maxValue = 6;
    public static void main(String[] args) {
        int n = 5;
        printProbability(n);
    }
    public static void printProbability(int n) {
        if (n < 1) {
            return;
        }
        result = new int[n * maxValue - n + 1];

        int maxSum = maxValue * n;
        for (int i = 1; i <= maxValue; i++) {
            probability(n, n, i);
        }
        int total = (int) Math.pow(maxValue, n);
        for (int i = n; i <= maxSum; i++) {
            System.out.println("s=" + i + "\tp=" + (1.0 * result[i - n] / total));
        }
    }
    public static void probability(int original, int current, int sum) {
        if (current == 1) {
            result[sum - original]++;
        } else {
            for (int i = 1; i <= maxValue; i++) {

                probability(original, current - 1, i + sum);
            }
        }
    }
}

基于循环查找骰子点btc骰子概率计算器，时间性能好

package com.wsy;
public class Main {
    public static int[] result;
    public static int maxValue = 6;
    public static void main(String[] args) {
        int n = 6;

        printProbability(n);
    }
    public static void printProbability(int n) {
        if (n < 1) {
            return;
        }
        result = new int[maxValue * n + 1];
        // 投出第1个骰子
        for (int i = 1; i <= maxValue; i++) {// f(1,1)=f(1,2)=f(1,3)=f(1,4)=f(1,5)=f(1,6)=1
            result[i] = 1;
        }
        for (int i = 2; i <= n; i++) {// 依次投出第i个骰子
            // 从后面向前更新result，因为投出第i个骰子后，[i,i*maxValue]之间的值都要更新，新增了一个骰子，可能构成的情况更多了
            // [1,i]之间的值也要更新，增加了骰子，有的值就取不到了，比如n个骰子，sum

            // 后面的值要用到前面的值在n-1时候的状态，如果先更新前面的值，后面的值在计算的时候，前面的值就是n时候的状态了
            for (int j = i * maxValue; j >= 1; j--) {
                int temp = 0;
                // 计算f(n-1,j-1)+f(n-1,j-2)+f(n-1,j-3)+f(n-1,j-4)+f(n-1,j-5)+f(n-1,j-6)，注意有的时候j小于6，累加不到j-6，就用0代替
                for (int k = 1; k <= maxValue; k++) {
                    temp += j > k ? result[j - k] : 0;
                }
                result[j] = temp;
            }
        }
        int total = (int) Math.pow(maxValue, n);
        for (int i = n; i <= n * maxValue; i++) {
            System.out.println("s=" + i + "\tp=" + (1.0 * result[i] / total));
        }
    }
}