Разделяй и властвуй: рекурсивное решение для внесения изменений ⇐ Python

[Anonymous]

Я пытаюсь реализовать программу «разделяй и властвуй», которая при наличии набора монет c = {c0, c1,...,cn} и суммы A определяет, сколькими различными способами можно оплатить A, как а также сколько раз функция была рекурсивна.

Я думаю сделать что-то вроде этого:

Код: Выделить всё

callsMade = 0
coins = [1,5,10,25]

def makeChange(A, c):
global callsMade
callsMade += 1
if(A == 0):
return 1
if(A < 0):
return 0
combos = 0
for i in range(len(coins)):
combos += makeChange(A - coins[i], i)
return combos

Где A — передаваемая сумма, а c = len(coins)-1.
Однако этот фрагмент кода ведет себя не так, как я ожидаю. это чтобы. Мой мыслительный процесс состоит в том, чтобы перебрать массив монет, вычесть текущую сумму из монеты в этой позиции массива и рекурсивно вызвать функцию makeChange с меньшей суммой и следующей монетой в массиве, а затем увеличить глобальные вызовы Made на 1 каждый. время.

Используя набор монет = [1,5,10,25] и сумму A = 200, количество комбинаций должно составлять 1463 с примерно Сделано 1500 звонков.

Подробнее здесь: https://stackoverflow.com/questions/560 ... ing-change