Псевдокод в логические шаги?

Question

Я пытаюсь решить проблему обмена монет:

Учитывая список чисел k, сколько существует способов внести изменения в данную сумму m.

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

 (define (count-change amount)
  (cc amount 5))
(define (cc amount kinds-of-coins)
  (cond ((= amount 0) 1)
        ((or (< amount 0) (= kinds-of-coins 0)) 0)
        (else (+ (cc amount
                     (- kinds-of-coins 1))
                 (cc (- amount
                        (first-denomination kinds-of-coins))
                     kinds-of-coins)))))
(define (first-denomination kinds-of-coins)
  (cond ((= kinds-of-coins 1) 1)
        ((= kinds-of-coins 2) 5)
        ((= kinds-of-coins 3) 10)
        ((= kinds-of-coins 4) 25)
        ((= kinds-of-coins 5) 50)))

Однако я не понимаю этот псевдокод. У этого есть арифметические знаки впереди, когда они должны быть позади. Я понимаю до того момента, когда начинается утверждение else. Но когда я иду внутрь цикла else, я понятия не имею, что происходит. Можете ли вы сократить этот псевдокод до ряда логических действий, которые нужно выполнять на каждом шаге после предложения else?

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

ПРИМЕЧАНИЕ Пожалуйста, не давайте мне код, так как это курс курса, и прямой ответ нарушит кодекс чести.

ОБНОВЛЕНИЕ Как @EmilVikström любезно объяснил мне, что именно там происходит, я попытался создать небольшой псевдокод, который должен быть таким же, как схема (это только предложение else, так как остальное довольно очевидно, даже для мне).

else
  cc ( amount - kindOfCoins.head , kindOfCoins) + cc ( amount , kindOfCoins.tail )

Это то, что вытекает из схемы? Если нет, то где я ошибся? Пожалуйста, еще раз не дайте мне ответ (просто укажите мне правильное направление, если можете), так как это нарушит кодекс чести Coursera.

Answer 1

Это содержимое блока else:

(+ (cc amount
       (- kinds-of-coins 1))
   (cc (- amount
          (first-denomination kinds-of-coins))
       kinds-of-coins))

Это схема, где все функции, включая арифметические операции, являются круглыми скобками с именем функции в качестве первого элемента и аргументами функции в качестве элементов впоследствии.

Сначала у вас есть звонок в + функция с двумя аргументами. Давайте назовем аргументы a а также b для целей этого объяснения:

(+ a b)

И то и другое a а также b случается, что вызовы функций. Вот a:

(cc amount (- kinds-of-coins 1))

а также b:

(cc (- amount ((first-denomination kinds-of-coins)) kinds-of-coins)

Давайте сосредоточимся на первом из них, a, a это вызов функции cc с двумя аргументами, давайте назовем их x а также yи у нас есть вызов этой функции: (cc x y) где x = amount а также y = (- kinds-of-coins 1), Итак, вы видите, что y также вызов функции.

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

Вы также должны понимать, что cc является рекурсивным, что означает, что он призывает себя выполнять свою работу. В конечном итоге он перестанет называть себя, когда код не введет else блокировать больше из-за других условий. Это условие остановки называется базовым случаем рекурсии. Хорошая рекурсивная функция всегда будет приближаться к своему базовому случаю на каждом рекурсивном шаге (каждый раз, когда она вызывает себя), так что вы можете быть уверены, что она в конечном итоге достигнет ее.