Разложить сумму с помощью рекурсии

Question

С учетом массива

bills = [500, 200, 100, 50, 20, 10, 5, 2, 1, 0.5, 0.2, 0.1, 0.05, 0.02, 0.01].

Требуется написать функцию decompose(), которая будет разлагать сумму в счетах, содержащихся в массиве.

---

Например, decompose(423) вернет список, содержащий следующие элементы

[200, 200, 20, 1, 1, 1]

Это мой код:

bills = [500, 200, 100, 50, 20, 10, 5, 2, 1, 0.5, 0.2, 0.1, 0.05, 0.02, 0.01]

def decompose(amount, lst = []):
    if len(bills) == 1:
        return lst

    if amount > bills[0]:
        lst += [bills[0]]
        amount = amount - bills[0]
        return decompose(bills, lst + [bills[0]])
    return decompose(bills[1:], lst + [bills[0]]) 

print(decompose(523)) 

Мой вывод:

Traceback (most recent call last):
  File "test.py", line 94, in <module>
    print(decompose(523)) 
  File "test.py", line 91, in decompose
    return decompose(bills, lst + [bills[0]])
  File "test.py", line 88, in decompose
    if amount > bills[0]:
TypeError: '>' not supported between instances of 'list' and 'int'

Как мне разложить мою сумму?

Answer 1

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

def decompose(amount, bills):
    if not bills:
        return []
    if amount >= bills[0]:
        return [bills[0]] + decompose(amount - bills[0], bills)
    else:
        return decompose(amount, bills[1:])

, чтобы:

bills = [500, 200, 100, 50, 20, 10, 5, 2, 1, 0.5, 0.2, 0.1, 0.05, 0.02, 0.01]
decompose(423, bills)

возвращает:

[200, 200, 20, 2, 1]

Answer 2

Вы пытаетесь указать bills вместо текущего amount - и, следовательно, позже вы получите ошибку, потому что вы не можете сделать amount >= bills[0] для list и int.

В вашем коде есть несколько других ошибок:

def decompose(amount, bills, lst = None):  # fix here - supply the possible bills as well
    lst = lst or []
    if amount == 0:                      # fix - when amount == 0 you are done
        return lst

    if amount >= bills[0]:      # fix - as long as bills[0] can be deducted, do so (>=)
        lst += [bills[0]]       # bill[0] is already addded no need to do below again
        amount = amount - bills[0]
        return decompose(amount, bills, lst ) # fix - supply same bills, 
    return decompose(amount, bills[1:], lst ) # fix - bill[0] too big, supply bills[1:]

bills = [500, 200, 100, 50, 20, 10, 5, 2, 1, 0.5, 0.2, 0.1, 0.05, 0.02, 0.01]
print(decompose(523, bills)) 

Вывод:

[500, 20, 2, 1]

Возможно, вы захотите посмотреть на отладку: https://wiki.python.org/moin/PythonDebuggingTools stepчерез ваш код очень помогает - через некоторое время вы разрабатываете внутренний отладчик для таких маленьких кусочков кода, как этот: o)