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