Комбинаторическая головоломка с подсчетом: бросьте 20 8-гранных кубиков, какова вероятность получить хотя бы 5 кубиков одинакового достоинства.

Двойной учет может быть решен с помощью принципа включения / исключения

Я подозреваю, что это связано с:

Choose(8,1)*P(one set of 5 Xs) 
- Choose(8,2)*P(a set of 5 Xs and a set of 5 Ys) 
+ Choose(8,3)*P(5 Xs, 5 Ys, 5 Zs) 
- Choose(8,4)*P(5 Xs, 5 Ys, 5 Zs, 5 As)

P(set of 5 Xs) = 20 Choose 5 * 7^15 / 8^20
P(5 Xs, 5 Ys) = 20 Choose 5,5 * 6^10 / 8^20

И так далее. Это не решает напрямую проблему «более 5 одинаковых», как если бы вы просто суммировали результаты, примененные к 5,6,7..20; вы бы переоценили случаи, когда у вас, скажем, 10 единиц и 5 восьмерок.

Вероятно, вы могли бы снова применить исключение включения, чтобы получить второй ответ; Итак, P (не менее 5) = P (один набор из 20) + ... + (P (один набор из 15) - 7 * P (набор из 5 из 5 кубиков)) + ((P (один набор из 14) - 7 * P (один набор из 5 из 6) - 7 * P (один набор из 6 из 6)). Придумывать исходный код для этого оказывается труднее.

Я предлагаю вам потратить немного времени на написание моделирования Монте-Карло и дать ему поработать, пока вы занимаетесь математикой вручную. Надеюсь, моделирование Монте-Карло сойдется до того, как вы закончите с математикой, и вы сможете проверить свое решение.

Чуть более быстрый вариант может включать создание SO-клона для математических вопросов.

Точное распределение вероятностей Fs, i суммы i s-сторонних игральных костей может быть вычислено как повторная свертка распределения вероятностей одиночных игральных костей с самим собой.

где для всех и 0 в противном случае.

http://en.wikipedia.org/wiki/Dice

Эта проблема действительно сложна, если вам нужно ее обобщить (получить точную формулу).

Но в любом случае позвольте мне объяснить алгоритм. Если вы хотите знать

количество способов получить ровно 5 кубиков одного достоинства

вам нужно перефразировать вашу предыдущую проблему, как

подсчитайте количество способов получить ровно 5 кубиков значения 3 И никакое другое значение не может быть повторено ровно 5 раз

Для простоты назовем функцию F (20,8,5) (5 кубиков, все значения) первым ответом, а F (20,8,5,3) (5 кубиков, значение 3) - вторым. У нас есть, что F (20,8,5) = F (20,8,5,3) * 8 + (события, когда более одного значения повторяются 5 раз)

Итак, если мы можем получить F (20,8,5,3), это должно быть довольно просто, не так ли? Ну ... не очень ...

Во-первых, давайте определим некоторые переменные: X1, X2, X3 ..., Xi, где Xi = количество раз, когда мы получаем кубик i

Потом:

F(20,8,5)/20^8 = P(X1=5 or X2=5 or ... or X8=5, with R=20(rolls) and N=8(dice number))

, P (утверждение) - стандартный способ записи вероятности.

мы продолжаем:

F(20,8,5,3)/20^8 = P(X3=5 and X1<>5 and ... and X8<>5, R=20, N=8) 
F(20,8,5,3)/20^8 = 1 - P(X1=5 or X2=5 or X4=5 or X5=5 or X6=5 or X7=5 or X8=5, R=15, N=7)  
F(20,8,5,3)/20^8 = 1 - F(15,7,5)/7^15

рекурсивно:

F(15,8,5) = F(15,7,5,1) * 7  
P(X1=5 or X2=5 or X4=5 or X5=5 or X6=5 or X7=5 or X8=5, R=15, N=7) = P(X1=5 and X2<>5 and X4<>5 and .. and X8<>5. R=15, N=7) * 7

F(15,7,5,1)/7^15 = 1 - F(10,6,5)/6^10 F(10,6,5) = F(10,6,5,2) * 6

F(10,6,5,2)/6^10 = 1 - F(5,5,5)/5^5
F(5,5,5) = F(5,5,5,4) * 5

Что ж, тогда ... F (5,5,5,4) - это количество способов получить 5 кубиков номиналом 4 за 5 бросков, например, никакие другие кубики не повторяются 5 раз. Есть только 1 способ из 5 ^ 5. Тогда вероятность равна 1/5 ^ 5.

F (5,5,5) - это количество способов получить 5 кубиков любого достоинства (из 5 значений) за 5 бросков. Очевидно, 5. Тогда вероятность равна 5/5 ^ 5 = 1/5 ^ 4.

F (10,6,5,2) - это количество способов получить 5 кубиков достоинством 2 за 10 бросков, например, никакие другие кубики не повторяются 5 раз. F (10,6,5,2) = (1-F (5,5,5) / 5 ^ 5) * 6 ^ 10 = (1-1 / 5 ^ 4) * 6 ^ 10

Что ж ... Я думаю, что это может быть в какой-то мере неверно, но в любом случае, вы поняли. Надеюсь, мне удалось сделать алгоритм понятным.

edit: Я провел несколько проверок и понял, что вам нужно добавить несколько случаев, когда вы получаете более одного значения, повторяющегося ровно 5 раз. У тебя нет времени решать эту часть ...

Вот о чем я думаю ...

Если бы у вас было всего 5 кубиков, у вас было бы только восемь способов получить желаемое.

Для каждого из этих восьми способов работают все возможные комбинации остальных 15 кубиков.

Итак - я думаю, что ответ: (8 * 8 15) / 8 20

(Ответ минимум на 5 одинаковый.)

Я считаю, что вы можете использовать формулу x вхождений в n событиях как:

P = вероятность ^ n * (n! / ((N - x)! X!))

Таким образом, окончательный результат будет суммой результатов от 0 до n.

Я действительно не вижу простого способа объединить это в один шаг, который был бы менее беспорядочным. Таким образом, формула также будет прописана в коде. Однако вам, возможно, придется написать свой собственный факторный метод.

  float calculateProbability(int tosses, int atLeastNumber) {
    float atLeastProbability = 0;
    float eventProbability = Math.pow( 1.0/8.0, tosses);
    int nFactorial = factorial(tosses);

    for ( i = 1; i <= atLeastNumber; i++) {
      atLeastProbability += eventProbability * (nFactorial / (factorial(tosses - i) * factorial(i) );
    }
  }

Рекурсивное решение:

Prob_same_value(n) = Prob_same_value(n-1) * (1 - Prob_noone_rolling_that_value(N-(n-1)))