计算的方法的数量滚动一定数量 [英] Calculate the number of ways to roll a certain number

问题描述

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

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?

在计算机计算所有可能的方式三个骰子可   抛出：1 + 1 + 1，1 + 1 + 2，1 + 1 + 3等加起来每个这些   的可能性，看看有多少给九如的结果，有多少   给十位。如果有更多的给十，那么信仰被证明。

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.

我很快就摸索出蛮力的解决方案，因为这样

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

这工作得很好，和一身蛮力的解决方案是什么，老师要我们做的。但是，它不适合，我想找到一种方法，使一个算法，可以计算方式推出 N 骰子获得一个特定的数目。因此，我开始产生办法让每个总和与 N 的骰子的数量。用1模具，对于各明显1溶液。然后，我计算出，通过强力的组合，带2和3骰子。这些都为2：

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 n dice to get a specific number. Therefore, I started generating the number of ways to get each sum with n dice. 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:

有1的方式来滚2
有2种方式推出3
  有3种方式推出4
有4种方式推出5
  有5种方法来滚6
有6个方面推出7
  有5种方法来滚8
有4种方式推出9
  有3种方式推出10
有2种方式推出一个11
  有1的方式推出12

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

这看起来很简单;它可以计算出一个简单的线性绝对值函数。但接下来的事情开始变得棘手。随着3：

Which looks straightforward enough; it can be calculated with a simple linear absolute value function. But then things start getting trickier. With 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个方面推出16
  有3种方式推出了17
有1的方式推出18

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

所以，我看那个，我想：酷，三角号！不过，后来我发现那些讨厌的25S和27S。因此，这显然不是三角形的数字，但还是有些多项式展开，因为它是对称的。
所以，我把谷歌，而我遇到<一href="http://math.stackexchange.com/questions/68045/rolling-dice-such-that-they-add-up-to-13-is-there-a-more-elegant-way-to-solve">this 该页面进入一些细节有关如何使用数学做到这一点。这是很容易（虽然长），采用重复衍生物或扩建找到这一点，但它会更难编写了我。我没太明白，第二和第三个答案，因为我以前从来没有遇到过的符号或这些概念在我的数学研究。可能有人请解释如何我可以写一个程序来做到这一点，或解释为我自己的理解组合数学在该网页上给出的解决方案？

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 page that 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?

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

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

推荐答案

使用生成函数方法与解决方案 N（D，S）可能是最容易程序。您可以使用递归的问题很好的模型：

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:

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 的相同的价值观和许多计算之可重复和重新计算一遍又一遍，使这个解决方案很可能还要少效率比原来的穷举法。例如，在计算所有计数 3 骰子，我的程序运行 numPossibilities 函数共 15106 倍，而不是你的循环只需要 6 ^ 3 = 216 执行。

At first glance this seems like a fairly straightforward and efficient solution. However you will notice that many calculations of the same values of numDice and sum may 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 3 dice, my program ran the numPossibilities function a total of 15106 times, as opposed to your loop which only takes 6^3 = 216 executions.

为使这种解决方案可行，则需要添加更多的技术 - $ P $的记忆化（缓存）pviously计算结果。使用的HashMap 的对象，例如，可以存储已经计算出的组合，是指那些先运行递归之前。当我实现了一个缓存， numPossibilities 函数只运行 151 次总计算结果 3 骰子。

To make this solution viable, you need to add one more technique - memoization (caching) of previously calculated results. Using a HashMap object, 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 numPossibilities function only runs 151 times total to calculate the results for 3 dice.

在提高效率变大，你增加的骰子的数量（结果是基于仿真我自己的实施解决方案）：

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

这篇关于计算的方法的数量滚动一定数量的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！