Как это работает: CodeWars
Я наткнулся на одну задачу на CodeWars. Не сумев ее решить, я решил посмотреть решения тех, кто уже прошел. Как и положено новичку, я ничего не понял. Chat-GPT непоследовательно требует объяснений. Помогите мне понять, что здесь происходит.
def outcome(n, s, k):
from math import comb
if not k: return 1
if not n or k < n: return 0
return sum((-1) ** i * comb(n, i) * comb(k - s * i - 1, k - s * i - n) for i in range((k - n) // s + 1))
ОПИСАНИЕ:
У вас есть n кубиков, каждый из которых имеет s сторон, пронумерованных от 1 до s. Сколько исходов в сумме дает указанное число k?
Например, если мы бросим четыре обычных шестигранных кубика, мы получим четыре результата, сумма которых равна 5.
(1, 1, 1, 2)
(1, 1, 2, 1)
(1, 2, 1, 1)
(2, 1, 1, 1)
Существует 100 случайных тестов с:
0 <= n <= 10
1 <= s <= 20
0 <= k <= n * s
Примечания:
всегда есть ровно 1 случай, которого нужно достичь k = 0, независимо от количества кубиков, которые у вас есть без кубиков, достичь положительного результата k невозможно. Изначально я думал решить упражнение с помощью рекурсии, но равномерно. Потом искал аналоги на форумах, но опять безуспешно.
Ответы 1
Ради вашего интереса это можно сделать рекурсивно. На самом деле это довольно просто:
def outcome(n, s, k):
dp = [[0] * (k+1) for _ in range(n+1)]
dp[0][0] = 1
for i in range(1, n+1):
for j in range(1, k+1):
for x in range(1, min(s, j)+1):
dp[i][j] += dp[i-1][j-x]
return dp[n][k]
В качестве примера:
n = 4
s = 6
k = 5
print(outcome(n, s, k))
возвращает 4.
Я думаю, что рекурсивный подход лучше объясняет, что происходит: сначала вы создаете 2d-массив dp (измерений (n+1) x (k+1) для хранения количества результатов для каждой возможной суммы с использованием кубиков i. Это пространство используется для учета базовых случаев, когда количество кубиков или целевая сумма равна 0. Установите dp[0][0] = 1 для базового случая, когда существует ровно 1 способ получить сумму 0 с 0 кубиками. Затем переберите количество кубиков и также пройдите по всем целям из. От 1 до k. Для каждой целевой суммы j рассмотрим все возможные результаты броска текущего игрального кубика, представленные переменной x. Перебор x от 1 до min(s, j) гарантирует, что вы не учитываете результаты, превышающие количество сторон. min(s, j) или текущая целевая сумма s Наконец, для каждого результата j добавьте количество результатов из предыдущего количества кубиков x и оставшуюся целевую сумму (i-1) в текущую ячейку (j-x).
Вы спрашиваете, как получается математическая формула. Имеет мало общего с программированием. Посмотрите Сколькими способами может быть сумма 𝑛 игральных костей 𝑠?.