我是一名高中计算机科学系的学生,今天遇到一个问题:
程序说明:掷骰子的人相信,掷三个骰子,十个比掷九个更容易。您可以编写一个证明或否定这一信念的程序吗? 让计算机计算所有可能的投掷三个骰子的方法:1 + 1 + 1,1 + 1 + 2,1 + 1 + 3,依此类推。将这些可能性中的每一个相加,然后看看有多少会给出九个有多少给十。如果多给十,那么信念就会得到证明。
程序说明:掷骰子的人相信,掷三个骰子,十个比掷九个更容易。您可以编写一个证明或否定这一信念的程序吗?
让计算机计算所有可能的投掷三个骰子的方法: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,我在此页面上找到了有关如何使用数学方法进行此操作的详细信息。使用重复的导数或扩展来找到它是很容易的(尽管很长),但是对我来说很难编程。我不太了解第二和第三个答案,因为我以前从未在数学学习中遇到过这种记号或那些概念。有人可以请我解释一下如何编写程序来执行此操作,或者请解释该页面上给出的解决方案,以使我对组合技术有所了解。
编辑:我正在寻找一种数学方法来解决此问题,它提供了一个准确的理论数字,而不是通过模拟骰子
使用生成函数方法的解决方案N(d, s)可能最容易编程。您可以使用递归很好地对问题建模:
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执行一次的循环。
numDice
sum
3
numPossibilities
15106
6^3 = 216
为了使该解决方案可行,您需要添加另一种技术- 先前计算结果的记忆(缓存)。HashMap例如,使用一个对象,您可以存储已经计算出的组合,并在运行递归之前先引用它们。当我实现一个缓存时,该numPossibilities函数只运行151总时间来计算3骰子的结果。
HashMap
151
随着骰子数量的增加,效率提高也越来越大(结果基于我自己实现的解决方案的仿真结果):
# 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