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

Question

挑战：例如，使用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 (sum< 2 || sum> 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的复杂度？

Answer 1

这里是一个带有备忘录的递归解决方案，用于计算组合。

import java.util.Arrays;
import java.lang.Math;

class Dices {
    public static final int DICE_FACES = 6;

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

    public static double whatAreTheOdds(int sum, int dices) {
        if (dices < 1 || sum < dices || sum > DICE_FACES * dices) return 0;

        long[][] mem = new long[dices][sum];
        for (long[] mi : mem) {
            Arrays.fill(mi, 0L);
        }
        long n = whatAreTheOddsRec(sum, dices, mem);
        return n / Math.pow(DICE_FACES, dices);
    }

    private static long whatAreTheOddsRec(int sum, int dices, long[][] mem) {
        if (dices <= 1) {
            return 1;
        }
        long n = 0;
        int dicesRem = dices - 1;
        int minFace = Math.max(sum - DICE_FACES * dicesRem, 1);
        int maxFace = Math.min(sum - dicesRem, DICE_FACES);
        for (int i = minFace; i <= maxFace; i++) {
            int sumRem = sum - i;
            long ni = mem[dicesRem][sumRem];
            if (ni <= 0) {
                ni = whatAreTheOddsRec(sumRem, dicesRem, mem);
                mem[dicesRem][sumRem] = ni;
            }
            n += ni;
        }
        return n;
    }
}

输出：

0.048464367913724195

编辑：根据记录，该算法的复杂度仍为O（6 ^ n），此答案旨在通过记忆和搜索空间修剪为一般情况提供一种比最简单的实现更好的可能实现（仅探索可行的解决方案）。

Answer 2

您可能想看看Wolfram article，这是一种完全不同的方法，它可以通过一个循环来计算所需的概率。

Answer 3

想法是有一个数组，用于存储每个骰子的当前“状态”，每个骰子都将从一个骰子开始，然后向上计数。例如，使用三个骰子，您将生成组合：

111
112
...
116
121
122
...
126
...
665
666

一旦有了状态，就可以轻松地找到总和是否是您要的数字。

我将详细信息留给您，因为这似乎是有用的学习练习：）

Answer 4

想法是让一个数组存储每个骰子的当前“状态”，每个骰子的起始位置将为1，然后向上计数。例如，使用三个骰子，您将生成组合：

111
112
...
116
121
122
...
126
...
665
666

一旦有了状态，就可以轻松地找到总和是否是您要的数字。

我将详细信息留给您，因为这似乎是有用的学习练习：）