java - 如何计算使用N个六面骰子得到总和X的概率

Question

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

2 个骰子的强力解决方案 - 复杂度为 6^2:

假设我们只有 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 的输出将是:

match: 1 6

match: 2 5

match: 3 4

match: 4 3

match: 5 2

match: 6 1

combination count: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)，这个答案只是旨在为一般情况提供一个可能的实现，该实现比最简单的实现更好，使用记忆化和搜索空间修剪(仅探索可行的解决方案)。