|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
17.08.2018, 10:30 | #1 | |
Пользователь
Регистрация: 29.07.2016
Сообщений: 13
|
Алгоритм, рекурсия, пайтон
Есть задача с ПЕ:
Цитата:
Код:
Последний раз редактировалось Alex11223; 17.08.2018 в 15:10. |
|
17.08.2018, 13:13 | #2 |
Программист
Участник клуба
Регистрация: 23.06.2009
Сообщений: 1,772
|
Эта задача - на динамическое программирование. По размениваемой сумме.
Прямой рекурсивный алгоритм слишком много ресурсов жрёт. |
17.08.2018, 15:03 | #3 |
Пользователь
Регистрация: 29.07.2016
Сообщений: 13
|
А разве memoization не динамическое программирование ? Или нужен bottom up ?
|
17.08.2018, 15:41 | #4 |
Программист
Участник клуба
Регистрация: 23.06.2009
Сообщений: 1,772
|
Дело в том, что при таком построении рекурсии мемоизация бесполезна - ведь количества только нарастают и ни разу не повторяются.
Динамика, как я уже сказал, должна строиться по суммам: сколько существует способов разменять данную сумму. Тогда да, можно построить рекурсивный алгоритм с мемоизацией. Но зачем, когда можно просто сделать массив результатов и заполнить его в один проход |
17.08.2018, 16:49 | #5 |
Пользователь
Регистрация: 29.07.2016
Сообщений: 13
|
Точно, мемоизация бесполезна.. спасибо
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Пайтон. Дан список чисел. Выведите все элементы списка, которые больше предыдущего элемента. Что не так? | adolphina | Помощь студентам | 3 | 16.11.2016 23:02 |
факториал. пайтон | adolphina | Помощь студентам | 5 | 11.11.2016 08:31 |
Пайтон, питон. надо найти максимум трёх элементов. | adolphina | Помощь студентам | 3 | 10.11.2016 23:02 |
Разработайте алгоритм методом пошаговой детализации и программу, реализующую этот алгоритм. | iamhated | Помощь студентам | 1 | 15.01.2012 16:24 |
Разработайте алгоритм методом пошаговой детализации и программу, реализующую этот алгоритм | iamhated | Помощь студентам | 1 | 14.01.2012 16:22 |