How to become an author
Search
Write a publication
Pull to refresh

Comments 30

По факту конкретный математический пример решается даже без привлечения терминологии и обозначений теории вероятности. Есть вероятность благоприятного исхода, которая зависит от количества кубиков. Есть количество благоприятных исходов. Произведение этих величин - это и есть искомая вероятность.

Но здесь, я так понял, задача состоит именно в том, чтобы написать алгоритм, который будет автоматически рассчитывать вероятность выпадения произвольной суммы с произвольным количеством кубиков?

This comment wasn’t rated yet0

Давайте посмотрим на исходную задачу "в лоб". Переформулируем ее в необходимость найти f(n, k) - функцию, которая вычисляет количество вариантов получить число n при броске k кубиков.

Пограничные случаи: если n < k или n > 6k, то значение 0.

Если k = 1, то результат 1 (все, кроме чисел от 1 до 6 отсечено выше, а эти числа можно получить только одним образом каждое).

И общий случай: пусть на первом кубике выпало 1, тогда нужно посмотреть сколькими способами можно получить n-1 броском k-1 кубика, если выпало 2, то сколько способов для n-2 те ми же k-1 кубиками. В общем f(n-1, k-1)+f(n-2, k-1)+f(n-3, k-1)+f(n-4, k-1)+f(n-5, k-1)+f(n-6, k-1).

Итого:

int f(int n, int k)
{
    if (n < k)
        return 0;
    if (n > 6*k)
        return 0;
    if (k == 1)
        return 1;
    return f(n-1, k-1)+f(n-2, k-1)+f(n-3, k-1)+f(n-4, k-1)+f(n-5, k-1)+f(n-6, k-1);
}

Добавляем сверху кэширование результатов, чтобы не вычислять уже вычисленное и готово.

Смотрим на ваш способ и видим, что он по сути такой же:

Вот как раз визуальная иллюстрация: для трех кубиков считаем количества сумм брошенных двумя кубиками со сдвигом.

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

Total votes 3: ↑3 and ↓0+3

Думаю, можно было бы воспользоваться разбиением чисел.
То есть мы берем 18 и пытаемся представить его как сумму шести чисел от 1 до 6.
Например, таким образом:

```python

def partition(n,k,l,m):
if k < 1:
return
if k == 1:
if n <= m and n>=l :
yield (n,)
return
for i in range(l,m+1):
for result in partition(n-i,k-1,i,m):
yield result+(i,)

x = list(partition(18 ,6, 1, 6 ))
print('x',x)

```

И потом для каждого полученного разложения найти количество перестановок -- это даст нам число всех благоприятных исходов.

Total votes 1: ↑0 and ↓1-1

Немного режет глаз слово "possibility". Всё же оно переводится как возможность, а вероятность - probability.

Total votes 2: ↑2 and ↓0+2

Упс, согласен, не усмотрел, спасибо!

По возможности заменю во всех скриптах программ с "possibility" на "probability"

This comment wasn’t rated yet0

Исправлено, ещё раз спасибо!

This comment wasn’t rated yet0

Ровно тот же результат при решении еще более "в лоб":

n=3
d = 6
s=d ** n
ps = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

for d1 in range(1, d+1):
    for d2 in range(1, d+1):
        for d3 in range(1, d+1):
            ps[d1+d2+d3] += 1
print(s)
print(ps)
print(ps[11]/s*100)

Total votes 1: ↑1 and ↓0+1
n = 3
dn = 6
s = dn ** n
ps = [0] * (n * dn + 1)
f = 11


def func(level, current):
    for d in range(1, dn+1):
        if level == 1:
            ps[current+d] += 1
        else:
            func(level-1, current+d)


func(n, 0)
print(s)
print(ps)
print(ps[f]/s*100)

чтобы n можно было указывать достаточно в рекурсию обернуть

This comment wasn’t rated yet0

Что интересно, эту задачу можно решить намного оптимальнее, чем предложено как в статье, так и в других комментариях (я не нашёл чего-то существенно лучше O(n^2)): например, за O(n \log^2 n).

Для формальности пусть наш кубик будет не обычный игральный, а с числами 1, 2, \ldots, d.

Заметим, что нам достаточно найти f(n, k) – количество способов набрать сумму k, после n бросков. Тогда вероятность можно получить, разделив f(n, k) на d^k.

Подставив разные результаты выпадения последнего кубика, получаем f(n, k) = f(n - 1, k - 1) + f(n - 1, k - 2) + \ldots + f(n - 1, k - d).

Заметим, что f(n, k) это просто коэффициент многочлена (x + x^2 + x^3 + \dots + x^d)^n при x^k.

Я не умею эффективно находить в отдельности k-й коэффициент, поэтому давайте найдём многочлен целиком.

Для этого воспользуемся бинарным возведением в степень: это позволит нам найти искомый многочлен всего за O(\log n) перемножений многочленов. Перемножать многочлены можно при помощи быстрого преобразованием Фурье за O(n \log n).
Итоговая асимптотика: O(n \log^2 n).

С небольшими изменениями это же решение можно использовать для кубиков разных размеров (например, для x бросков d125 и y бросков d512).

Total votes 2: ↑2 and ↓0+2

Вот только длина многочлена там не n, а n*d, так что ассимптотика в общем случае указана не совсем точно. Но для констнтного d=6 — это действительно более быстрый метод. Правда есть вообще за O(n), развивающий вашу идею с производящими функциями, указанный в комментарии выше akhalat:
https://towardsdatascience.com/modelling-the-probability-distributions-of-dice-b6ecf87b24ea

This comment wasn’t rated yet0
Идея с тем что число всех комбинаций просто будет коэффициентом при соответствующей степени в многочлене реально прикольная, и по сути служит краеугольным камнем точного решения. Остальное всё — техника.
Total votes 1: ↑1 and ↓0+1

Ага. Это называется "метод производящей функции".

This comment wasn’t rated yet0
Это называется «метод производящей функции».

В курсе, и основная проблема всегда — найти эту производяющую функцию. В данном случае это делается весьма остроумно.
Total votes 1: ↑1 and ↓0+1

На одном из собеседований по приёму на работу попросили за 30 минут написать программу

Задачка, конечно, интересная, но по мне так идиотизм давать такое на очном собесе ещё и с ограничением по времени. Даже сильный специалист банально из-за волнения может затупить с вероятностью 50/50. Результат будет совершенно не показательный, зато уверенно пройдёт отлимпиадник с нулевым опытом реальной разработки. Если такой и нужен, то ок конечно, но по мне так лучше давать несколько мелких, но хитрых задачек по 3-7 минут на каждую и смотреть по кол-ву решённых. Причём, начинать нужно с наиболее лёгких -- сбить волнение.
Говорю это на собственном опыте, на одних собесах без проблем решал подобное, особенно когда вакансия не особо интересна и больше по приколу собес проходишь, на других начинаешь чуть тупить, из-за этого волнуешься, от волнения ещё больше тупишь и так по кругу. Результат околонулевой, после собеса уже спокойно садишься и через 15 минут получаешь рабочее решение. Только работодатель уже не поверит, что я его сам получил, а не в интернете нашёл.
Хороший пример с Яндексом, куда я дважды устраивался. Первый раз собеседующий начал закидывать меня мелкими задачками, каждая легко решалась знанием какой-то фичи языка, но можно было и без этого обойтись. В конце он сказал, что я первый кто всю его коллекцию успел решить, большинство около трети решают. При втором устройстве было два коротких собеса минут по 30-40 и задачи уже явно больше, хоть и не как в статье. На первом решил две, на втором первую и жёстко затупил на второй. В результате два собеса с хорошим результатом и один с плохим. Так это точно не должно работать.

Total votes 4: ↑4 and ↓0+4

Задачка, конечно, интересная, но по мне так идиотизм давать такое на очном собесе ещё и с ограничением по времени. Даже сильный специалист банально из-за волнения может затупить с вероятностью 50/50. Результат будет совершенно не показательный, зато уверенно пройдёт олимпиадник с нулевым опытом реальной разработки

Скажу осторожно, что больше соглашусь.

Если рассказывать про мой опыт, то эту задачку я писал минут 40-45 (т.е. в 30 минут не уложился), учитывая, что случайно нечто подобное я решал лет 8 назад чисто для себя.

Почему не на 100% соглашусь.

Предположу, что для случая с "тупняком" собеседуемого, возможно опрашивающий уже имел заготовленный сценарий как направлять мысли в правильное русло наводящими вопросами

Total votes 1: ↑1 and ↓0+1
и снизить вычислительную сложность алгоритма с O(n) до O(log(n))

У вас алгоритм работает за O(n^2) (но реализован он через такую задницу, что там константы на куб хватит и еще на логарифм останется). Я бы постыдился вот это выставлять на всеобщее обозрение и еще пытаться объяснять.

Total votes 2: ↑1 and ↓10

Озвучу очевидное: чтобы что-то объяснить не нужно писать идеальный код, он должен быть достаточен для понимания, желательно с разделёнными смысловыми блоками.

Я бы постыдился вот это выставлять на всеобщее обозрение

Не стоит комплексовать - ничто не идеально.

У меня не было цели описывать все возможные варианты решения и тем более сравнивать их между собой. Один метод показался занятным - его и расписал. А объяснение - оно работает.

По поводу O(n^2) - наврал, согласен, исправлю

This comment wasn’t rated yet0
ничто не идеально.

Да. Но неужели у вас при написании, например, вот этого куска кода ничего не напряглось внутри?


for i in range(len(list_values)):
    if list_values[i] == int_number_to_find:
        result_out = list_interm_possibility[i] / (c_int_side_dice ** int_dice_number)
        break

Его же можно заменить на


result_out = list_interm_possibility[int_number_to_find - list_values[0]] / (c_int_side_dice ** int_dice_number)

И тут должно стать понятно, что вам вообще не нужен список list_values. Он даже у вас в коде элементарно вычисляется.

Total votes 2: ↑1 and ↓10

И тут должно стать понятно, что вам вообще не нужен список list_values. Он даже у вас в коде элементарно вычисляется.

Абсолютно верно

вот этого куска кода ничего не напряглось внутри?

Подтвержу, напряглось. Однако же для пояснения алгоритма ниже вывожу вот такую картинку:

Т.е. хочется какого-то единообразия и в пояснении и в коде. Иначе если я напишу в коде одно а в пояснении другое, ну согласитесь как минимум будет небольшой ступор у читающего (как максимум - недоверие: пишет в коде одно, а описывает другое)

И тут должно стать понятно, что вам вообще не нужен список list_values. Он даже у вас в коде элементарно вычисляется.

И тут согласен на все 100%

Но в пояснениях оперирую массивами/списками и в коде сознательно иду на этот шаг, чтобы повествование не отходила от кода (или точнее наоборот чтобы код не отходил от повествования).

This comment wasn’t rated yet0

Вы очень намудрили и с решением и с объяснением.


Все ваше объяснение упрощается и ужимается до:
Давайте считать, сколько способов получить все возможные суммы бросив 1,2… n кубиков. Когда мы бросаем k кубиков мы можем получить значения от k (все по 1) до 6*k (все по 6). Примеры (показываем массив с индексами. Числа в квадратиках, индексы над ними):


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

Для подсчета каждого значения для k надо сложить 6 предыдущих значений для k-1, ведь последняя кость может принять значения 1..6 и потом каждый способ получить оставшуюся сумму k-1 кубиком дает новый способ получить всю сумму вместе с последним кубиком. Вот и получается, что массив для следующего k — это сумма 6 массивов для предыдущего k, сдвинутые на 1..6 вправо. Тут можно показать картинку как один массив получается из предыдущего суммой в столбик.


Можно не хранить нули, а только значения от k до 6*k — тогда надо к массиву прибавить 5 его сдвинутых копий и помнить, что начало всегда дает значение для суммы = k. Или можно представить, что на кубиках не числа 1..6, а 0..5. Тогда вам надо просто вычесть из искомой суммы количество кубиков, чтобы перейти к новой задаче.


Вот весь код:


def dice_possibility(int_dice_number, int_number_to_find, c_int_side_dice):
  if int_number_to_find < int_dice_number or int_number_to_find > c_int_side_dice*int_dice_number:
    return 0;
  counts = [1]*6; # Бросок одной кости.
  for k in range(2, int_dice_number+1):
    next_counts = [0]*(len(counts) + 5)
    for shift in range(0, c_int_side_dice):
      for i in range(0, len(counts)):
        # Прибавляем копию массива со сдвигом shift.
        next_counts[i+shift] += counts[i];
    counts = next_counts
  return counts[int_number_to_find - int_dice_number] / c_int_side_dice**int_dice_number

Что делает этот код понятно любому чуть знакомому с питоном. Почему этот код работает понятно и из одного абзаца перед кодом. И не надо писать всякие извращения.


А вообще, все объяснение заменяется двумя словами "динамическое программирование". Но алгоритмы же программистам знать не надо.

This comment wasn’t rated yet0

Вообще можно проработать хоть десять лет и так и не встретить задачу для которой понадобилось бы применять ДП ))

This comment wasn’t rated yet0

Если работать исключительно формошлепством — то да. А так за 10 лет скорее можно несколько раз встретить задачу но просто не понять, что вот где-то тут можно было написать в десять раз более быстрый и в 3 раза более короткий и простой код вместо полного перебора вариантов.


Это проблема задач в программировании. Почти всегда есть тупое понятное плохое решение и без знания алгоритмов даже мысли никакой не возникнет — а вдруг тут что-то не так.

Total votes 2: ↑2 and ↓0+2

Для подсчета каждого значения для k надо сложить 6 предыдущих значений для k-1, ведь последняя кость может принять значения 1..6 и потом каждый способ получить оставшуюся сумму k-1 кубиком дает новый способ получить всю сумму вместе с последним кубиком. Вот и получается, что массив для следующего k — это сумма 6 массивов для предыдущего k, сдвинутые на 1..6 вправо.

Я могу только приветствовать разные интерпретации и объяснения одного и того же явления.

Однако, если для 2-х кубиков данное объяснение ещё можно посчитать интуитивно понятным, то для 3-х, 4-х и далее - это не столь очевидно.

Собственно все "извращения" касались предтече и самому объяснению этой одной единственной фразы.

Озвучу очевидное: читатели могут не оперировать всем накопленным функционалом и опытом, доступным писателю (и если их поменять местами, то будет та же самая ситуация). Соответственно, если цель именно донести мысль, то не всегда ёмкие фразы являются удобоваримым инструментом пояснений, лучше их расписывать, прибавлять к ним картинку, схему, иногда даже анимацию.

This comment wasn’t rated yet0
Однако, если для 2-х кубиков данное объяснение ещё можно посчитать интуитивно понятным, то для 3-х, 4-х и далее — это не столь очевидно.

Давайте представим что все кубики разного цвета. Это ни на что не влияет же? Вот теперь понятно, что если посмотреть, какое число выпало на красном кубике, то остается задача подсчитать количество способов получить x-[1..6] на n-1 кубике.

This comment wasn’t rated yet0

Добавлю обратную связь по коду Python: лучше использовать аннотации типов, чем явно указывать в названиях параметров функции/возвращаемых значениях их тип.

Total votes 1: ↑1 and ↓0+1
Sign up to leave a comment.

Articles

Show the best of all time

Your account

Sections

Information

Services

Support
© 2006–2024, Habr