2

Дано число шестигранных кубиков - N. В следующем рядочке 2 числа - диапазон (left,right). Как найти вероятность того что при бросании N кубиков сумма очков будет в диапазоне (left,right)?

Ограничения:

 N = 100
 left, right <= 600

Примерчики :)

 1
 1 3

 2
 11 12

Ответы:

 0.5

 0.083

Объяснение: 1) Возможные числа что выпадут - 1, 2, 3 , а всех (6**N = 6).

Итог: вероятность - 3 / (6**N = 6) = 0.5.

2) Возможные числа что выпадут - (5 + 6), (6 + 5), (6 + 6).

Итог: вероятность - 3 / (6**N = 36) = 3 / 36 = 0,083.

Я пытался решить задачку алгоритмически,найти все перестановки длины N в массиве (1,2,3,4,5,6), ну и тогда проверять что сумма находится в диапазоне (left,right).

Код:

from itertools import product
n = int(input())
a,b = map(int,input().split())
arr = ["1","2","3","4","5","6"]
res = ["".join(i) for i in product(arr, repeat = n)]
k = 0
for i in range(0,len(res)):
    string = res[i]
    s = 0
    for j in range(0,n):
        s+=int(string[j])
    if s>=a and s<=b:
        k+=1
print(k / (6**n))
2
  • ну что вы написали имеет сложность что-то около 6^N а можно за 6*N*N. Это делается через дп. Пересчёт F[i][k+j] = F[i-1][k] | i in [1,N] j in [1,6] k in 1..R.
    – pavel
    5 дек 2018 в 17:40
  • Pavel,обьясните что к чему бо не особо понимаю (
    – GGO
    5 дек 2018 в 19:00

2 ответа 2

3

Вероятность попадания в диапазон равна сумме вероятностей выпадения каждого дискретного значения из диапазона.

Вероятность выпадения каждого дискретного значения суммы S равно отношению количества способов набрать такую сумму к количеству всевозможных исходов. Последнее равно 6N.

А количество способов набрать сумму S равно

    Cумма для i от 0 до [(S-N)/6] слагаемых вида (-1)i CiN CN-1S-6i-1

Вычислить эту величину можно и "вручную": методом включения-исключения (как это делается я подробно расписывал здесь) или через генерирующие функции. Выше приведена уже готовая формула.

Например, для задачи 2 11 12 находим количество способов выбрасывания сумм 11 и 12, которых, по вышеприведенной формуле, 2 и 1 соответственно. Тогда вероятность равна (1 + 2) / 36 = 0.08(3).

1

Слишком длинно для комментария - пояснение толстого намёка @pavel

Создаёте таблицу Nx6N и заполняете её ряд за рядом.

Что в ячейке A[K][P]? количество вариантов набрать сумму P при бросании K кубиков.

Сумму P при использовании K кубиков можно получить при выпадении одного очка на K-м кубике и сумме P-1 на K-1 кубиках.

Эту же сумму можно получить при выпадении двух очков на K-м кубике и сумме P-2 на K-1 кубиках.

и т.д. до 6 очков.

    1  2  3  4  5  6  7  8  9  10  11  12
1   1  1  1  1  1  1  0  0  0  0   0   0
2   0  1  2  3  4  5  6  5  4  3   2   1

Простая реализация на Delphi:

function SumProb(n, a, b: Integer): Double;
var
  Table: array of array of Int64;
  i, j, k: integer;
begin
  SetLength(Table, n + 1, 6 * n + 1);
  for i := 1 to 6 do
    Table[1, i] := 1;
  for i := 2 to n do
     for j := i to 6 * i do
       for k := Min(6, j) downto 1 do
          if j - k > 0 then
             Table[i, j] := Table[i, j] + Table[i - 1, j - k];
  Result := 0;
  for i := a to b do
    Result := Result + Table[n, i];
  for i := 1 to n do
    Result := Result / 6;
end;
15
  • MBo,если вам не сложно накидать какой то псевдокод,вам не сложно - а мне приятно :)
    – GGO
    5 дек 2018 в 19:50
  • У меня ночь глубокая, уж постарайтесь разобраться на примере двух и трех кубиков
    – MBo
    5 дек 2018 в 19:52
  • Ну окей,я то понимаю но где начальные значения брать то,ну мне не горит :)
    – GGO
    5 дек 2018 в 19:54
  • шесть единиц для одного кубика, остальные нули.
    – MBo
    5 дек 2018 в 19:56
  • У меня на текстувалке идёт неверный ответ,но почему я не понимаю,все зделал как вы сказали :(
    – GGO
    6 дек 2018 в 16:40

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.