SICP学习笔记 2.2.2 层次性结构

    练习2.24

;; 嵌套结构的list
1 ]=> (list 1 (list 2 (list 3 4)))
;Value : (1 (2 (3 4)))

 *
/ \
1  *
 /   \
 2    * 
    /   \
    3   4

 

    练习2.25

;; (1 3 (5 7) 9)
1 ]=> (define list1 (list 1 3 (list 5 7) 9))
1 ]=> list1
;Value : (1 3 (5 7) 9)

1 ]=> (car (cdr (car (cdr (cdr list1)))))
;Value: 7

;; ((7))
1 ]=> (define list1 (list (list 7)))
1 ]=> list1
;Value : ((7))

1 ]=> (car (car list1))
;Value: 7

;; (1 (2 (3 (4 (5 (6 7))))))
1 ]=> (define list1 (list 1 (list 2 (list 3 (list 4 (list 5 (list 6 7)))))))
1 ]=> list1
;Value : (1 (2 (3 (4 (5 (6 7))))))

1 ]=> (car (cdr (car (cdr (car (cdr (car (cdr (car (cdr (car (cdr list1))))))))))))
;Value: 7

 

     练习2.26

1 ]=> (append x y)
;Value : (1 2 3 4 5 6)

1 ]=> (cons x y)
;Value : ((1 2 3) 4 5 6)

1 ]=> (list x y)
;Value : ((1 2 3) (4 5 6))

    

    练习2.27

(define (deep-reverse items)
  (cond ((null? items) '())
	      ((pair? (car items))
	       (append (deep-reverse (cdr items))
		             (list (deep-reverse (car items)))))
	      (else
	       (append (deep-reverse (cdr items))
		             (list (car items))))))

 

    练习2.28

;; 采用递归的方式,如果是序对就将左子树和右子树的结果拼接,否则直接拼接
(define (fringe items)
  (define (frings-iter things answer)
    (cond ((null? things) answer)
	        ((pair? things)
	         (append (frings-iter (car things) answer)
		               (frings-iter (cdr things) answer)))
	        (else
	         (append answer (list things)))))
  (frings-iter items '()))

 

    练习2.29

;; a
(define (left-branch mobile)
  (car mobile))
(define (right-branch mobile)
  (cdr mobile))
(define (branch-length branch)
  (car branch))
(define (branch-structure branch)
  (car (cdr branch)))
  
;; b
;; 先检查是不是二叉活动体,如果是则递归求两个分支的重量
;; 再检查分支的structure是否仍然是活动体, 如果是则递归求structure的重量
;; 最后对于最简单的分支情况直接相加重量
(define (total-weight mobile)
  (define (mobile-flag m)
    (pair? (left-branch m)))
  (define (branch-flag m)
    (pair? (branch-structure m)))
  (define (total-weight-iter m tw)
    (cond ((null? m) tw)
	        ((mobile-flag m) (+ (total-weight-iter (left-branch m) tw)
			                        (total-weight-iter (right-branch m) tw)))
	        ((branch-flag m) (+ (total-weight-iter (branch-structure m) tw)))
	        (else (+ tw (branch-structure m)))))
  (total-weight-iter mobile 0))

;; 或者可以将活动体的重量看做是两个分支重量之和
;; 但是在对分支求重量时仍然要区分是否还有分支
(define (total-weight mobile)
  (if (pair? (left-branch mobile))
      (+ (branch-weight (left-branch mobile)) 
	       (branch-weight (right-branch mobile)))
      (branch-weight mobile))) 
(define (branch-weight branch)
  (let ((structure
	       (if (null? (right-branch branch))
	           (left-branch branch)
	           (branch-structure branch))))
    (if (pair? structure)
	      (branch-weight structure)
	      structure)))
;; c
;; 首先定义分支的力矩,依据其是否有分支分别处理
(define (branch-value branch)
  (if (null? (right-branch branch))
      (* (branch-length (left-branch branch)) (branch-weight branch))
      (* (branch-length branch) (branch-weight branch))))

;; 然后实现活动体的检测过程:两个分支平衡且两个分支的力矩相等
(define (check-balance mobile)
  (if (pair? (left-branch mobile))
      (and (check-balance (left-branch mobile))
	         (check-balance (car (right-branch mobile)))
	         (= (branch-value (left-branch mobile))
	            (branch-value (right-branch mobile))))
      #t))
  
;; d
;; 需要对structure过程修改
(define (branch-structure branch)
  ;;(car (cdr branch)))
  (cdr branch))
  
(define (check-balance mobile)
  (if (pair? (left-branch mobile))
      (and (check-balance (left-branch mobile))
	         ;;(check-balance (car (right-branch mobile)))
	         (check-balance (right-branch mobile))
	         (= (branch-value (left-branch mobile))
	            (branch-value (right-branch mobile))))
      #t))
;; 验证  
(define mtest 
  (make-mobile (make-branch 3 4)
			         (make-branch 2 6)))
1 ]=> (total-weight mtest)
;Value: 10			         
		
1 ]=> (check-balance mtest)
;Value: #t	

 

    练习2.30

(define (square-tree tree)
  (cond ((null? tree) '())
	      ((not (pair? tree)) (square tree))
	      (else (cons (square-tree (car tree))
		                (square-tree (cdr tree))))))
(define (map-square-tree tree)
  (map (lambda (sub-tree)
	        (if (pair? sub-tree)
	            (map-square-tree sub-tree)
	            (square sub-tree)))
       tree))
       
1 ]=> (square-tree (list 1 (list 2 (list 3 4) 5) (list 6 7)))
;Value : (1 (4 (9 16) 25) (36 49))

1 ]=> (map-square-tree (list 1 (list 2 (list 3 4) 5) (list 6 7)))
;Value : (1 (4 (9 16) 25) (36 49))

 

    练习2.31

(define (tree-map fun tree)
  (map (lambda (sub-tree)
      	 (if (pair? sub-tree)
      	     (tree-map fun sub-tree)
      	     (fun sub-tree)))
       tree))
       
1 ]=> (define (square-tree-test tree) (tree-map square tree))
;Value : square-tree-test

1 ]=> (square-tree-test (list 1 (list 2 (list 3 4) 5) (list 6 7)))
;Value : (1 (4 (9 16) 25) (36 49))

 

    练习2.32

;; 仿照换零钱的例子
;; rest取不包含(car s)元素的所有剩余元素的组合
;; 则应加上(car s)元素与所有剩余元素的组合
(define (subsets s)
  (if (null? s)
      (list '())
      (let ((rest (subsets (cdr s))))
	      (append rest (map (lambda (r) (append (list (car s)) r)) rest)))))
	
1 ]=> (subsets s)
;Value : (() (3) (2) (2 3) (1) (1 3) (1 2) (1 2 3))