如何用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 (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的复杂性？

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

这样做的目的是让一个数组存储每个骰子的当前“状态”，开始时每个骰子都在一个骰子上，然后向上数。例如，使用三个骰子，您将生成以下组合：

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

一旦你有了状态，你就可以很容易地找到你想要的和。

我把细节留给你们，因为这似乎是一个有用的学习练习:)