3

Мы имеем вводные данные M и N, N > M, M > 0. После этого мы создаем список от 1 до M, а дальше нам надо найти все возможные варианты сумм элементов в списке чтобы сумма элементов равнялась N, причём каждый элемент списка можно складывать с самим собой несколько раз. Надо вывести количество сумм, которое можно сделать в списке.

Например: M = 3 , N = 4, ---> [1,2,3] ---> 1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2, 1+3, 3+1, количество возможных вариантов сумм в этом примере: 7.

3

2 ответа 2

1

Общее количество вариантов можно посчитать, суммируя возможные варианты для каждого допустимого слагаемого по очереди:

from functools import lru_cache

@lru_cache(maxsize=None)
def C(m, n):
    return sum(C(m, n - k) for k in range(1, min(m, n) + 1)) if n else 1

print(C(3, 4)) # -> 7

functools.lru_cache используется, чтобы не пересчитывать уже рассмотренные варианты.

3
  • Может, сказалось то, что я не спал всю ночь, но я допирал до этого алгоритма несколько часов. Вы бы добавили объяснение.
    – AvidCoder
    23 июл 2019 в 5:25
  • @ИмяФамилия решение в ответе это адаптация из вопроса с более сложным случаем (ссылка выше была). Если всё равно не ясно, то можно начать с чтения о динамическом программировании.
    – jfs
    23 июл 2019 в 15:38
  • Да я разобрался. Написал же "допирал", значит, в конце концов допёр.)
    – AvidCoder
    23 июл 2019 в 15:53
1

В дополнение к ответу jfs.

Думается мне, что массивом быстрее.

def C(M, N):
    f = [0] * (N + 1)
    f[0] = 1
    for i in range(1, N + 1):
        for j in range(min(M, i), 0, -1):
            f[i] += f[i - j]     
    return f[N]
2
  • если вас производительность интересует, то полезно её измерить. Что-нибудь вроде: python -m timeit -s "from array_solution import C" "C(3, 4)"
    – jfs
    23 июл 2019 в 15:45
  • @jfs проверил через time.time(), на больших числах появляется большая разница, на небольших, например, на 16 и 32 у моего метода 0.000187, у вашего - 0.00138, если через python -m timeit -s у моего пишет 20000000 loops, best of 5: 13.6 nsec per loop, у вашего - 20000000 loops, best of 5: 13.9 nsec per loop. Я кроме синтаксиса питона больше практически ничего не знаю, как может какой-то непонятный цикл (loop) выполниться за 14nsec на числах 10 и 100? Там же явно больше времени должно уйти!
    – AvidCoder
    24 июл 2019 в 21:06

Ваш ответ

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

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