计算滚动某个数字的方式数

Question

我是一名高中计算机科学专业的学生,​​今天我遇到了一个问题:

节目描述:骰子玩家有一种信念,即投掷三个骰子十分比一个骰子更容易获得.你能写一个证明或反驳这种信念的程序吗？

让计算机计算所有可能的方式可以抛出三个骰子:1 + 1 + 1,1 + 1 + 2,1 + 1 + 3等.将这些可能性加起来,看看有多少给出九个结果,多少给十.如果更多给十,那么信念就会得到证实.

我很快就制定了一个强力解决方案

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个骰子获得每个总和的方法的数量.使用1个模具,每个模具显然有1个解决方案.然后我通过蛮力计算了2和3个骰子的组合.这些是两个:

有1种方法可以滚动2种
有2种方式可以滚动3种
有3种方式可以滚动4种
有4种方式可以滚动5种
有5种方式可以滚动6种
有6种方式可以滚动7种
有5种滚动方式8滚动方式
有4种方式滚动方式
有3种方式
有2种滚动方式有11
种滚动方式有1种方式

这看起来很简单; 它可以用简单的线性绝对值函数计算.但事情变得越来越棘手.有3:

有1种方法可以滚动3种
有3种方式可以滚动4种
有6种方式可以滚动5种
有10种方式可以滚动6种
有15种方式可以滚动7种
有21种方式可以滚动8
种滚动的25种方式9
有27种方式滚动10
种滚动方式有27种方式
有25种方式滚动12
种滚动方式有21种方式有13
种滚动方式有14
种方式有10种方式滚动15
有6种方法可以滚动16种
有3种方式可以滚动17
种滚动方式有18种

所以我看一下,我想:酷,三角数字!但是,我注意到那些讨厌的25和27.所以它显然不是三角形数字,但仍然是一些多项式展开,因为它是对称的.
所以我带到谷歌,我遇到了这个页面,详细介绍了如何用数学做这个.使用重复的衍生物或扩展来找到它是相当容易的(虽然很长),但对我来说编程要困难得多.我不太明白第二和第三个答案,因为我之前从未在数学研究中遇到过这种符号或那些概念.有人可以解释我如何编写一个程序来做这个,或解释在该页面上给出的解决方案,以便我自己理解组合学？

编辑:我正在寻找一种解决这个问题的数学方法,它给出了一个精确的理论数,而不是通过模拟骰子

Answer 1

使用generate-function方法的解决方案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);
}

乍一看,这似乎是一个相当简单有效的解决方案.但是你会注意到许多相同值的计算,numDice并且sum可能反复重复计算,这使得这个解决方案可能比原来的强力方法效率更低.例如,在计算3骰子的所有计数时,我的程序numPossibilities总共运行该函数15106,而不是只6^3 = 216执行执行的循环.

要使此解决方案可行,您需要再添加一项技术 - 先前计算结果的memoization(缓存).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