Рекурсивно найти все комбинации монет, которые производят указанное количество - PullRequest
Новая
       28

Рекурсивно найти все комбинации монет, которые производят указанное количество

0 голосов
/ 22 марта 2012

Мои извинения заранее.Я знаю, что этот вопрос задавался ранее с ответами, которые не дали результатов, которые я хочу / нуждаюсь.Я пытаюсь написать функцию, которая выполняет следующие действия в Python3:

Мне нужна рекурсивная функция, которая возвращает все количество способов (комбинаций монет), которые производят указанное количество.Эта функция может содержать только два аргумента, количество и монеты.Мне было трудно сосредоточиться на рекурсии, поэтому объяснения также будут с благодарностью.Благодарю.

Вот что у меня сейчас есть: 

COINS = dict(
    USA=[100, 50, 25, 10, 5, 1],
    AUSTRALIA=[200, 100, 50, 20, 10, 5],
    UK=[500, 200, 100, 50, 20, 10, 5, 2, 1]
)

def change(amount, coins):
    """
    >>> change(100, COINS['USA'])
    293
    """
    if amount < 0:
        return 0
    elif amount == 0:
        return 1
    else:
        biggestcoin, *rest = coins[0], coins[1:]
        return change(amount-biggestcoin, coins) + change(amount, rest)

Ответы [ 2 ]

3 голосов
/ 22 марта 2012 
biggestcoin, *rest = coins[0], coins[1:]

Вы хотите rest здесь, логически, а не *rest, потому что у вас есть два элемента на каждой стороне. Использование *rest здесь создает дополнительный слой переноса списка, который затем приводит к исключению, которое вы, вероятно, видите.

Как только вы это исправите: подумайте о том, что произойдет, если вы не сможете заработать желаемую сумму с 1 каждой монетой. В конечном итоге рекурсивный вызов change(amount, rest) произойдет, если amount больше нуля, а rest пусто. Вам также нужно разобраться с этим делом.

1 голос
/ 22 марта 2012

Идея рекурсии проста:

Попробуйте уменьшить размер задачи, по одному маленькому шагу за раз.ты почти закончил!Начните с большой проблемы и продолжайте постепенно уменьшать размер, пока не получите очень маленькую проблему.Вы можете решить это так, как вам нравится.

Как это относится к проблеме внесения изменений?Что ж, если вас попросят набрать n, вы можете немного уменьшить размер проблемы, используя всего одну монету.И если вы продолжите идти, в конце концов вы получите достаточно маленькую проблему для решения!

...