如何用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(n2)。


这里有一个替代算法,它一次计算所有的概率。其思想是使用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(n2)时间,如果使用fast Fourier transform,则需要O(Nlogn)时间。

相关文章