Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > Скриптовые языки программирования > Python
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 17.08.2018, 10:30   #1
shonzie
Пользователь
 
Регистрация: 29.07.2016
Сообщений: 13
По умолчанию Алгоритм, рекурсия, пайтон

Есть задача с ПЕ:
Цитата:
In England the currency is made up of pound, £, and pence, p, and there are eight coins in general circulation:
1p, 2p, 5p, 10p, 20p, 50p, p1 (100p) and p2 (200p).
How many different ways can p2 be made using any number of coins?
Написал рекурсивный алгоритм, но работает очень медленно.. Есть какие идеи как его оптимизировать, и что со скоростью ?

Код:
cnt = 0
set = set()
def coin_sums(one=0, two=0, five=0, ten=0,
              twenty=0, fifty=0, onep=0, twop=0):
    global cnt
    global set
    sum = one + two + five + ten + twenty + fifty + onep + twop
    tup = (one, two, five, ten, twenty, fifty, onep, twop)

    if tup in set:
        return
    elif sum == 200:
        set.add(tup)
        cnt += 1
        return
    elif sum > 200:
        return
    else:
        coin_sums(one+1, two, five, ten, twenty, fifty, onep, twop)
        coin_sums(one, two+2, five, ten, twenty, fifty, onep, twop)
        coin_sums(one, two, five+5, ten, twenty, fifty, onep, twop)
        coin_sums(one, two, five, ten+10, twenty, fifty, onep, twop)
        coin_sums(one, two, five, ten, twenty+20, fifty, onep, twop)
        coin_sums(one, two, five, ten, twenty, fifty+50, onep, twop)
        coin_sums(one, two, five, ten, twenty, fifty, onep+100, twop)
        coin_sums(one, two, five, ten, twenty, fifty, onep, twop+200)

coin_sums()
print(cnt)

Последний раз редактировалось Alex11223; 17.08.2018 в 15:10.
shonzie вне форума Ответить с цитированием
Старый 17.08.2018, 13:13   #2
Black Fregat
Программист
Участник клуба
 
Аватар для Black Fregat
 
Регистрация: 23.06.2009
Сообщений: 1,772
По умолчанию

Эта задача - на динамическое программирование. По размениваемой сумме.
Прямой рекурсивный алгоритм слишком много ресурсов жрёт.
Black Fregat вне форума Ответить с цитированием
Старый 17.08.2018, 15:03   #3
shonzie
Пользователь
 
Регистрация: 29.07.2016
Сообщений: 13
По умолчанию

А разве memoization не динамическое программирование ? Или нужен bottom up ?
shonzie вне форума Ответить с цитированием
Старый 17.08.2018, 15:41   #4
Black Fregat
Программист
Участник клуба
 
Аватар для Black Fregat
 
Регистрация: 23.06.2009
Сообщений: 1,772
По умолчанию

Дело в том, что при таком построении рекурсии мемоизация бесполезна - ведь количества только нарастают и ни разу не повторяются.

Динамика, как я уже сказал, должна строиться по суммам: сколько существует способов разменять данную сумму. Тогда да, можно построить рекурсивный алгоритм с мемоизацией. Но зачем, когда можно просто сделать массив результатов и заполнить его в один проход
Black Fregat вне форума Ответить с цитированием
Старый 17.08.2018, 16:49   #5
shonzie
Пользователь
 
Регистрация: 29.07.2016
Сообщений: 13
По умолчанию

Точно, мемоизация бесполезна.. спасибо
shonzie вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Пайтон. Дан список чисел. Выведите все элементы списка, которые больше предыдущего элемента. Что не так? 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