19

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

程序描述： 掷骰子的人认为掷三个骰子，十比九更容易得到。你能写一个程序来证明或反驳这种信念吗？

让计算机计算所有可能的掷三个骰子的方式：1 + 1 + 1、1 + 1 + 2、1 + 1 + 3 等。将这些可能性中的每一个加起来，看看有多少得到 9 作为结果，多少给十。如果更多给十，那么这个信念就被证明了。

我很快就想出了一个蛮力解决方案，因此

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
有掷 8 的 5 种
方法 掷 9 的方法有 4 种
掷 10 的方法有 3 种
掷 11 的方法有 2 种
掷 12 的方法有 1 种

看起来很简单；它可以用一个简单的线性绝对值函数来计算。但随后事情开始变得棘手。3：

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

所以我看着那个，我想：很酷，三角数！但是，然后我注意到那些讨厌的 25 和 27。所以它显然不是三角数，而是一些多项式展开，因为它是对称的。
所以我去了谷歌，我遇到了这个页面，其中详细介绍了如何用数学来做到这一点。使用重复的导数或扩展来找到它相当容易（虽然很长），但对我来说编程要困难得多。我不太明白第二个和第三个答案，因为我以前在数学学习中从未遇到过这种符号或那些概念。有人可以解释我如何编写一个程序来做到这一点，或者解释该页面上给出的解决方案，以了解我自己对组合学的理解吗？

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

4

4 回答 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);
}

乍一看，这似乎是一个相当简单有效的解决方案。但是，您会注意到对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
于 2013-11-01T01:54:57.953 回答
2

您不需要蛮力，因为您的第一轮决定了第二轮可以使用的值，而第一轮和第二轮都决定了第三轮。让我们以十位为例，假设您滚动 a 6，这10-6=4意味着您仍然需要4。对于第二卷你至少需要3，因为你的第三卷至少应该算数1。所以第二卷从1到3。假设你的第二卷是2，你有10-6-2=2，这意味着你的第三卷是 a 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-nm-lateral-dice-can-add -up-t

于 2013-11-01T02:24:37.417 回答
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_1以及P_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^s( a_s) 处的系数。推导的自由系数 (at x^0)为。所以，在 0 的导数是。s'ths! * a_ks'ths! * a_k

所以，我们必须推导出这个函数s时间。它可以使用推导规则来完成，但我认为它的复杂性会比计数方法更糟糕，因为每个推导都会产生“更复杂”的功能。以下是 Wolfram Alpha 的前三个推导：first、second和third。

一般来说，我更喜欢计数解决方案，mellamokb 给出了很好的方法和解释。

于 2013-11-01T12:12:13.463 回答
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);
    }

}

误差随着模拟次数的增加而减少，但以 cputime 为代价，但上述值非常快。

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}
于 2013-11-01T01:49:32.367 回答