如何用N个六边骰子计算得到和X的概率

挑战： 例如，当使用3个六面骰子时，得到15之和的概率是多少。这可以通过获得5-5-5、6-6-3、3-6-6或更多选项来实现。

2个骰子的暴力解决方案-复杂性为6^2：

假设我们只有两个六面骰子，我们可以编写一个非常基本的代码：

public static void main(String[] args) {
   System.out.println(whatAreTheOdds(7));
}

public static double whatAreTheOdds(int wantedSum){
    if (wantedSum < 2 || wantedSum > 12){
        return 0;
    }

    int wantedFound = 0;
    int totalOptions = 36;

    for (int i = 1; i <= 6; i++) {
        for (int j = 1; j <= 6; j++) {
            int sum = i+j;
            if (sum == wantedSum){
                System.out.println("match: " + i  + " " + j );
                wantedFound +=1;
            }
        }
    }

    System.out.println("combinations count:" + wantedFound);
    return (double)wantedFound / totalOptions;
}

，7的输出将为：

匹配：1 6

匹配：2 5

匹配：3 4

匹配：4 3

匹配：5%2

匹配：6 1

组合计数：6

0.16666666666666666

问题是如何推广算法以支持N骰子：

public static double whatAreTheOdds(int wantedSum, int numberOfDices)

因为无法动态创建嵌套的for循环，所以必须使用不同的方法。

我想到了类似的东西：

 public static double whatAreTheOdds(int sum, int numberOfDices){

    int sum;
    for (int i = 0; i < numberOfDices; i++) {
        for (int j = 1; j <= 6; j++) {

        }
    }
}

但未能提出正确的算法。

这里的另一个挑战是-有没有一种方法可以有效地完成这项工作，而不是在6^N的复杂性中？

---

解决方案

如Alex's answer所示，存在一个组合公式：

在这个公式中，p是掷出的数字的总和(在你的问题中是X)，n是骰子的数目，s是每个骰子的边数(在你的问题中是6)。无论是使用循环计算二项式系数，还是使用帕斯卡三角形预计算，如果我们取s ；=-nbsp；6为常数，X-nbsp；- ；n为O(N)，则时间复杂度为O(n²)。

---

这里有一个替代算法，它一次计算所有的概率。其思想是使用discrete convolution来计算给定分布的两个随机变量之和的分布。通过使用exponentiation by squaring算法中的分治方法，我们只需进行O(log ；n)次卷积。

伪代码在下面；sum_distribution(v, n)返回一个数组，其中索引X-nbsp；- ；n处的值是n掷骰子总数为X的组合数。

// for exact results using integers, let v = [1, 1, 1, 1, 1, 1]
// and divide the result through by 6^n afterwards
let v = [1/6.0, 1/6.0, 1/6.0, 1/6.0, 1/6.0, 1/6.0]

sum_distribution(distribution, n)
    if n == 0
        return [1]
    else if n == 1
        return v
    else
        let r = convolve(distribution, distribution)
        // the division here rounds down
        let d = sum_distribution(r, n / 2)
        if n is even
            return d
        else
            return convolve(d, v)

卷积不能在线性时间内完成，因此运行时间由长度为3n的两个数组上的最后一个卷积控制，因为其他卷积位于足够短的数组上。

这意味着如果使用简单的卷积算法，计算所有概率需要O(n²)时间，如果使用fast Fourier transform，则需要O(Nlogn)时间。