一尘不染

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

java

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

程序说明:掷骰子的人相信,掷三个骰子,十个比掷九个更容易。您可以编写一个证明或否定这一信念的程序吗?

让计算机计算所有可能的投掷三个骰子的方法: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,我在此页面上找到了有关如何使用数学方法进行此操作的详细信息。使用重复的导数或扩展来找到它是很容易的(尽管很长),但是对我来说很难编程。我不太了解第二和第三个答案,因为我以前从未在数学学习中遇到过这种记号或那些概念。有人可以请我解释一下如何编写程序来执行此操作,或者请解释该页面上给出的解决方案,以使我对组合技术有所了解。

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


阅读 219

收藏
2020-12-03

共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);
}

乍一看,这似乎是一个相当简单有效的解决方案。但是你会发现相同的值,很多计算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
2020-12-03