Python-сообщество

Enfoire · Июнь 2, 2017 06:01:16

Разбиение числа на слагаемые. Нужно оптимизировать по памяти и по скорости, подскажите, что предпринять? Или может как - нибудь иначе, тем же перебором лучше решается?. Прикрепил скрин с алгоритмом.

 def split(n, m, k, response):
    
    if n == 0 and m == 0:
        response.append(1)
    if (0 < m <= n) is False or (k * m >= n) is False:
        return
    return split(n, m, k - 1, response), split(n - k, m - 1, k, response)
    
response = []
n = int(input())
split(n, 4, n - 3, response)
print(len(response))

Отредактировано Enfoire (Июнь 2, 2017 06:02:52)

Прикреплённый файлы:
Алгоритм.png (174,5 KБ)

doza_and · Июнь 2, 2017 06:47:31

Enfoire
Нужно оптимизировать по памяти и по скорости

Это сродни попросить чтобы и волки были сыты и овцы целы. Оптимизация выполняется по одному критерию. Или память или скорость. Определитесь.

Enfoire
что предпринять?

Судя по вашему посту ничего. Вы не написали что вас не устраивает в вашем решении.

Смею предположить что от вас хотят ровно то что задании у вас написано. Применить метод динамического программирования с мемоизацией. Ваша реализация к этому не имеет никакого отношения.

Enfoire · Июнь 2, 2017 12:34:39

doza_and
метод динамического программирования с мемоизацией

Был бы очень благодарен, если бы Вы показали реализацию обозначенными методами. Сел бы сразу разбираться что к чему там.

Отредактировано Enfoire (Июнь 2, 2017 12:35:17)

Python-сообщество

Уведомления

#1 Июнь 2, 2017 06:01:16

Помогите оптимизировать алгоритм

#2 Июнь 2, 2017 06:47:31

Помогите оптимизировать алгоритм

#3 Июнь 2, 2017 12:34:39

Помогите оптимизировать алгоритм

Board footer