计算掷出某个数字的方法数量

19
我是一名高中计算机科学学生,今天我被给了一个问题:
程序描述:骰子玩家有一种信仰,认为在掷三个骰子时,得到十比得到九更容易。你能写一个程序来证明或反驳这种信仰吗?
让计算机计算扔三个骰子的所有可能方式:1 + 1 + 1,1 + 1 + 2,1 + 1 + 3等。将每个可能性相加,看看有多少个结果为9,有多少个结果为10。如果有更多的结果为10,则证明了这种信仰。
我很快想出了一种暴力解决方案,如下所示:
int sum,tens,nines;
    tens=nines=0;

    for(int i=1;i<=6;i++){
        for(int j=1;j<=6;j++){
            for(int k=1;k<=6;k++){
                sum=i+j+k;
                //Ternary operators are fun!
                tens+=((sum==10)?1:0);
                nines+=((sum==9)?1:0);
            }
        }

    }
    System.out.println("There are "+tens+" ways to roll a 10");
    System.out.println("There are "+nines+" ways to roll a 9");

这个算法可以正常工作,但是它不可扩展。我正在尝试找到一种算法,可以计算掷n个骰子得到特定数字的方法数。因此,我开始生成使用n个骰子获得每个总和的方法数。对于1个骰子,显然有1种解决方案。然后,我通过暴力破解计算了使用2个和3个骰子的组合。这些是两个骰子的结果:
Which looks straightforward enough; it can be calculated with a simple linear absolute value function. But then things start getting trickier. With 3:

掷出3的方法有1种
掷出4的方法有3种
掷出5的方法有6种
掷出6的方法有10种
掷出7的方法有15种
掷出8的方法有21种
掷出9的方法有25种
掷出10的方法有27种
掷出11的方法有27种
掷出12的方法有25种
掷出13的方法有21种
掷出14的方法有15种
掷出15的方法有10种
掷出16的方法有6种
掷出17的方法有3种
掷出18的方法有1种

所以我看到这个,想:酷,三角形数!然后,我注意到那些讨厌的25和27。因此,它显然不是三角形数,但仍然是一些多项式扩展,因为它是对称的。
于是我去谷歌,找到了这个页面,详细介绍了如何用数学方法解决这个问题。使用重复导数或扩展很容易(尽管很长)找到这个结果,但对我来说编程会更难。我没有完全理解第二个和第三个答案,因为我之前的数学学习中从未遇到过那种符号或概念。有人能否解释一下如何编写程序来解决这个问题,或者解释该页面上给出的解决方案,以便我更好地理解组合数学?

编辑:我正在寻找一种数学方法来解决这个问题,可以得到一个精确的理论数字,而不是通过模拟骰子。


这似乎有点离题,因为您正在寻找一个数学解决方案,一旦您知道自己在做什么,您就可以编写代码。因此,从本质上讲,它似乎并不是一个编程问题。 - Duncan Jones
4个回答

13

使用生成函数方法并带有N(d, s)的解决方案可能是最容易编程的。您可以使用递归来很好地对问题进行建模:

public int numPossibilities(int numDice, int sum) {
    if (numDice == sum)
        return 1;
    else if (numDice == 0 || sum < numDice)
        return 0;
    else
        return numPossibilities(numDice, sum - 1) +
               numPossibilities(numDice - 1, sum - 1) -
               numPossibilities(numDice - 1, sum - 7);
}

乍一看,这似乎是一个相当简单和高效的解决方案。 但是你会注意到,对于相同的 numDicesum 值的许多计算可能会重复并一遍又一遍地重新计算,使得这个解决方案甚至比您最初的暴力方法更低效。例如,在计算所有3个骰子的点数时,我的程序总共运行了numPossibilities函数15106次,而您的循环仅需要执行6^3 = 216次。

为了使这个解决方案可行,您需要添加一种技术 - 记忆化(缓存)以前计算过的结果。例如,使用HashMap对象,您可以存储已经计算过的组合,并在递归之前首先引用那些组合。当我实现缓存时,numPossibilities函数仅总共运行151次来计算3个骰子的结果。

随着您增加骰子的数量,效率提高得越来越大(结果基于使用我自己实现的解决方案进行的模拟):

# Dice | Brute Force Loop Count | Generating-Function Exec Count
3      | 216 (6^3)              | 151
4      | 1296 (6^4)             | 261
5      | 7776 (6^5)             | 401
6      | 46656 (6^6)            | 571
7      | 279936 (6^7)           | 771
...
20     | 3656158440062976       | 6101

这很棒,但我不熟悉HashMap对象。你能向我展示在这种情况下如何使用它,并指引我学习它们的地方吗? - scrblnrd3
你也可以使用二维锯齿数组来存储它们。例如,sum 的可能输入是 numDice - 6*numDice。因此,实例化一个具有范围 [1][1-6][2][1-12][3][1-18] 等的数组,直到您计算结果的骰子数量为止。如果您想了解 HashMap 的介绍,可以尝试访问 http://www.java-made-easy.com/java-collections.html。 - mellamokb
谢谢。这个给了我想要的一切,我能够弄清楚如何使用记忆化并理解代码,所以感谢您教导我。 - scrblnrd3
@mellamokb,我很难理解你的算法是如何工作的。你能否扩展一下你的答案并解释一下吗? - Duncan Jones
1
@Duncan:可能不太清楚,但是OP指的是Math.SE上的另一个问题(在最后一段),该问题更加严谨地解决了此问题。 我基于[此答案](http://math.stackexchange.com/a/68057/2704)建模编程解决方案-我将推迟到那篇文章中获得比我更好的解释 :) - mellamokb
@mellamokb 或许我做错了什么,但是你开发的方法没有返回掷出指定总和的方式数。当我运行它时,它只会给我一个StackOverflowException异常。有什么建议吗?比如说,对于一个非常简单的例子,我掷一颗骰子,希望找到获得总和为2的方法。那么它将是{1,1}和{2},总共有2种方法。 - JustMeh

2
您不需要暴力破解,因为您的第一次掷骰子就决定了第二次掷骰子可以使用哪些值,而第一次和第二次掷骰子都决定了第三次掷骰子。让我们以十位数为例,假设您掷出了6,那么10-6=4表示您仍需要4。对于第二次掷骰子,您至少需要3,因为您的第三次掷骰子至少应该计为1。所以第二次掷骰子从13。假设您的第二次掷骰子是2,那么您有10-6-2=2,这意味着您的第三次掷骰子是2,没有其他方法。

十位数的伪代码:

tens = 0

for i = [1..6] // first roll can freely go from 1 to 6
   from_j = max(1, 10 - i - 6) // We have the first roll, best case is we roll a 6 in the third roll
   top_j = min(6, 10 - i - 1) // we need to sum 10, minus i, minus at least 1 for the third roll
   for j = [from_j..to_j]
      tens++

请注意,每次循环都会增加1,因此最终您会知道该代码循环了27次。
以下是所有18个值的Ruby代码(抱歉不是Java,但容易理解)。请注意最小和最大值,它们确定每个骰子投掷可以有哪些值。
counts = [0] * 18

1.upto(18) do |n|
  from_i = [1, n - 6 - 6].max # best case is we roll 6 in 2nd and 3rd roll
  top_i = [6, n - 1 -1].min # at least 1 for 2nd and 3rd roll
  from_i.upto(top_i) do |i|
    from_j = [1, n - i - 6].max # again we have the 2nd roll defined, best case for 3rd roll is 6
    top_j = [6, n - i -1].min # at least 1 for 3rd roll
    from_j.upto(top_j) do
      # no need to calculate k since it's already defined being n - first roll - second roll
      counts[n-1] += 1
    end
  end
end

print counts

如果你想采用数学方法,可以参考以下链接:https://math.stackexchange.com/questions/4632/how-can-i-algorithmically-count-the-number-of-ways-n-m-sided-dice-can-add-up-t


该链接介绍了如何通过算法计算n个m面骰子投掷后总点数为t的方式数量。

随着骰子数量的增加,这个规模是如何扩展的?它只是6^(d-1),而不是6^d吗? - mellamokb
@mellamokb 请查看http://math.stackexchange.com/questions/4632/how-can-i-algorithmically-count-the-number-of-ways-n-m-sided-dice-can-add-up-t - aromero

2
数学描述只是为了进行相同计数的“技巧”。它使用多项式来表示骰子,1*x^6 + 1*x^5 + 1*x^4 + 1*x^3 + 1*x^2 + 1*x 意味着每个值 1-6 都被计算了一次,并且使用多项式乘法 P_1*P_2 来计算不同组合的计数。这样做是因为在某些指数(k)处的系数通过将 P_1P_2 中幂和为 k 的所有系数相加来计算。

例如,对于两个骰子:

(1*x^6 + 1*x^5 + 1*x^4 + 1*x^3 + 1*x^2 + 1*x) * (x^6 + x^5 + x^4 + x^3 + x^2 + x) = 
(1*1)*x^12 + (1*1 + 1*1)*x^11 + (1*1 + 1*1 + 1*1)*x^11 + ... + (1*1 + 1*1)*x^3 + (1*1)*x^2

用这种方法计算的复杂度与“计数”相同。
由于函数 (x^6 + x^5 + x^4 + x^3 + x^2 + x)^n 有更简单的表达式 (x(x-1)^6/(x-1))^n,因此可以使用导数方法。 (x(x-1)^6/(x-1))^n 是一个多项式,我们要寻找 x^sa_s)处的系数。自由系数(在 x^0 处)的 s'th 导数是 s! * a_k。因此,在 0 处的 s'th 导数是 s! * a_k
所以,我们必须对这个函数求导 s 次。可以使用导数规则来完成,但我认为它的复杂度甚至比计数方法更糟糕,因为每个导数都会产生“更复杂”的函数。以下是 Wolfram Alpha 的前三个导数:第一第二第三
总的来说,我更喜欢计数解决方案,mellamokb 提供了不错的方法和解释。

1

请查看蒙特卡罗方法,它们通常与输入大小成线性比例关系。在这种情况下,示例很简单,我们假设由于一次掷骰子不会影响其他骰子,所以我们可以简单地计算随机掷出的骰子面的总和(足够多次)而不是计数组合。

   public class MonteCarloDice {

    private Map<Integer, Integer> histogram;
    private Random rnd;
    private int nDice;
    private int n;

    public MonteCarloDice(int nDice, int simulations) {
        this.nDice = nDice;
        this.n = simulations;
        this.rnd = new Random();
        this.histogram = new HashMap<>(1000);
        start();
    }

    private void start() {
        for (int simulation = 0; simulation < n; simulation++) {
            int sum = 0;
            for (int i = 0; i < nDice; i++) {
                sum += rnd.nextInt(6) + 1;
            }
            if (histogram.get(sum) == null)
                histogram.put(sum, 0);
            histogram.put(sum, histogram.get(sum) + 1);
        }
        System.out.println(histogram);
    }


    public static void main(String[] args) {
        new MonteCarloDice(3, 100000);
        new MonteCarloDice(10, 1000000);
    }

}

错误减少随着模拟次数的增加而降低,但代价是 CPU 时间,但上述值非常快。
3个骰子
{3=498, 4=1392, 5=2702, 6=4549, 7=7041, 8=9844, 9=11583, 10=12310, 11=12469, 12=11594, 13=9697, 14=6999, 15=4677, 17=1395, 16=2790, 18=460}

10个骰子

{13=3, 14=13, 15=40, 17=192, 16=81, 19=769, 18=396, 21=2453, 20=1426, 23=6331, 22=4068, 25=13673, 24=9564, 27=25136, 26=19044, 29=40683, 28=32686, 31=56406, 30=48458, 34=71215, 35=72174, 32=62624, 33=68027, 38=63230, 39=56008, 36=71738, 37=68577, 42=32636, 43=25318, 40=48676, 41=40362, 46=9627, 47=6329, 44=19086, 45=13701, 51=772, 50=1383, 49=2416, 48=3996, 55=31, 54=86, 53=150, 52=406, 59=1, 57=2, 56=7}

1
我正在寻找一个更数学化的解决方案。 - scrblnrd3
蒙特卡罗方法是数学方法,不要被它的简单所欺骗 ;) 我们将其作为一种替代艰难数学的方法。它们被广泛用于模拟那些难以找到直接解析解(或者效率太低)的问题。 - arynaq
3
我认为原帖作者的暴力方法更好。1)它可以得出精确答案。2)相较于暴力迭代,你需要进行更多模拟才能获得“好”的分布。我发现对于三个骰子,你要模拟 10 万次掷骰子才能得到稍微靠谱的结果,而原帖作者只需计算 216 种情况。 - Geobits
当然,你可以尝试使用暴力或递归方法来模拟100个骰子的情况。这种方法的时间复杂度为O(simulations * dice),而暴力方法的时间复杂度为n^dice,递归方法的时间复杂度似乎是O(n^5)。当然,你有权对此进行负投票,但像这样的情况本质上是为蒙特卡罗算法而设计的。 - arynaq
只看你的 n=10,sims=1000000 的情况。你展示了掷出 [10,11,12] 的概率都相同,为零。这显然不接近真实情况。事实上,你掷出 11 的方式是掷出 10十倍。原因是你进行的模拟次数比可能性(6^n)少,所以它们不可能以正确的比例全部被覆盖。这就是为什么你不能只翻一次硬币来决定它是否是一个“公平”的硬币的原因。你需要至少翻一百次。 - Geobits
我并不是说蒙特卡罗方法是无用的,我只是说这 并不是 它本质上适用的情况。 - Geobits

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接