Посмотрите на эту рекурсивную функцию.Он рассчитывает количество вариантов для данного флага n, k
и last
(показывает, помечали ли мы ячейку в последнем столбце).
Если мы не помечаем ячейку в текущем столбце, у нас есть три варианта следующего: не отмечать снова, отмечать сверху, отмечать снизу.
Если мы помечаем ячейку в текущем столбце, у нас есть только два варианта для следующего: не отмечать снова или отмечать ячейку в противоположной строке.
Обратите внимание, что код возвращает правильный результат 38 для вашего второго примера - есть C(5,3)=10
комбинации для распределения объектов по столбцам.Одиночная комбинация с разделенными столбцами 10101
дает 8 вариантов, три комбинации с объединенными столбцами, например 01110
, дают 3 * 2 = 6 вариантов, а шесть комбинаций, таких как 01011
, дают 6 * 4 = 24 варианта.
Предоставленный код не эффективен (он имеет экспоненциальную сложность), поэтому для практических целей его следует переписать с использованием динамического программирования или запоминания (сохранение результатов вызовов в карте с помощью клавиши n / k / l и их повторное использование при необходимости) или с использованием табличного подхода(заполните н / к / л таблицу по ячейкам).
Я оставляю это преобразование как довольно простое упражнение для автора (потому что автор не показал никакого собственного кода)
def F(n, k, last):
if k > n:
return 0
if k == 0:
return 1
if k == n:
return 2 - last # 2 if last==0 else 1
return F(n - 1, k, 0) + (2 - last) * F(n - 1, k - 1, 1)
print(F(4,2,0))
print(F(5,3,0))
>>18
>>38