欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

SICP学习笔记 2.2.3 序列作为一种约定的接口

程序员文章站 2024-01-10 18:01:52
...

    练习2.33

;; map过程即为使用过程p作用x, 然后再合并作用y后的结果
(define (map p sequence)
  (accumulate (lambda (x y) (cons (p x) y)) '() sequence))

;; append过程为合并两个列表, 则初始值为空表, 要传入的列表为枚举两个参数列表的元素组成的列表
(define (append seq1 seq2)
  (accumulate cons '() (enumerate-tree (list seq1 seq2))))
  
;; length过程即为在y参数不为空时将长度递增
(define (length sequence)
  (accumulate (lambda (x y) (+ 1 y))  0 sequence))

 

    练习2.34

(define (horner-eval x coefficient-sequence)
  (accumulate (lambda (this-coeff higher-terms) (+ this-coeff (* x higher-terms)))
	            0 coefficient-sequence))
 

    练习2.35

(define (count-leaves tree)
  (accumulate + 0 (map (lambda (x) 1) (enumerate-tree tree))))

 

    练习2.36

;; 这里关键是从序列的序列中依次取第一个、第二个、第N个元素
;; 则应首先枚举序列中的每个序列, 检测非空, 分别取首元素
;; 即(map car (filter pair? seqs))
(define (accumulate-n op init seqs)
  (if (null? (car seqs))
      '()
      (cons (accumulate op init (map car (filter pair? seqs)))
	          (accumulate-n op init (map cdr (filter pair? seqs))))))	 
 

    练习2.37

;; 首先定义扩充的map,可以接收多个序列参数        
(define (new-map proc item1 item2)
  (define items (list item1 item2))
  (accumulate-n proc 1 items))
(define (dot-product v w)
  (accumulate + 0 (new-map * v w))) 

;; 矩阵与向量的乘法即为矩阵中的每一行与向量做dot-product  
(define (matrix-*-vector m v)
  (map (lambda (w) (dot-product v w)) m))  
  
;; 矩阵转置即为分别取矩阵相同行的相同列组成新的行
(define (transpose mat)
  (accumulate-n cons '() mat))
;; 矩阵乘法即为第一个矩阵的转置与第二个矩阵中的每一行做matrix-*-vector
(define (matrix-*-matrix m n)
  (let ((cols (transpose n)))
    (map (lambda (w) (matrix-*-vector cols w)) m)))

 

    练习2.38

(define (fold-right op initial sequence)
  (define (iter result rest)
    (if (null? rest)
      	result
      	(op (car rest)
      	    (iter result (cdr rest)))))
  (iter initial sequence))

1 ]=> (fold-right / 1 (list 1 2 3))  
;Value: 3/2

1 ]=> (fold-left / 1 (list 1 2 3))
;Value: 1/6

1 ]=> (fold-right list '() (list 1 2 3))
;Value : (1 (2 (3 ())))

1 ]=> (fold-left list '() (list 1 2 3))
;Value : (((() 1) 2) 3)

;; 因为这两种方式的不同之处在于对结果的累加方式,因为如果对于op,如果满足交换律则两种方式处理的结果相同
1 ]=> (fold-right + 0 (list 1 2 3 4))
;Value: 10
1 ]=> (fold-left + 0 (list 1 2 3 4))
;Value: 10

1 ]=> (fold-right * 1 (list 1 2 3 4))
;Value: 24
1 ]=> (fold-left * 1 (list 1 2 3 4))
;Value: 24
 

    练习2.39

(define (reverse sequence)
  (fold-right (lambda (x y) (append y (list x))) '() sequence))

(define (reverse sequence)
  (fold-left (lambda (x y) (append (list y) x)) '() sequence))
 

    练习2.40

(define (unique-pairs n)
  (flatmap (lambda (i) (map (lambda (j) (list i j))
			                      (enumerate-interval 1 (- i 1))))
	         (enumerate-interval 1 n)))
(define (prime-sum-pairs n)
  (map make-pair-sum (filter prime-sum? (unique-pairs n))))

 

    练习2.41

;; 构建三元组即为在二元组的基础上进行组合
;; 如n为6的三元组即为6与5的二元组的组合
;; 即 (cons i (unique-pairs (- i 1))
(define (unique-pairs-new n)
  (flatmap (lambda (i) (map (lambda (j) (cons i j))
			                      (unique-pairs (- i 1))))
	         (enumerate-interval 1 n)))

1 ]=> (unique-pairs-new 6)
;Value : ((3 2 1) 
          (4 2 1) (4 3 1) (4 3 2) 
          (5 2 1) (5 3 1) (5 3 2) 
          (5 4 1) (5 4 2) (5 4 3) 
          (6 2 1) 
          (6 3 1) (6 3 2) 
          (6 4 1) (6 4 2) (6 4 3)
          (6 5 1) (6 5 2) (6 5 3) (6 5 4))	         
;; 过滤三元组的过程
(define (s-sum-pairs n)
  (filter s-sum? (unique-pairs-new n)))
(define S 8)
(define (s-sum? pair)
  (= S (accumulate + 0 pair)))
  
1 ]=> (s-sum-pairs 6)
;Value : ((4 3 1) (5 2 1))
 

    练习2.42

;; 首先定义棋盘
;; 构造棋盘的一列
(define (matrix-seqs seqs i n)
  (if (< i n)
      (matrix-seqs (cons 0 seqs) (+ i 1) n)
      seqs))
;; 在已有的棋盘上追加n列
(define (matrix-iter matrix i n)
  (if (< i n)
      (matrix-iter (cons (matrix-seqs '() 0 n) matrix) (+ i 1) n)
      matrix))
;; 构造n阶棋盘
(define (matrix-n n)
  (matrix-iter '() 0 n))
1 ]=> (matrix-n 4)
;Value : ((0 0 0 0) (0 0 0 0) (0 0 0 0) (0 0 0 0))	

;; 然后构造在已有格局的基础上追加一列的过程
;; 以4阶棋盘为例
;; 0 0 0 0
;; 1 0 0 0
;; 0 0 0 0
;; 0 1 0 0
;; 此时有n=4, k=3
;; 则新的格局应为(已经安全的前k-1列 + 需要循环检测每行安全性的第k列 + 暂时为空值的后(n-k)列

;; 构造为空值的后(n-k)列
(define (cdr-rest n k)
  (if (= k n)
	  '()
	  (cons (matrix-seqs '() 0 n) (cdr-rest n (+ k 1)))))

;; 构造需要检测的第k列, 其中第row行的值设为1
(define (make-rest n row)
  (define x (- (+ n 1) row))
  (define (rest-iter seqs i)
    (if (> i n)
	      seqs
	      (if (= i x)
	          (rest-iter (cons 1 seqs) (+ i 1))
	          (rest-iter (cons 0 seqs) (+ i 1)))))
  (rest-iter '() 1))
  
;; 将三者组合在一起构造出新的格局
(define (adjoin-position n row k rest)
  (define cdr-postion (cons (make-rest n row) (cdr-rest n k)))
  (define x (- k 1))
  (define (iter i result)
    (if (> i 0)
	      (iter (- i 1) (cons (list-ref rest (- i 1)) result))
	      result))
  (iter x cdr-postion))   
  
1 ]=> rest
;Value : ((0 1 0 0) (0 0 0 1) (1 0 0 0) (0 0 0 0)) 

1 ]=> (adjoin-position 4 1 4 rest)
;Value : ((0 1 0 0) (0 0 0 1) (1 0 0 0) (1 0 0 0))

1 ]=> (adjoin-position 4 4 4 rest)
;Value : ((0 1 0 0) (0 0 0 1) (1 0 0 0) (0 0 0 1))
     
;; 最后完成安全性的检测

;; 在一列中查找皇后所在的行数
(define (find i seqs)
  (if (= (list-ref seqs (- i 1)) 1)
	    i
	    (find (+ i 1) seqs)))
	    
;; 根据新格局中新添加的皇后的位置与已有的皇后位置进行冲突检测
(define (safe? n k positions)
  (define seqs-k (list-ref positions (- k 1)))
  (define row-k (find 1 seqs-k))
  
  (define (iter i)
    (define seqs-i (list-ref positions (- i 1)))
    (define row-i (find 1 seqs-i))
    (if (= i k)
	      #t
	      (if (= row-i row-k) ;; 相同行
	          #f
	          (if (or (= (+ i row-i) (+ k row-k))
		                (= (- i row-i) (- k row-k)))  ;; 对角线
		            #f
		            (iter (+ i 1))))))
  (iter 1))
  
;; 因此可以使用如下过程进行求解
(define (queens board-size)
  (define empty-board (matrix-n board-size))
  (define (queen-cols k)
    (if (= k 0)
	      (list empty-board)
	      (filter
	        (lambda (positions) (safe? board-size k positions))
	        (flatmap
	          (lambda (rest-of-queens)
	            (map (lambda (new-row)
		                 (adjoin-position board-size new-row k rest-of-queens))
		               (enumerate-interval 1 board-size)))
	          (queen-cols (- k 1))))))
  (queen-cols board-size))
  
1 ]=> (queens 4)
;Value : (((0 1 0 0) (0 0 0 1) (1 0 0 0) (0 0 1 0)) ((0 0 1 0) (1 0 0 0) (0 0 0 1) (0 1 0 0)))

;; 这里序列中的序列代表的是棋盘中的一列, 转换后即为
0 0 1 0    0 1 0 0
1 0 0 0    0 0 0 1
0 0 0 1    1 0 0 0
0 1 0 0    0 0 1 0
 

    练习2.43

;; 交换前
;; 求解(queen n)时会递归调用(queen-cols n)
;; 直到k=0,得到n阶空棋盘
;; 然后在第一列的第i行添加皇后作为新的格局, 共n种格局, 保留通过安全检测的格局
;; 然后依次处理第i列, 共n列
;; 所以这里共调用queen-cols过程n次

;; 交换后
;; 求解(queen n)时会递归调用(queen-cols n)
;; 而(queen-cols n)过程将递归调用嵌套在了嵌套映射中
;; 因此queen-cols将会被调用n^n次

;; 所以Louis的方法将会是原来的N^(N-1)倍