recursion - 用特定票据表示金额

Question

我想在 Racket 中编写一个函数，它接受一定数量的钱和一个特定账单值的列表，然后返回一个列表，其中包含每种类型的账单数量，以使总金额达到给定。例如 (calc 415 (list 100 10 5 2 1)) 应该返回 '(4 1 1 0 0)。

我尝试过这种方式，但这不起作用:/老实说，我想我还没有完全理解在 Racket 中使用 set! 可以/不能做什么。

(define (calc n xs)
  (cond ((null? xs) (list))
        ((not (pair? xs)) 
          (define y n) 
          (begin (set! n (- n (* xs (floor (/ n xs)))))
                 (list (floor (/ y xs))) ))
        (else (append (calc n (car xs))
                      (calc n (cdr xs))))))

Answer 1

您的程序做的太多，并且您使用了不必要的突变。如果你把问题分开。

(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)) 并且可能找到所有解决方案组合，请参阅 Will's answer .