Java 计算滚动某个数字的方法数

Calculate the number of ways to roll a certain number

提问by scrblnrd3

I'm a high school Computer Science student, and today I was given a problem to:

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

Program Description: There is a belief among dice players that in throwing three dice a ten is easier to get than a nine. Can you write a program that proves or disproves this belief?

Have the computer compute all the possible ways three dice can be thrown: 1 + 1 + 1, 1 + 1 + 2, 1 + 1 + 3, etc. Add up each of these possibilities and see how many give nine as the result and how many give ten. If more give ten, then the belief is proven.

程序说明：掷骰子的玩家普遍认为，掷三个骰子，掷出 10 个骰子比得到 9 个骰子更容易。你能编写一个程序来证明或反驳这种信念吗？

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

I quickly worked out a brute force solution, as such

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

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");

Which works just fine, and a brute force solution is what the teacher wanted us to do. However, it doesn't scale, and I am trying to find a way to make an algorithm that can calculate the number of ways to roll ndice to get a specific number. Therefore, I started generating the number of ways to get each sum with ndice. With 1 die, there is obviously 1 solution for each. I then calculated, through brute force, the combinations with 2 and 3 dice. These are for two:

哪个工作得很好，而一个蛮力解决方案正是老师希望我们做的。但是，它不能扩展，我正在尝试找到一种方法来制作一种算法，该算法可以计算掷n 个骰子以获得特定数字的方法数。因此，我开始生成用n 个骰子获得每个总和的方法数。对于 1 个骰子，每个骰子显然有 1 个解决方案。然后我通过蛮力计算了 2 个和 3 个骰子的组合。这些是两个：

There are 1 ways to roll a 2
There are 2 ways to roll a 3
There are 3 ways to roll a 4
There are 4 ways to roll a 5
There are 5 ways to roll a 6
There are 6 ways to roll a 7
There are 5 ways to roll a 8
There are 4 ways to roll a 9
There are 3 ways to roll a 10
There are 2 ways to roll a 11
There are 1 ways to roll a 12

有 1 种掷 a 的方法 2
有 2 种掷 a 3
有 3 种掷 a 4
有 4 种掷 a 5
有 5 种掷 a 6
有 6 种掷 a 7
有5 种方法可以掷出 8
有 4 种方法可以掷出 9
有 3 种方法可以掷出 10
有 2 种方法可以掷出 11
有 1 种方法可以掷出 12

Which looks straightforward enough; it can be calculated with a simple linear absolute value function. But then things start getting trickier. With 3:

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

There are 1 ways to roll a 3
There are 3 ways to roll a 4
There are 6 ways to roll a 5
There are 10 ways to roll a 6
There are 15 ways to roll a 7
There are 21 ways to roll a 8
There are 25 ways to roll a 9
There are 27 ways to roll a 10
There are 27 ways to roll a 11
There are 25 ways to roll a 12
There are 21 ways to roll a 13
There are 15 ways to roll a 14
There are 10 ways to roll a 15
There are 6 ways to roll a 16
There are 3 ways to roll a 17
There are 1 ways to roll a 18

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

So I look at that, and I think: Cool, Triangular numbers! However, then I notice those pesky 25s and 27s. So it's obviously not triangular numbers, but still some polynomial expansion, since it's symmetric.
So I take to Google, and I come across this pagethat goes into some detail about how to do this with math. It is fairly easy(albeit long) to find this using repeated derivatives or expansion, but it would be much harder to program that for me. I didn't quite understand the second and third answers, since I have never encountered that notation or those concepts in my math studies before. Could someone please explain how I could write a program to do this, or explain the solutions given on that page, for my own understanding of combinatorics?

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

EDIT: I'm looking for a mathematical way to solve this, that gives an exact theoretical number, not by simulating dice

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

采纳答案by mellamokb

The solution using the generating-function method with N(d, s)is probably the easiest to program. You can use recursion to model the problem nicely:

使用生成函数方法的解决方案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);
}

At first glance this seems like a fairly straightforward and efficient solution. However you will notice that many calculations of the same values of numDiceand summay be repeated and recalculated over and over, making this solution probably even less efficient than your original brute-force method. For example, in calculating all the counts for 3dice, my program ran the numPossibilitiesfunction a total of 15106times, as opposed to your loop which only takes 6^3 = 216executions.

乍一看，这似乎是一个相当简单有效的解决方案。然而，您会注意到许多相同值的numDice和sum可能会一遍又一遍地重复和重新计算，这使得该解决方案的效率可能比您原来的蛮力方法还要低。例如，在计算3骰子的所有计数时，我的程序numPossibilities总共运行了该函数15106，而不是您的循环只6^3 = 216执行一次。

To make this solution viable, you need to add one more technique - memoization (caching) of previously calculated results. Using a HashMapobject, for example, you can store combinations that have already been calculated and refer to those first before running the recursion. When I implemented a cache, the numPossibilitiesfunction only runs 151times total to calculate the results for 3dice.

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

The efficiency improvement grows larger as you increase the number of dice (results are based on simulation with my own implemented solution):

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

# 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

回答by arynaq

Check out Monte Carlo Methodsthey usually scale linearly with inputsize. In this case the example is easy, we assume that since once throw of the dice doesn't affect the other instead of counting combinations we can simply count the sum of the faces of dices thrown randomly (many times enough).

查看Monte Carlo 方法，它们通常与输入大小成线性关系。在这种情况下，示例很简单，我们假设因为一次掷骰子不会影响另一个，而不是计算组合，我们可以简单地计算随机掷出的骰子面的总和（多次就足够了）。

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

}

The error decreases with number of simulations but at the cost of cputime but the above values were pretty fast.

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

3 dice

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 dice

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}

回答by aromero

You don't need to brute force since your first roll determines what values can be used in the second roll, and both first and second roll determine the third roll. Let's take the tens example, suppose you roll a 6, so 10-6=4meaning you still need 4. For the second roll you need at least 3, because your third roll should at least count for 1. So the second roll goes from 1to 3. Suppose your second roll is 2, you have 10-6-2=2, meaning your third roll IS a 2, there is no other way.

您不需要蛮力，因为您的第一次掷骰决定了第二次掷骰中可以使用的值，而第一次掷骰和第二次掷骰都决定了第三次掷骰。让我们以十位为例，假设您掷出 a 6，这10-6=4意味着您仍然需要4. 你至少需要第二次掷骰子3，因为你的第三次掷骰子至少应该算数1。所以第二卷从1到3。假设你的第二卷是2，你有10-6-2=2，这意味着你的第三卷是 a 2，没有其他办法。

Pseudo code for tens:

十位的伪代码：

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++

Note that each loop adds 1, so at the end you know this code loops exactly 27 times.

请注意，每个循环加 1，所以最后您知道这段代码正好循环了 27 次。

Here is the Ruby code for all 18 values (sorry it's not Java, but it can be easily followed). Note the min and max, that determine what values can have each of the dice rolls.

这是所有 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

For a mathematical approach, take a look at https://math.stackexchange.com/questions/4632/how-can-i-algorithmically-count-the-number-of-ways-n-m-sided-dice-can-add-up-t

对于数学方法，请查看https://math.stackexchange.com/questions/4632/how-can-i-algorithmically-count-the-number-of-ways-nm-side-dice-can-add -up-t

回答by Ante

Mathematical description is just a 'trick' to make same counting. It uses polynomial to express dice, 1*x^6 + 1*x^5 + 1*x^4 + 1*x^3 + 1*x^2 + 1*xmeans that each value 1-6 is counted once, and it uses polynomial multiplication P_1*P_2for a counting of different combinations. That is done since coefficient at some exponent (k) is calculated by summing all coefficient in P_1and P_2which exponent sum to k.

数学描述只是进行相同计数的“技巧”。它使用多项式来表示骰子，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。

E.g. for two dices we have:

例如，对于两个骰子，我们有：

(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

Calculation by this method has same complexity as 'counting' one.

这种方法的计算与“计数”具有相同的复杂性。

Since function (x^6 + x^5 + x^4 + x^3 + x^2 + x)^nhas simpler expression (x(x-1)^6/(x-1))^n, it is possible to use derivation approach. (x(x-1)^6/(x-1))^nis a polynomial, and we are looking for coefficient at x^s(a_s). Free coefficient (at x^0) of s'thderivation is s! * a_k. So, s'thderivation in 0 is s! * a_k.

由于函数(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)s'th是s! * a_k。因此，s'th在 0 中的推导是s! * a_k。

So, we have to derive this function stimes. It can be done using derivation rules, but I think that it will have even worse complexity than counting approach since each derivation produces 'more complex' function. Here are first three derivations from Wolfram Alpha: first, secondand third.

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

In general, I prefer counting solution, and mellamokb gave nice approach and explanation.

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