0

我只是通过 SICP 探索函数式编程，并且想知道如何扩展练习 2.19 来做一些更有用的事情（并且这似乎需要副作用）。

该练习涉及一个程序，该程序计算一个给定硬币面额列表的给定金额（以便士为单位）的更改方式的数量。解决方案非常简单（cc 代表“count-change”）：

(define (cc amount coin-values)
  (cond ((= amount 0) 1)
        ((or (< amount 0) (no-more? coin-values)) 0)
        (else
         (+ (cc amount
                (except-first-denomination coin-values))
            (cc (- amount
                   (first-denomination coin-values))
                coin-values)))))

(define (first-denomination coinTypes) (car coinTypes))
(define (except-first-denomination coinTypes) (cdr coinTypes))
(define (no-more? coinTypes) (null? coinTypes))

您可以在此处查看相关的 SICP 部分，如果上述内容不清楚，则链接到算法描述。

我首先想看看硬币的实际组合构成了每种更改方式，因此我编写了自己的版本，将每个解决方案打印为列表：

(define (count-change amount coinTypes)
    (define (cc amount coinTypes currChangeList)
        (cond ((= amount 0) 
                    (display (reverse currChangeList)) 
                    (newline) 
                    1)
              ((or (negative? amount) (null? coinTypes)) 
                    0)
              (else (+ (cc amount (cdr coinTypes) currChangeList)
                       (cc (- amount (car coinTypes)) coinTypes (cons (car coinTypes) currChangeList))))))
    (cc amount coinTypes ()))

所以这就是我卡住的地方：我想修改我的方法，而不是返回一个整数结果=# 进行更改的方式，并在计算过程中简单地打印每种方式，我希望它返回一个解决方案列表（a列表的列表，其中的长度 = # 进行更改的方法）。但是，我不知道如何实现这一点。用命令式/OO 语言很容易做到，但我不知道如何在功能上做到这一点。

有人知道如何实现这一目标吗？对于经验丰富的函数式编码器来说，这似乎应该是一件很容易的事情。请帮助满足我的好奇心，并为自己赢得一些编码业力:)

谢谢

4

1 回答 1

0 
(define (count-change amount coinTypes)
    (define (cc amount coinTypes currChangeList)
        (cond ((= amount 0) 
               (list (reverse currChangeList)))
              ((or (negative? amount) (null? coinTypes)) 
               '())
              (else
                (append
                   (cc amount (cdr coinTypes) currChangeList)
                   (cc (- amount (car coinTypes))
                       coinTypes
                       (cons (car coinTypes) currChangeList))))))
    (cc amount coinTypes '()))
于 2013-01-30T09:02:59.767 回答