计算可能组合的数量以达到与模具的总和 [英] Counting number of possible combination to reach a sum with a die

问题描述

假设您需要n步(例如100步)才能回到专卖"的起点，再次滚动模具以达到起始点的数量.

Assume you need n steps (e.g. 100) to visit back to the start point on Monopoly, how many combination of rolling a die to reach start point again.

最小投掷次数取整(n/6)，最大投掷次数为n(投掷1代表n次).

The min throw count is round up (n/6), max is n (throwing 1 for n times).

n可能大于10000.但是除了蛮力之外，我想不出更好的解决方法.

n might be greater than 10000. But I can't think of any better solution other than brute force.

推荐答案

这取决于顺序是否重要.

It depends if the order matters or not.

可以说不是.那是，抛出1、2、3与抛出3、2、1相同.在这种情况下，此Scala代码片段应该可以正常工作.

Let's say it doesn't. That is, throwing 1, 2, 3 is the same as throwing 3, 2, 1. In this case this Scala snippet should work just fine.

  def count(n: Int): Int = {
    def count(n: Int, dots: List[Int]): Int = dots match {
      case _ if n == 0 => 1
      case h :: t if n > 0 => count (n - h, h :: t) + count (n, t)
      case _ => 0
    }
    count(n, List(1, 2, 3, 4, 5, 6))
  }

如果顺序很重要，那么这将是解决方案.

If the order matters than this would be the solution.

import java.math.BigInteger;
import java.util.LinkedList;

public class HexabonacciSolver {

    public BigInteger solve(int n) {
        LinkedList<BigInteger> lastSix = new LinkedList<>();
        lastSix.add(new BigInteger("1"));
        lastSix.add(new BigInteger("2"));
        lastSix.add(new BigInteger("4"));
        lastSix.add(new BigInteger("8"));
        lastSix.add(new BigInteger("16"));
        lastSix.add(new BigInteger("32"));
        if (n < 7)
            return lastSix.get(n - 1);
        for (int i = 0; i < n - 6; i++){
            lastSix.add(lastSix.get(0).add(lastSix.get(1).add(lastSix.get(2).add(lastSix.get(3).add(lastSix.get(4).add(lastSix.get(5)))))));
            lastSix.removeFirst();
        }
        return lastSix.get(5);
    }

}

说明:它如何工作?

比方说，您想知道要进入大富翁"领域100的骰子掷骰有多少个不同序列.您知道要到达那里，以前的掷骰必须是6、5、4、3、2或1.如果您只有到达94、95、96、97，在98、99中，您可以将它们总结起来并获得字段100的解决方案.这正是程序的工作.这与斐波那契数列的构建方式非常相似，不同之处在于该序列中的下一个数字是通过将6个先前的数字相加而得出的(因此名称为"Hexabonacci")

Let's say you want to know how many different sequences of dice rolls there are to get into the field 100 in Monopoly. You know that to get there the previous rolls had to be either 6, 5, 4, 3, 2 or 1. If you only had the number of different sequences of rolls needed to arrive to the fields 94, 95, 96, 97, 98, 99 you could just sum them up and get the solution for the field 100. This is exactly what the program does. This is very analogous to how the Fibonacci sequence is build with the difference that the next number in the sequence is calculated by summing up 6 previous numbers (hence the name "Hexabonacci")

该解决方案在时间上是线性的 O(N)，而在空间上的常数是O(C)，因为我们只需要存储 Hexabonacci 序列的最后6个数字.由于n = 10000的结果有数百个数字，因此Java解决方案将返回BigInteger.

The solution is linear O(N) in time and constant O(C) in space as we only need to store 6 last numbers of the Hexabonacci sequence. Since the result for n=10000 has hundreds of digits the Java solution returns a BigInteger.

让我知道您是否想在Scala/Python/JavaScript中看到一个解决方案.

Let me know if you'd like to see a solution in Scala/Python/JavaScript.

这篇关于计算可能组合的数量以达到与模具的总和的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！