781
sicp習題2.2節嚐試解答
習題2.17,直接利用list-ref和length過程
習題2.18,采用迭代法
習題2.21，遞歸方式：
習題2.23，這與ruby中的each是一樣的意思，將操作應用於集合的每個元素：
習題2.24，盒子圖就不畫了，麻煩，解釋器輸出：
第一個list可以表示為(list 1 3 (list 5 7) 9)
因此取7的操作應當是：
因此取7操作為：
第三個list可以表示為：
習題2.26，純粹的動手題，就不說了
習題2.27，在reverse的基礎上進行修改，同樣采用迭代，比較難理解：
習題2.28，遞歸，利用append過程就容易了：
習題2.29，這一題很明顯出來的二叉活動體也是個層次性的樹狀結構
1）很簡單，利用car,cdr
2）首先需要一個過程用於求解分支的總重量：
利用這個過程寫出balanced?過程：
3)選擇函數和定義函數提供了一層抽象屏蔽，其他函數都是建立在這兩個基礎上，因此需要改變的僅僅是selector函數：
習題2.30：
習題2.31，進一步抽象出map-tree，與map過程類似，將proc過程作用於樹的每個節點：
習題2.32，通過觀察，rest總是cdr後的子集，比如對於(list 1 2 3)，連續cdr出來的是：
(2 3)
(3)
()
其他的5個子集應該是car結果與這些子集組合的結果，因此：
(define (last-pair items)
(list (list-ref items (- (length items) 1))))
(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 (reverse-iter i k)
(if (null? i) k (reverse-iter (cdr i) (cons (car i) k))))
(reverse-iter items ()))
(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取模(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)))
習題2.21，遞歸方式：
(define (square-list items)
(if (null? items)
items
(cons (square (car items)) (square-list (cdr items)))))
利用map過程：(if (null? items)
items
(cons (square (car items)) (square-list (cdr items)))))
(define (square-list items)
(map square items))
(map square items))
習題2.23，這與ruby中的each是一樣的意思，將操作應用於集合的每個元素：
(define (for-each proc items)
(define (for-each-temp proc temp items)
(if (null? items)
#t
(for-each-temp proc (proc (car items)) (cdr items))))
(for-each-temp proc 0 items))
最後返回true(define (for-each-temp proc temp items)
(if (null? items)
#t
(for-each-temp proc (proc (car items)) (cdr items))))
(for-each-temp proc 0 items))
習題2.24，盒子圖就不畫了，麻煩，解釋器輸出：
Welcome to DrScheme, version 360.
Language: Standard (R5RS).
> (list 1 (list 2 (list 3 4)))
(1 (2 (3 4)))
樹形狀應當是這樣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))))))))))))
夠恐怖！-_-(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
(reverse-iter (cdr rest)
(cons (deep-reverse (car rest)) result)))
))
(reverse-iter x ()))
(define (reverse-iter rest result)
(cond ((null? rest) result)
((not (pair? (car rest)))
(reverse-iter (cdr rest)
(cons (car rest) result)))
(else
(reverse-iter (cdr rest)
(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))))
(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)))
(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))))
(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))))
(* (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))
(define (branch-structure branch) (cdr branch))
習題2.30：
(define (square-tree tree)
(cond ((null? tree) tree)
((not (pair? tree)) (square tree))
(else
(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))
(cond ((null? tree) tree)
((not (pair? tree)) (square tree))
(else
(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)
(cond ((null? tree) tree)
((not (pair? tree)) (proc tree))
(else
(cons (tree-map proc (car tree)) (tree-map proc (cdr tree))))))
(define (square-tree3 tree)
(tree-map square tree))
(cond ((null? tree) tree)
((not (pair? tree)) (proc tree))
(else
(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)))))
(if (null? s)
(list s)
(let ((rest (subsets (cdr s))))
(append rest (map (lambda(x) (cons (car s) x)) rest)))))
評論
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-)))
>
(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-)))
>
文章轉自莊周夢蝶 ，原文發布時間5.17
最後更新：2017-05-17 14:01:50