2

我正在尝试解决硬币找零问题：

给定一个数字 k 的列表，有多少种方法可以改变给定的数量 m。

作为资源之一，我有以下伪代码：

 (define (count-change amount)
  (cc amount 5))
(define (cc amount kinds-of-coins)
  (cond ((= amount 0) 1)
        ((or (< amount 0) (= kinds-of-coins 0)) 0)
        (else (+ (cc amount
                     (- kinds-of-coins 1))
                 (cc (- amount
                        (first-denomination kinds-of-coins))
                     kinds-of-coins)))))
(define (first-denomination kinds-of-coins)
  (cond ((= kinds-of-coins 1) 1)
        ((= kinds-of-coins 2) 5)
        ((= kinds-of-coins 3) 10)
        ((= kinds-of-coins 4) 25)
        ((= kinds-of-coins 5) 50)))

但是我不明白这个伪代码。当它们应该在后面时，它在前面有算术符号。我了解 else 语句开始的地方。但是当进入 else 循环时，我不知道发生了什么。您能否将此伪代码简化为在 else 子句之后的每个步骤中要做的一些逻辑事情？

或者有什么文章比这个伪代码解决这个问题更有用。谷歌搜索这个我只发现要求你给出最佳改变的问题，但我不需要那个。

注意请不要给我代码，因为这是一个 coursera 课程，直接回答会违反荣誉代码。

更新 正如@EmilVikström 亲切地向我解释了那里到底发生了什么，我试图生成一个应该与方案相同的小伪代码（这只是 else 子句，因为其余的甚至是不言自明的我）。

else
  cc ( amount - kindOfCoins.head , kindOfCoins) + cc ( amount , kindOfCoins.tail )

这是计划的结果吗？如果不是我哪里出错了？请再次不要给我答案（如果可以的话，请指出我正确的方向），因为这将违反 coursera 荣誉守则。

4

1 回答 1

1

这是 else 块的内容：

(+ (cc amount
       (- kinds-of-coins 1))
   (cc (- amount
          (first-denomination kinds-of-coins))
       kinds-of-coins))

这是Scheme，其中所有函数，包括算术运算，都是一个括号，函数名作为第一个元素，函数的参数作为后面的元素。

首先，您+使用两个参数调用该函数。让我们调用这些参数a，并b出于解释的目的：

(+ a b)

两者都a恰好b是函数调用。这里是a：

(cc amount (- kinds-of-coins 1))

和b：

(cc (- amount ((first-denomination kinds-of-coins)) kinds-of-coins)

让我们专注于其中的第一个，a。a是一个cc带有两个参数的函数调用，我们称它们为xand y，我们有这个函数调用：(cc x y)wherex = amount和y = (- kinds-of-coins 1)。所以你看这y也是一个函数调用。

这种情况还在继续。您可以查看每个括号本身并解析它的值。从最里面的括号开始（如数学），然后向外工作。

您还需要了解它cc是递归的，这意味着它调用自己来完成它的工作。else当代码由于其他条件为真而不再进入块时，它将最终停止调用自己。这种停止条件称为递归的基本情况。一个好的递归函数在每个递归步骤（每次它调用自己）中总是更接近它的基本情况，所以你可以确定它最终会到达它。

于 2014-05-07T15:42:08.550 回答