Введение
На одном из собеседований по приёму на работу попросили за 30 минут написать программу, которая бы решал следующую задачу:
Есть n стандартных игральных костей (6-ти гранных кубиков) со стандартным обозначением всех граней от 1 до 6. Бросаем все n кубики разом. Нужно найти вероятность выпадения числа k, а именно суммы всех значений, выпавших на этих кубиках.
Решение
Не буду томить ожиданием и сразу выложу код алгоритма, который получился и впоследствии был немного обработан напильником.
Python
# -*- coding: utf-8 -*-
# import numpy # <можно_использовать_numpy>
def main():
c_int_side_dice: int = 6 # сколько граней у кубика
c_int_dice_number: int = 6 # кол-во кубиков
c_int_number_to_find: int = 18 # число, вероятность выпадения которого хотим найти
probability = dice_probability(c_int_dice_number, c_int_number_to_find, c_int_side_dice)
print(probability)
# собственно поиск вероятности определённого значения
def dice_probability(int_dice_number: int, int_number_to_find: int, c_int_side_dice: int) -> float:
list_values, list_interm_probability = list_values_and_interm_probabilities(int_dice_number, c_int_side_dice)
if int_number_to_find < list_values[0] or int_number_to_find > list_values[-1]:
# задаваемое число выходит за рамки реально возможного диапазона значений
result_out: float = 0.0
else:
for i in range(len(list_values)):
if list_values[i] == int_number_to_find:
result_out: float = list_interm_probability[i] / (c_int_side_dice ** int_dice_number)
break
return result_out
# возвращает списки/массивы: значения (сумма выпавших всех значений кубиков), сколько раз встречается значение
def list_values_and_interm_probabilities(int_dice_number: int, c_int_side_dice: int) -> tuple[list[int], list[int]]: # [кол-во кубиков], [сколько граней у кубика]
list_values = [i for i in range(int_dice_number, c_int_side_dice * int_dice_number + 1)] # <длина_списков_совпадает!>
list_interm_probability = [1] * c_int_side_dice # [1, 1, 1, 1, 1, 1]
for i in range(int_dice_number - 1):
list_interm_probability = multiply_by_ones(list_interm_probability, c_int_side_dice) # <длина_списков_совпадает!>
# list_interm_probability = numpy.convolve(list_interm_probability, [1] * c_int_side_dice) # <можно_использовать_numpy> и не использовать multiply_by_ones()
return list_values, list_interm_probability
# "умножение" на единицы
def multiply_by_ones(list_in: list[int], c_int_side_dice: int) -> list[int]: # [1, 1, 1, 1, 1, 1], 6
list_dummy: list[list[int]] = []
for i in range(c_int_side_dice):
list_dummy.append([0] * i) # [], [0], [0, 0], [0, 0, 0] ...
list_for_sum: list[list[int]] = []
for i in range(c_int_side_dice):
list_for_sum.append(list_dummy[i] + list_in + list_dummy[c_int_side_dice - i - 1])
"""
[list_in, 0, 0, 0, 0, 0]
[0, list_in, 0, 0, 0, 0]
[0, 0, list_in, 0, 0, 0]
[0, 0, 0, list_in, 0, 0]
[0, 0, 0, 0, list_in, 0]
[0, 0, 0, 0, 0, list_in]
"""
list_out: list[int] = []
for i in range(len(list_for_sum[0])):
sum_out: int = 0
for j in range(c_int_side_dice):
sum_out += list_for_sum[j][i]
list_out.append(sum_out)
"""
[1, 2, 3, 4, 5, 6, 5, 4, 3, 2, 1]
"""
return list_out
if __name__ == "__main__":
main()
JavaScript
function main(){
const c_int_side_dice = 6; // сколько граней у кубика
const c_int_dice_number = 6; // кол-во кубиков
const c_int_number_to_find = 18; // число, вероятность выпадения которого хотим найти
let probability = dice_probability(c_int_dice_number, c_int_number_to_find, c_int_side_dice);
console.log(probability);
}
// собственно поиск вероятности определённого значения
function dice_probability(int_dice_number, int_number_to_find, c_int_side_dice){
let lists_val_and_prob = list_values_and_interm_probabilities(int_dice_number, c_int_side_dice);
let result_out;
if (int_number_to_find < lists_val_and_prob[0][0] || int_number_to_find > lists_val_and_prob[0][lists_val_and_prob[0].length - 1]){
// задаваемое число выходит за рамки реально возможного диапазона значений
result_out = 0.0;
} else {
for (let i = 0; i < lists_val_and_prob[0].length; i++){
if (lists_val_and_prob[0][i] == int_number_to_find){
result_out = lists_val_and_prob[1][i] / Math.pow(c_int_side_dice, int_dice_number);
break;
}
}
}
return result_out;
}
// возвращает списки/массивы: значения (сумма выпавших всех значений кубиков), сколько раз встречается значение
function list_values_and_interm_probabilities(int_dice_number, c_int_side_dice){ // [кол-во кубиков], [сколько граней у кубика]
let list_values = new Array();
let i = 0;
for (let j = int_dice_number; j <= c_int_side_dice * int_dice_number; j++){
list_values[i] = j;
i++;
}
console.log(list_values);
let list_interm_probability = Array(c_int_side_dice).fill(1); // [1, 1, 1, 1, 1, 1]
for (let i = 0; i < int_dice_number - 1; i++){
list_interm_probability = multiply_by_ones(list_interm_probability, c_int_side_dice);
}
console.log(list_interm_probability);
return [list_values, list_interm_probability];
}
// "умножение" на единицы
function multiply_by_ones(list_in, c_int_side_dice){
let list_dummy = new Array(c_int_side_dice);
for (let j = 0; j < c_int_side_dice; j++){
list_dummy[j] = Array(j).fill(0);
}
let list_for_sum = new Array(c_int_side_dice);
for (let j = 0; j < c_int_side_dice; j++){
list_for_sum[j] = list_dummy[j].concat(list_in, list_dummy[c_int_side_dice - j - 1]);
}
// [list_in, 0, 0, 0, 0, 0]
// [0, list_in, 0, 0, 0, 0]
// [0, 0, list_in, 0, 0, 0]
// [0, 0, 0, list_in, 0, 0]
// [0, 0, 0, 0, list_in, 0]
// [0, 0, 0, 0, 0, list_in]
let list_out = new Array();
for (let i = 0; i < list_for_sum[0].length; i++){
let sum_out = 0;
for (let j = 0; j < c_int_side_dice; j++){
sum_out += list_for_sum[j][i];
}
list_out[i] = sum_out;
}
// [1, 2, 3, 4, 5, 6, 5, 4, 3, 2, 1]
return list_out;
}
main();VBScript
Option Explicit
Sub main()
Const c_int_side_dice = 6 'сколько граней у кубика
Const c_int_dice_number = 3 'кол-во кубиков
Const c_int_number_to_find = 10 'число, вероятность выпадения которого хотим найти
Dim probability
probability = dice_probability(c_int_dice_number, c_int_number_to_find, c_int_side_dice)
MsgBox probability
End Sub
'собственно поиск вероятности определённого значения
Function dice_probability(int_dice_number, int_number_to_find, c_int_side_dice)
Dim list_values()
Dim list_interm_probability()
list_values_and_interm_probabilities int_dice_number, c_int_side_dice, list_values, list_interm_probability
Dim result_out
Dim i
If int_number_to_find < list_values(0) Or int_number_to_find > list_values(UBound(list_values)) Then
'задаваемое число выходит за рамки реально возможного диапазона значений
result_out = 0.0
Else
For i = 0 To UBound(list_values)
If list_values(i) = int_number_to_find Then
result_out = list_interm_probability(i) / (c_int_side_dice ^ int_dice_number)
End If
Next
End If
dice_probability = result_out
End Function
'возвращает списки/массивы: значения (сумма выпавших всех значений кубиков), сколько раз встречается значение
Sub list_values_and_interm_probabilities(int_dice_number, c_int_side_dice, list_values, list_interm_probability) '[кол-во кубиков], [сколько граней у кубика]
ReDim list_values(int_dice_number * (c_int_side_dice - 1))
Dim i, j
i = 0
For j = int_dice_number To c_int_side_dice * int_dice_number
list_values(i) = j
i = i + 1
Next
ReDim list_interm_probability(c_int_side_dice - 1)
For j = 0 To c_int_side_dice - 1
list_interm_probability(j) = 1
Next
For j = 0 To int_dice_number - 2
multiply_by_ones list_interm_probability, c_int_side_dice
Next
End Sub
'"умножение" на единицы
Sub multiply_by_ones(list_in, c_int_side_dice)
Dim list_in_length
list_in_length = UBound(list_in)
Dim list_for_sum()
ReDim list_for_sum(c_int_side_dice - 1, list_in_length + c_int_side_dice - 1)
Dim i, j, k, n
For i = 0 To c_int_side_dice - 1
j = 0
For n = 0 To c_int_side_dice - 1
If i = n Then
For k = 0 To list_in_length
list_for_sum(i, j) = list_in(k)
j = j + 1
Next
Else
list_for_sum(i, j) = 0
j = j + 1
End If
Next
Next
' [list_in, 0, 0, 0, 0, 0]
' [0, list_in, 0, 0, 0, 0]
' [0, 0, list_in, 0, 0, 0]
' [0, 0, 0, list_in, 0, 0]
' [0, 0, 0, 0, list_in, 0]
' [0, 0, 0, 0, 0, list_in]
' ArrOut_2 list_for_sum
Erase list_in
ReDim list_in(list_in_length + c_int_side_dice - 1)
Dim sum_out
For j = 0 To list_in_length + c_int_side_dice - 1
sum_out = 0
For i = 0 To c_int_side_dice - 1
sum_out = sum_out + list_for_sum(i, j)
Next
list_in(j) = sum_out
Next
' [1, 2, 3, 4, 5, 6, 5, 4, 3, 2, 1]
' ArrOut_1 list_in
End Sub
'==================================================
'<Additional_MsgBox_For_Arrays>
Sub ArrOut_1(arr_in)
Dim str_out
Dim i
For i = 0 To UBound(arr_in)
If i = 0 Then
str_out = arr_in(i)
Else
str_out = str_out & " " & arr_in(i)
End If
Next
MsgBox str_out
End Sub
Sub ArrOut_2(arr_in)
Dim str_out
Dim i, j
For i = 0 To UBound(arr_in, 1)
For j = 0 To UBound(arr_in, 2)
If i = 0 And j = 0 Then
str_out = arr_in(i, j)
ElseIf j = 0 Then
str_out = str_out & vbNewLine & arr_in(i, j)
Else
str_out = str_out & " " & arr_in(i, j)
End If
Next
Next
MsgBox str_out
End Sub
'</Additional_MsgBox_For_Arrays>
'==================================================
mainПояснение
Понятно, что копание в чужом коде — дело не благодарное, опишу работу алгоритма для одного конкретного примера.
Картинку можно описать словами как: нахождение делимого вероятности выпадения при помощи многократной свёртки последовательности [1 1 1 1 1 1] на саму себя. Количество операций свёртки совпадает с количеством кубиков минус 1.
Смею предположить, что дочитав до этого момента у многих читателей уже зародятся скептические настроения, однако в свою очередь предложу поверить самостоятельно и в помощь приложу SQL запрос, который считает «в лоб», т.е. генерирует все возможные комбинации выпадения для 3-х кубиков, а потом пересчитывает все выпавшие суммы. В результате отработки скрипта мы получим 2 столбца из самого конца пункта “Этап I. Генерация 2-х списков/массивов: Значения (сумма выпавших костей) И Сколько раз встречается значение”.
SQL запрос - генератор решения "в лоб"
-- заводим значения сторон кубика
WITH step_01_insert (dice) AS (
SELECT 1 AS dice UNION ALL
SELECT 2 AS dice UNION ALL
SELECT 3 AS dice UNION ALL
SELECT 4 AS dice UNION ALL
SELECT 5 AS dice UNION ALL
SELECT 6 AS dice
)
-- генерируем все возможные ситуации для 3-х кубиков
, step_02_spawn (dice_1, dice_2, dice_3, dice_sum) AS (
SELECT T1.dice AS dice_1
, T2.dice AS dice_2
, T3.dice AS dice_3
, T1.dice + T2.dice + T3.dice AS dice_sum -- Значения (сумма выпавших костей)
FROM step_01_insert AS T1
, step_01_insert AS T2
, step_01_insert AS T3
)
-- считаем в лоб, сколько раз встречается значение
SELECT dice_sum -- Значения (сумма выпавших костей)
, COUNT(1) AS num -- Сколько раз встречается значение
FROM step_02_spawn
GROUP BY dice_sum
ORDER BY dice_sum;dice_sum | num |
3 | 1 |
4 | 3 |
5 | 6 |
6 | 10 |
7 | 15 |
8 | 21 |
9 | 25 |
10 | 27 |
11 | 27 |
12 | 25 |
13 | 21 |
14 | 15 |
15 | 10 |
16 | 6 |
17 | 3 |
18 | 1 |
Конечно это не достаточно для полноценного доказательства, о котором я расскажу чуть позже, но хоть накал скепсиса, надеюсь, мне удалось сбавить.
Отмечу, что я не претендую на какую-то оригинальность, т.к. подобный алгоритм упоминается в данных статьях: "How to Calculate Multiple Dice Probabilities" Method 2 Recursion, "Как посчитать вероятность определенной комбинации при игре в кости" Метод 2 Рекурсия (перевод).
Пусть вас не смущает хитрое смещение суммирования в формуле Excel – суть от этого никак не меняется. Явно именно раздел «Метод 2» затачивался под Excel реализацию, но запрограммировать данный алгоритм в лоб без изменений именно на каком-либо языке программирования — задача не тривиальная.
Но всё-таки, почему этот алгоритм работает?
Для начала вспомним треугольник Паскаля:
Из всего множества его замечательных свойств я бы хотел заострить внимание на следующем: до строки:
цифры в треугольнике Паскаля повторяют степени числа 11 в степени 1<=k<=4 (натуральное). Но это утверждение верно для десятичной системы счисления, однако, если считать степень числа 11 в шестнадцатеричной системе счисления, то можно продлить совпадения до 1<=k<=5.
Можно задаться вопросом: а на каком калькуляторе можно 11 возводить в степень 5 в шестнадцатеричной системе счисления? Ответ: воспользуемся свойством
Иначе говоря идём итерационно:
121=11 * 11
1331=121 * 11
14641=1331 * 11
15AA51=14641 * 11
Давайте чуть здесь остановимся и вспомним школьную программу, а именно умножение в столбик, с одной лишь оговоркой, что перенос числа из одного разряда в другой (при переполнении разряда) буду делать отдельной операцией, а так же визуально для каждого разряда выделю отдельный столбец.
Пример 1.
14641 * 11 в десятеричной системе счисления.
Заполняем условия.
Записываем результаты умножения каждой единицы разряда.
Суммируем.
Переводим из переполнившихся разрядов в разряды выше.
Проделаем ту же операцию в шестнадцатеричной системе счисления (Шестнадцатеричная система счисления)
Пример 2.
Заполняем условия.
Записываем результаты умножения каждой единицы разряда.
Суммируем.
Записываем полученные числа правильно в шестнадцатеричной системе счисления.
И для закрепления ещё один.
Пример 3.
15AA51 * 11 в шестнадцатеричной системе счисления.
Заполняем условия в шестнадцатеричной системе счисления.
Переводим запись из шестнадцатеричной в десятичную систему счисления для улучшения восприятия (благо мы можем себе это позволить, т.к. визуально отделяем каждый разряд друг от друга).
Записываем результаты умножения каждой единицы разряда.
Суммируем.
Переводим поэтапно из переполнившихся разрядов в разряды выше.
Записываем полученные числа правильно в шестнадцатеричной системе счисления.
Во всех приведённых примерах я бы акцентировал внимание на пунктах «Суммируем» (Пример 1 - п3., Пример 2 - п3., Пример 3 - п4.), которые «цитируют» одну из строк треугольника Паскаля. Если продолжить мысль, то манипуляции с разрядами мешают нормальному воспроизведению всего треугольника. А давайте от них избавимся? Т.е. условно говоря будем считать (да простят меня математики) в «условно бесконечной системе счисления» (вероятно есть и более адекватный термин, но увы, беглый запрос по интернету ничего не дал, что больше доказывает мою лень, а не на отсутствие информации как таковой), т.е. когда перехода из одного разряда в другой при операции сложения не происходит. И это работает:
Тут я не претендую опять же на оригинальность, данный метод есть и им пользуются: как вывести треугольник Паскаля на Python? (см. «Простейшая реализация»)
Аналогия с умножением в столбик двух чисел в очень большой системой счисления, в принципе, имеет право на существование и даёт представление об операции, однако стоит грамотнее назвать её свёрткой последовательности. В данном посте приводится как раз выведение "строк" треугольника Паскаля сверткой: дискретная свёртка или полиномиальное умножение
Вернёмся к кубикам.
Посчитаем в лоб сколько раз встречается сумма костей для всех возможных случаев.
1 кубик (тут всё просто).
2 кубика (идём по классике жанра).
Тут конечно можно посчитать вручную, т.е. просуммировать все единицы в правой таблице, соответствующие полученным значениям в левой таблице (лучше визуализировать):
Однако, заметим смещение "Полученных значений" в левой таблице и преобразуем обе таблицы следующим образом:
После этого в правой таблице нам останется лишь просуммировать строки. Опять же тут немного остановимся на правой табличке, и заметим, что она напоминает уже упомянутое выше умножение столбик в десятичной системе счисления (или свёртку последовательностей).
В итоге получим:
Проделаем аналогичные шаги для 3-х кубиков:
Смещаем:
Акцентируем внимание, что опять же правая таблица напоминает умножение в столбик в «условно бесконечной системе счисления» (или свёртку последовательностей):
Выводим результат:
Описанные операции итерационно можно продолжать сколь угодно долго.
Данный алгоритм походит для любого числа одинаковых игровых кубиков с любым количеством граней, у которых числа на гранях входят в арифметическую последовательность. И его при некотором желании можно даже модифицировать и для решения задач, когда речь идёт не об однотипных кубиках а с разным количеством граней (правда я ума не приложу кому это может понадобиться).
Итого, выводы
Задачи на поиск вероятности выпадения числа k у n игральных кубиков попадаются на собеседованиях.
В данной статье рассмотрен довольно элегантный алгоритм по решению подобных задач, указанных выше. В принципе можно решать подобные задачи просто на листе бумаге.
О чём стоит упомянуть
Представленный алгоритм не является самым оптимальным. Например для 1000 кубиков (не знаю кому это будет нужно, но вдруг) придётся просчитать для всех элементов последовательности 1000 раз. Но можно ещё поиграться с умножением в столбик в «условно ...» и снизить вычислительную сложность алгоритма с O(n^2) ("Оценка сложности алгоритмов, или Что такое О(log n)").
Updated: 23.08.2022
