(Lisp)计数更改代码

Question

我最近开始学习lisp，我想一个有趣的问题是计数改变算法，它已经尝试了很多次，但我发现很难弄清楚如何处理这个问题，我想我可以尝试使用循环，但它就是不起作用。我将把我的两个无用的尝试放在下面，但如果有人对我应该如何从lisp的角度思考这个问题有任何建议，我将不胜感激。我也更喜欢使用递归解决方案。

我已经看过了这里关于计算变化的问题，但它们都倾向于面向对象，而我需要更多的功能。这不是家庭作业，只是私人学习！

(defun dollar (amount)   
(let ((l 0) (j 0) (array (make-array '(5 10 20 50 100 200 500 1000 2000 5000 100000))) (results (make-array 50 :initial-element nil))
        (do (l 10 (+ l 1))
       (do ((= j (aref array l)) amount (+ j 1))
         (+ (aref array j) (- (aref results j) (aref array l))))))
                   ))

(defun coin-change (amount coins)
(cond ((< amount 0) 0)
      ((= amount 5) 1)
      ((null coins) 0)
      (t (+ (make-change-with-coins (- amount (car coins)) coins)
            (make-change-with-coins amount (cdr coins)))))

)

示例输入将是(硬币找零20 '(5 10 20 50 100 200 500 1000 2000 5000 100000))，它将返回4

Answer 1

标准格式有助于获得正确的代码结构。阅读一些关于一门新语言的文档会更有帮助。

这是你写的：

(defun dollar (amount)
  (let ((l 0)
        (j 0)
        (array (make-array '(5 10 20 50 100 200 500 1000 2000 5000 100000)))
        (results (make-array 50 :initial-element nil))
        (do (l 10 (+ l 1))
            (do ((= j (aref array l)) amount (+ j 1))
                (+ (aref array j) (- (aref results j) (aref array l))))))))

Dollar没有得到正确的语义。Make-array将维度作为第一个参数，您很可能希望将do表单作为let的主体。我在这里使用向量文字。

(defun dollar (amount)
  (let ((l 0)
        (j 0)
        (array #(5 10 20 50 100 200 500 1000 2000 5000 100000))
        (results (make-array 50 :initial-element nil)))
    (do (l 10 (+ l 1))
        (do ((= j (aref array l)) amount (+ j 1))
            (+ (aref array j) (- (aref results j) (aref array l)))))))

Do首先接受绑定列表，然后是包含结束条件的表单和返回表单，最后是形成主体的表单。

(defun dollar (amount)
  (let ((l 0)
        (j 0)
        (array #(5 10 20 50 100 200 500 1000 2000 5000 100000))
        (results (make-array 50 :initial-element nil)))
    (do ((l 10 (+ l 1)))
        (#| end condition here |#
         #| some more forms
         that return something |#)
      (do ((= j (aref array l)) ; uh, so this binds the variable "=" to j
                                ; and updates it to (aref array l) on iteration
           amount    ; an empty binding, initially nil
           (+ j 1))  ; binds the variable "+" to j and updates it to 1
          (+           ; tries to evaluate the variable "+" as a form...
           (aref array j)   ; no effect
           (- (aref results j) (aref array l)))))))  ; would return this

我尝试纠正外部do的形状，并对内部do进行注释。正如您所看到的，这完全没有意义。

(defun coin-change (amount coins)
  (cond ((< amount 0) 0)
        ((= amount 5) 1)
        ((null coins) 0)
        (t (+ (make-change-with-coins (- amount (car coins)) coins)
              (make-change-with-coins amount (cdr coins))))))

这看起来至少在语义上是正确的，但是我不知道它应该如何工作(我也不知道make-change-with-coins是做什么的)。

我认为最好先读一本好的介绍性书籍(我喜欢Practical Common Lisp)，然后再仔细阅读Common Lisp Hyperspec (CLHS)。

Answer 2

我不清楚第一个函数应该做什么。

第二个几乎没问题，这是一个固定的版本：

(defun coin-change (amount coins)
  (cond
    ((< amount 0) 0)
    ((= amount 0) 1)
    ((= (length coins) 0) 0)
    (t (+ (coin-change (- amount (first coins)) coins)
          (coin-change amount (rest coins))))))

这个想法是：

• A负金额不能匹配(0方式)
• 零可以以一种方式匹配(不提供任何硬币)
• 如果金额>0并且我们没有剩余的硬币类型，那么就没有方法
• 否则我们可以要么A)给出第一种硬币类型的一块，然后计算我们可以匹配其余部分的方法，B)在不使用第一种硬币类型的情况下计算方法。答案是A+B

请注意，这将为大笔金额提供巨大的计算时间，因为它没有利用一个重要的事实，即从特定硬币类型开始匹配特定金额的方法数量并不取决于我们如何获得这个金额(即过去的历史)。通过添加缓存，您可以获得一个更快的动态编程解决方案，因为每个计算只做一次。