Представление суммы денег конкретными счетами

Ваша процедура делает слишком много, и вы используете ненужную мутацию. Если вы разделите проблему на части.

(define (calc-one-bill n bill)
  ...)

;; test 
(calc-one-bill 450 100) ; ==> 4
(calc-one-bill 450 50)  ; ==> 9

Тогда вы можете сделать:

(define (calc-new-n n bill amount)
  ...)

(calc-new-n 450 100 4) ; ==> 50
(calc-new-n 450 50 9)  ; ==> 0

Затем вы можете уменьшить исходную реализацию следующим образом:

(define (calc n bills)
  (if (null? bills)
      (if (zero? n)
          '()
          (error "The unit needs to be the last element in the bills list"))
      (let* ((bill (car bills))
             (amount (calc-one-bill n bill)))
        (cons amount
              (calc (calc-new-n n bill amount)
                    (cdr bills))))))

Это всегда будет выбирать решение с наименьшим количеством счетов, как и ваша версия. Обе версии требуют, чтобы последний элемент в переданном bill был единицей 1. Более сложный метод, который работает с (calc 406 (list 100 10 5 2)) и потенциально может найти все комбинации решений, см. В ответе Уилла.

Эта проблема требует простого рекурсивного недетерминированного программирования.

• Мы начинаем с заданной суммы и заданного списка банкнот достоинств, очевидно, с неограниченным количеством каждой банкноты (в противном случае это была бы другая проблема).
• В каждый момент времени мы можем использовать либо самую большую купюру, либо нет.
• Если мы его используем, общая сумма уменьшается на сумму счета.
• Если сумма равна 0, мы получили решение!
• Если сумма отрицательная, она недействительна, поэтому нам следует отказаться от этого пути.

Код здесь будет следовать за другим моим ответом, в котором из общего количества решений (которых больше одного, для вашего примера). Нам просто нужно будет помнить и о самих решениях, тогда как упомянутый выше код только их считал.

Мы можем закодировать это как recursive-backtracking, вызывая обратный вызов с каждым успешно найденным решением изнутри самого глубокого уровня рекурсии (равносильно самому глубоко вложенному циклу в структуре вложенных циклов, созданной с помощью рекурсии , что является сутью рекурсивного поиска с возвратом):

(define (change sum bills callback)
  (let loop ([sum sum] [sol '()] [bills bills])    ; "sol" for "solution"
    (cond
       ((zero? sum)   (callback sol))              ; process a solution found
       ((< sum 0)      #f)
       ((null? bills)   #f)
       (else
        (apply
          (lambda (b . bs)                         ; the "loop":
              ;; 1.                                ; either use the first
            (loop (- sum b) (cons b sol) bills)    ;   denomination,
              ;; 2.                                ;   or,
            (loop    sum            sol     bs))   ;   after backtracking, don't!
          bills)))))

Он должен быть вызван, например, один из

;; construct `the-callback` for `solve` and call 
;;       (solve ...params the-callback)
;; where `the-callback` is an exit continuation

(define (first-solution solve . params)
  (call/cc (lambda (return)
      (apply solve (append params         ; use `return` as
                     (list return))))))   ; the callback

(define (n-solutions n solve . params)    ; n assumed an integer
  (let ([res '()])                        ; n <= 0 gets ALL solutions
    (call/cc (lambda (break)
        (apply solve (append params
                       (list (lambda (sol)
                               (set! res (cons sol res))
                               (set! n (- n 1))
                               (cond ((zero? n) (break)))))))))
    (reverse res)))

Тестирование,

> (first-solution change 406 (list 100 10 5 2))

'(2 2 2 100 100 100 100)

> (n-solutions 7 change 415 (list 100 10 5 2 1))

'((5 10 100 100 100 100)
  (1 2 2 10 100 100 100 100)
  (1 1 1 2 10 100 100 100 100)
  (1 1 1 1 1 10 100 100 100 100)
  (5 5 5 100 100 100 100)
  (1 2 2 5 5 100 100 100 100)
  (1 1 1 2 5 5 100 100 100 100))

Относительно того, как структурирован этот код, см. Как сгенерировать все перестановки элементов в списке по одной в Лиспе? Он создает вложенные циклы с решением доступный в теле самого внутреннего цикла.

Относительно того, как кодировать недетерминированный алгоритм (делая все возможные варианты сразу) надлежащим функциональным способом, см. Как сделать powerset в DrRacket? и Как найти разделы списка в схеме.

Я вот так решил сейчас :)

(define (calc n xs)
  (define (calcAssist n xs usedBills)
    (cond ((null? xs) usedBills)
          ((pair? xs) 
            (calcAssist (- n (* (car xs) (floor (/ n (car xs))))) 
                        (cdr xs) 
                        (append usedBills 
                                (list (floor (/ n (car xs)))))))
          (else 
            (if ((= (- n (* xs (floor (/ n xs)))) 0)) 
               (append usedBills (list (floor (/ n xs))))
               (display "No solution")))))

  (calcAssist n xs (list)))

Тестирование:

> (calc 415 (list 100 10 5 2 1))
'(4 1 1 0 0)

Думаю, это первая программа, которую я написал при изучении ФОРТРАНА! Вот версия, которая не скрывает использования всего, что может предложить Racket (или, по крайней мере, всего, о чем я знаю). Таким образом, это, вероятно, ужасное домашнее задание, и оно определенно красивее, чем ФОРТРАН, который я написал в 1984 году.

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

(define/contract (denominations-of amount denominations)
  ;; split amount into units of denominations, returning the split
  ;; in descending order of denomination, and any remainder (if there is
  ;; no 1 denomination there will generally be a remainder).
  (-> natural-number/c (listof (integer-in 1 #f))
      (values (listof natural-number/c) natural-number/c))
  (let handle-one-denomination ([current amount]
                                [remaining-denominations (sort denominations >)]
                                [so-far '()])
    ;; handle a single denomination: current is the balance,
    ;; remaining-denominations is the denominations left (descending order)
    ;; so-far is the list of amounts of each denomination we've accumulated
    ;; so far, which is in ascending order of denomination
    (if (null? remaining-denominations)
        ;; we are done: return the reversed accumulator and anything left over
        (values (reverse so-far) current)
        (match-let ([(cons first-denomination rest-of-the-denominations)
                     remaining-denominations])
          (if (> first-denomination current)
              ;; if the first denomination is more than the balance, just
              ;; accumulate a 0 for it and loop on the rest
              (handle-one-denomination current rest-of-the-denominations
                                       (cons 0 so-far))
              ;; otherwise work out how much of it we need and how much is left
              (let-values ([(q r)
                            (quotient/remainder current first-denomination)])
                ;; and loop on the remainder accumulating the number of bills
                ;; we needed
                (handle-one-denomination r rest-of-the-denominations
                                         (cons q so-far))))))))