SICP中关于兑换零钱的练习

记得在SICP的第一章中，第1.2.2小节讲树形递归的时候，有一个实例是换零钱方式的统计。其中，作者是用的树形递归去求解的。但是，在这个实例的最后，作者又以找到一个效率更高的算法作为了一个非正式的作业，留给了读者作为挑战。起先在看完这节内容的时候，也是绞尽脑汁都想不出还能有什么更好的算法。但是，在看完了大半本书之后，无意中发现了一种方式。其实方法也很笨，就是枚举法，只是当时学到的语法太少了，不知道如何用scheme表达罢了，但是如果换成用python，那当时就应该能马上写出来的。好了 不废话了，直接上代码吧：

; 方法1 纯函数式实现
(define (count-change-1 amount denomination-list)
    (length (filter
                (lambda (data) (= amount (apply + (map * data denomination-list))))
                (accumulate
                    (lambda (a-list b-list)
                        (flatmap
                            (lambda (a) (map (lambda (b) (cons a b)) b-list))
                            a-list))
                    (list '())
                    (map
                        (lambda (c) (enumerate-interval 0 c))
                        (map (lambda (d) (floor (/ amount d))) denomination-list))))))

           

这是用纯函数式的编程风格实现的方法，还是那函数式编程的三大件：filter、map、accumulate。这里没有使用scheme自带的reduce而是用了书上定义的accumulate是有原因的，因为accumulate是用递归实现的，而reduce我猜测MIT-scheme是用迭代实现的，这里用accumulate能保证映射后结果的次序问题，而一旦使用了reduce则保证不了，从而导致错误。其他的过程像enumerate-interval，flatmap等等都在之前的文章中出现过了，书上也有，就不再放代码了。

然后是使用非函数式编程对上面代码的一点改进，效率会高一点。首先要定义一个核心的过程，嵌套映射：

; 定义嵌套映射
(define (nested-map mapping op keys-list)
    (define (rec keys-list args)
        (if (null? keys-list)
            (apply op (reverse args))
            (mapping
                (lambda (key)
                    (rec (cdr keys-list) (cons key args)))
                (car keys-list))))
    (rec keys-list '()))

           

这里使用递归的方式实现了对与映射的嵌套，映射的种类由mapping参数传入，而keys-list则是由映射的基表所组成的表，即向量空间，这个表中的元素是所对应的每一层映射的基表。

有了它就可以改写上面的方法了，于是有了第二种效率更高一点的做法：

; 方法2 循环嵌套
(define (count-change-2 amount denomination-list)    
    (let ((count 0))
        (define (count-inc! . b)
            (if (= amount (apply + (map * b denomination-list)))
                    (set! count (+ count 1))))        
        (nested-map
            for-each
            count-inc!
            (map
                (lambda (c) (enumerate-interval 0 c))
                (map (lambda (d) (floor (/ amount d))) denomination-list)))
        count))

           

虽然效率有那么一点提高，但是这里使用了局部变量，因此已经不再属于函数式编程了。但是基本的思路还是没改变：先枚举，再筛选。