Вычислить количество способов катания определенного числа

Ответ 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);
}

На первый взгляд это кажется довольно простым и эффективным решением. Однако вы заметите, что многие вычисления тех же значений numDice и sum могут повторяться и повторяться снова и снова, что делает это решение, вероятно, даже менее эффективным, чем ваш исходный метод грубой силы. Например, при вычислении всех счетчиков для 3 dice моя программа выполняла функцию numPossibilities в общей сложности 15106 раз, в отличие от вашего цикла, который принимает только 6^3 = 216 исполнения.

Чтобы сделать это решение жизнеспособным, вам нужно добавить еще один метод - memoization (кэширование) ранее рассчитанных результатов. Например, с помощью объекта 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

Ответ 2

Вам не нужно использовать команду перебора, так как ваш первый бросок определяет, какие значения можно использовать во втором рулоне, и как первый, так и второй ролик определяют третий бросок. Возьмем пример десятков, предположим, что вы катите 6, поэтому 10-6=4 означает, что вам все еще нужно 4. Для второго броска вам потребуется как минимум 3, потому что ваш третий бросок должен, по крайней мере, рассчитывать на 1. Таким образом, второй рулон идет от 1 до 3. Предположим, что ваш второй бросок 2, у вас есть 10-6-2=2, что означает, что ваш третий рулон IS 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 раз.

Вот код Ruby для всех 18 значений (извините, это не Java, но это можно легко выполнить). Обратите внимание на min и max, которые определяют, какие значения могут иметь каждый из рулонов кости.

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

Ответ 3

Математическое описание - всего лишь "трюк", чтобы сделать тот же подсчет. Он использует полином для выражения кубиков, 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). Свободный коэффициент (при x^0) вывода s'th равен s! * a_k. Таким образом, вывод s'th в 0 равен s! * a_k.

Итак, мы должны получить эту функцию s раз. Это можно сделать с помощью правил деривации, но я думаю, что он будет иметь еще худшую сложность, чем подсчет, поскольку каждый вывод создает "более сложную" функцию. Вот первые три вывода из Wolfram Alpha: сначала, second и третий.

В общем, я предпочитаю считать решение, и mellamokb дал хороший подход и объяснение.

Ответ 4

Отъезд Методы Монте-Карло, они обычно масштабируются линейно с вводом. В этом случае пример прост, мы предполагаем, что, поскольку бросок кубика не влияет на другой, а не на подсчет комбинаций, мы можем просто подсчитать сумму граней, брошенных случайным образом (много раз).

   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}