CG@CPPBLOG

/*=========================================*/
随笔 - 76, 文章 - 39, 评论 - 137, 引用 - 0
数据加载中……

我的SICP习题答案(2.27~2.32)

2.27
(define (deep-reverse lst)
  (define (iter lst-o lst-d)
    (cond ((null? lst-o) 
           lst-d)
          ((not (pair? (car lst-o))) 
           (iter (cdr lst-o)
                 (cons (car lst-o) lst-d)))
          (else 
           (iter (cdr lst-o) 
                 (cons (deep-reverse (car lst-o))
                       lst-d)))))
  (iter lst null))

2.28
(define (fringe x)
  (define (iter tree lst)
    (cond ((null? tree) lst)
          ((not (pair? tree)) (cons tree lst))
          (else (iter (car tree) (iter (cdr tree) lst)))))
  (iter x null))

2.30
(define (square-tree- x)
  (cond ((null? x) null)
        ((not (pair? x)) (* x x))
        (else (cons (square-tree- (car x))
                    (square-tree- (cdr x))))))
(define (square-tree x)
  (map (lambda(subtree)
         (if (pair? subtree)
             (square-tree subtree)
             (* subtree subtree)))
       x))

2.31
(define (tree-map proc tree)
  (map (lambda(subtree)
         (if (pair? subtree)
             (tree-map proc subtree)
             (proc subtree)))
       tree))
(define (square-tree+ tree)
  (tree-map (lambda(x) (* x x)) tree))

2.32
(define (subsets s)
  (if (null? s)
      (list null)
      (let ((rest (subsets (cdr s))))
        (append rest (map (lambda(x) (cons (car s) x)) rest)))))

和换零钱问题的思路是一样的,对于一个集合的所有子集的集合,可以分为两部分,含有第一个元素和不含第一个元素的集合。而且含第一个元素的所有子集除去第一个元素,恰好正是所有不含第一个元素的子集。

也可以换个思路,对于集合A,设它可以表示为 (a1)∪(a2,...,an) ,而 (a2,...,an) 的所有子集的集合是 B=(B1,...Bm),那么可以证明A的所有子集的集合 C=B∪((A1)∪B1,(A1)∪B2,...,(A1)∪Bm);
证明:设 X 是 A 的一个子集,那么如果 a1∈X,那么 X
((A1)∪B1,(A1)∪B2,...,(A1)∪Bm),否则X∈B,所以
   
X∈C



posted on 2008-06-17 23:48 cuigang 阅读(1279) 评论(4)  编辑 收藏 引用 所属分类: Lisp/Scheme我的SICP答案

评论

# re: 我的SICP习题答案(2.27~2.32)  回复  更多评论   

2.27 2.28 想了好久都没想出来。。。
2011-08-24 18:26 | wangwangwar

# re: 我的SICP习题答案(2.27~2.32)  回复  更多评论   

2.32 确实太美妙了, 也知道和换零思路一样但是没有作出来。。。
2011-09-01 10:50 | wangwangwar

# re: 我的SICP习题答案(2.27~2.32)[未登录]  回复  更多评论   

函数式编程的思维方式真是累死人啊
2013-04-10 11:21 | wang

# re: 我的SICP习题答案(2.27~2.32)[未登录]  回复  更多评论   

(deep-reverse 1)运行失败
2015-01-17 20:05 | raof01

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理