sicp习题2.2节尝试解答

习题2.17,直接利用list-ref和length过程

(define (last-pair items)

  (list (list-ref items (- (length items) 1))))

习题2.18,采用迭代法

(define (reverse-list items)

  (define (reverse-iter i k)

    (if (null? i) k (reverse-iter (cdr i) (cons (car i) k))))

  (reverse-iter items ()))

习题2.20，如果两个数的奇偶相同，那么他们的差模2等于0，根据这一点可以写出：

(define (same-parity a . b)

  (define (same-parity-temp x y)

  (cond ((null? y) y)

        ((= (remainder (- (car y) x) 2) 0)

         (cons (car y) (same-parity-temp x (cdr y))))

        (else

           (same-parity-temp x (cdr y)))))

  (cons a (same-parity-temp a b)))

利用了基本过程remainder取模

习题2.21，递归方式：

(define (square-list items)

  (if (null? items)

      items 

      (cons (square (car items)) (square-list (cdr items)))))

利用map过程：

  (map square items))

习题2.23，这与ruby中的each是一样的意思，将操作应用于集合的每个元素：

(define (for-each proc items)

  (define (for-each-temp proc temp items)

      #t

      (for-each-temp proc (proc (car items)) (cdr items))))

  (for-each-temp proc 0 items))

最后返回true

习题2.24，盒子图就不画了，麻烦，解释器输出：

welcome to drscheme, version 360.

language: standard (r5rs).

> (list 1 (list 2 (list 3 4)))

(1 (2 (3 4)))

树形状应当是这样

习题2.25，

第一个list可以表示为(list 1 3 (list 5 7) 9)

因此取7的操作应当是：

(car (cdr (car (cdr (cdr (list 1 3 (list 5 7) 9))))))

第二个list表示为:(list (list 7))

因此取7操作为：

(car (car (list (list 7))))

第三个list可以表示为：

(list 1 (list 2 (list 3 (list 4 (list 5 (list 6 7))))))

因此取7的操作为：

(define x (list 1 (list 2 (list 3 (list 4 (list 5 (list 6 7)))))))

(car (cdr (car (cdr (car (cdr (car (cdr (car (cdr (car (cdr x))))))))))))

够恐怖！-_-

习题2.26，纯粹的动手题，就不说了

习题2.27，在reverse的基础上进行修改，同样采用迭代，比较难理解：

(define (deep-reverse x)

  (define (reverse-iter rest result)

    (cond ((null? rest) result)

          ((not (pair? (car rest)))

           (reverse-iter (cdr rest)

                 (cons (car rest) result)))

          (else

                 (cons (deep-reverse (car rest)) result)))

           ))

  (reverse-iter x ()))

习题2.28，递归，利用append过程就容易了：

(define (finge x)

  (cond ((pair? x) (append (finge (car x)) (finge (cdr x))))

        ((null? x) ())

        (else (list x))))

习题2.29，这一题很明显出来的二叉活动体也是个层次性的树状结构

1）很简单，利用car,cdr

(define (left-branch x)

  (car x))

(define (right-branch x)

  (car (cdr x)))

(define (branch-length b)

  (car b))

(define (branch-structure b)

  (car (cdr b)))

2）首先需要一个过程用于求解分支的总重量：

(define (branch-weight branch)

  (let ((structure (branch-structure branch)))

    (if (not (pair? structure))

        structure

        (total-weight structure))))

(define (total-weight mobile)

  (+ (branch-weight (left-branch mobile))

     (branch-weight (right-branch mobile))))

利用这个过程写出balanced?过程：

(define (torque branch)

  (* (branch-length branch) (branch-weight branch)))

(define (balanced? mobile)

  (= (torque (left-branch mobile))

     (torque (right-branch mobile))))

3)选择函数和定义函数提供了一层抽象屏蔽，其他函数都是建立在这两个基础上，因此需要改变的仅仅是selector函数：

(define (right-branch mobile) (cdr mobile))

(define (branch-structure branch) (cdr branch))

习题2.30：

(define (square-tree tree)

  (cond ((null? tree) tree)

        ((not (pair? tree)) (square tree))

           (cons (square-tree (car tree)) (square-tree (cdr tree))))))

(define (square-tree2 tree)

  (map (lambda(x)

         (if (pair? x)

             (square-tree x)

             (square x))) tree))

习题2.31，进一步抽象出map-tree，与map过程类似，将proc过程作用于树的每个节点：

(define (tree-map proc tree)

        ((not (pair? tree)) (proc tree))

           (cons (tree-map proc (car tree)) (tree-map proc (cdr tree))))))

(define (square-tree3 tree)

  (tree-map square tree))

习题2.32，通过观察，rest总是cdr后的子集，比如对于(list 1 2 3)，连续cdr出来的是：

(2 3)

(3)

()

其他的5个子集应该是car结果与这些子集组合的结果，因此：

(define (subsets s)

  (if (null? s)

      (list s)

      (let ((rest (subsets (cdr s))))

        (append rest (map (lambda(x) (cons (car s) x)) rest)))))

<a></a>

2.32, 跟楼主思路一样，可惜出不了结果

(define (subsets s)

(if (null? s) (list s)

(let ((rest (subsets (cdr s))))

(append rest (map (lambda (x) (cons (car s) x)) rest)))))

(subsets (list 1 2 3))

welcome to drscheme, version 371 [3m].

language: advanced student.

(shared ((-2- (list 3)) (-4- (list 2)) (-6- (cons 2 -2-)))

(list empty -2- -4- -6- (list 1) (cons 1 -2-) (cons 1 -4-) (cons 1 -6-)))

&gt;

文章转自庄周梦蝶  ，原文发布时间5.17