计算滚动一定数量的方式的数量

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 8
种滚动方式9
一种3种滚动方式10
一种2种滚动方式11
一种1种滚动方式12

看起来很简单；可以使用简单的线性绝对值函数进行计算。但是，事情开始变得棘手。与3：

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

所以我看了一下，我想：很酷的三角数！但是，然后我注意到那些讨厌的25和27。因此，显然它不是三角数，而是一些多项式展开式，因为它是对称的。
因此，我进入了Google，我在此页面上找到了有关如何使用数学方法进行此操作的详细信息。使用重复的导数或扩展来找到它是很容易的（尽管很长），但是对我来说很难编程。我不太了解第二和第三个答案，因为我以前从未在数学学习中遇到过这种记号或那些概念。有人可以请我解释一下如何编写程序来执行此操作，或者请解释该页面上给出的解决方案，以使我对组合技术有所了解。

编辑：我正在寻找一种数学方法来解决此问题，它提供了一个准确的理论数字，而不是通过模拟骰子

Answer 1

使用生成函数方法的解决方案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执行一次的循环。

为了使该解决方案可行，您需要添加另一种技术-
先前计算结果的记忆（缓存）。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