我想在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))))))

最佳答案

您的过程做得太多,您使用了不必要的突变。如果您拆分问题。

(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

09-25 19:21