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