计算掷出一定数量的方式数量

algorithm java combinatorics probability

2022-09-02 13:34:58

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

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

让计算机计算所有可能的方式可以投掷三个骰子：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个骰子以获得特定数字的方法的数量。因此，我开始生成使用n个骰子获取每个和的方法数量。对于1个芯片，显然每个芯片都有1个解决方案。然后，我通过蛮力计算了2和3骰子的组合。这些是两个：

有1种滚动方法 2
有2种滚动方法 3
滚动方法 4滚动方法 4
滚动方法 5滚动方法 6
滚动方法 6
滚动方法 7
有5种滚动方法 8
有4种滚动方法 a 9
有3种滚动方法 a 10
有2种方法滚 11
的方法有 12 滚 12 的方法

这看起来很简单;它可以使用简单的线性绝对值函数进行计算。但后来事情开始变得越来越棘手。含 3：

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

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

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

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

乍一看，这似乎是一个相当简单有效的解决方案。但是，您会注意到，对相同的值和的许多计算可能会一遍又一遍地重复和重新计算，从而使此解决方案可能比原始的蛮力方法更有效。例如，在计算骰子的所有计数时，我的程序总共运行了该函数几次，而不是您的循环仅执行。numDicesum3numPossibilities151066^3 = 216

要使此解决方案可行，您需要再添加一种技术 - 对以前计算的结果进行记忆（缓存）。例如，使用对象，可以存储已计算的组合，并在运行递归之前首先引用这些组合。当我实现缓存时，该函数仅运行总计次数来计算骰子的结果。HashMapnumPossibilities1513

随着骰子数量的增加，效率的提高会越来越大（结果基于我自己实现的解决方案的模拟）：

# 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

答案 2

您不需要暴力破解，因为您的第一个滚动决定了可以在第二个滚动中使用的值，而第一个和第二个滚动都决定了第三个滚动。让我们以十个例子，假设你掷了一个，所以这意味着你仍然需要。对于第二卷，你至少需要，因为你的第三卷至少应该算数。因此，第二个滚动从到.假设你的第二卷是，你有，意味着你的第三卷是一个，没有其他办法。610-6=443113210-6-2=22

十个伪代码：

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-n-m-sided-dice-can-add-up-t