本文共 6276 字，大约阅读时间需要 20 分钟。
练习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/21 ]=> (fold-left / 1 (list 1 2 3));Value: 1/61 ]=> (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: 101 ]=> (fold-left + 0 (list 1 2 3 4));Value: 101 ]=> (fold-right * 1 (list 1 2 3 4));Value: 241 ]=> (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 01 0 0 0 0 0 0 10 0 0 1 1 0 0 00 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)倍
转载地址：http://kovbi.baihongyu.com/