SICP-2.2.3节练习
练习 2.33 - 2.43
练习 2.33：
Fill in the missing expressions to complete the following definitions of some basic list-manipulation operations as accumulations: (define (map p sequence) (accumulate (lambda (x y) <??>) nil sequence)) (define (append seq1 seq2) (accumulate cons <??> <??>)) (define (length sequence) (accumulate <??> 0 sequence))
我的解答：
(define (accumulate op initial sequence)
(if (null? sequence)
initial
(op (car sequence)
(accumulate op initial (cdr sequence)))))
(define (map p sequence)
(accumulate (lambda (x y) (cons (p x) y))
'()
sequence))
(define (append seq1 seq2)
(accumulate cons seq2 seq1))
(define (length sequence)
(accumulate (lambda (x y) (+ 1 y))
0
sequence))
练习 2.34：
Evaluating a polynomial in x at a given value of x can be formulated as an accumulation. We evaluate the polynomial
a_n r^n + a_(n-1) r^(n-1) + ... + a_1 r + a_0
using a well-known algorithm called Horner's rule, which structures the computation as
(... (a_n r + a_(n-1)) r + ... + a_1) r + a_0
In other words, we start with a_n, multiply by x, add a_(n-1), multiply by x, and so on, until we reach a_0.3
Fill in the following template to produce a procedure that evaluates a polynomial using Horner's
rule. Assume that the coefficients of the polynomial are arranged in a sequence, from a_0 through a_n.
(define (horner-eval x coefficient-sequence)
(accumulate (lambda (this-coeff higher-terms) <??>)
0
coefficient-sequence))
For example, to compute 1 + 3x + 5x^3 + x^(5) at x = 2 you would evaluate
(horner-eval 2 (list 1 3 0 5 0 1))
我的解答：
(define (horner-eval x coefficient-sequence)
(accumulate (lambda (this-coeff higher-terms)
(+ this-coeff (* x higher-terms)))
0
coefficient-sequence))
练习 2.35：
Redefine count-leaves from section 2-2-2 as an accumulation: (define (count-leaves t) (accumulate <??> <??> (map <??> <??>)))
我的解答：
(define (count-leaves t)
(accumulate (lambda (x y)
(+ (if (integer? x)
x
(count-leaves x))
y))
0
(map (lambda (x) (if (pair? x) x 1))
t)))
练习 2.36：
The procedure accumulate-n is similar to accumulate except that it takes as its third argument a
sequence of sequences, which are all assumed to have the same number of elements. It applies the
designated accumulation procedure to combine all the first elements of the sequences, all the second
elements of the sequences, and so on, and returns a sequence of the results. For instance, if s is a
sequence containing four sequences, ((1 2 3) (4 5 6) (7 8 9) (10 11 12)), then the value of
(accumulate-n + 0 s) should be the sequence (22 26 30). Fill in the missing expressions in the
following definition of accumulate-n:
(define (accumulate-n op init seqs)
(if (null? (car seqs))
nil
(cons (accumulate op init <??>)
(accumulate-n op init <??>))))
我的解答：
(define (accumulate-n op init seqs)
(if (null? (car seqs))
'()
(cons (accumulate op init (map (lambda (xs) (car xs)) seqs))
(accumulate-n op init (map (lambda (xs) (cdr xs)) seqs)))))
练习 2.37：
Suppose we represent vectors v = (v_i) as sequences of numbers, and matrices m = (m_(ij)) as
sequences of vectors (the rows of the matrix). For example, the matrix
+- -+
| 1 2 3 4 |
| 4 5 6 6 |
| 6 7 8 9 |
+- -+
is represented as the sequence ((1 2 3 4) (4 5 6 6) (6 7 8 9)). With this representation, we can use
sequence operations to concisely express the basic matrix and vector operations. These operations
(which are described in any book on matrix algebra) are the following:
(dot-product v w) returns {\sum_i v_i*w_i}
(matrix-*-vector m v) returns the vector t, where t_i = {\sum_j m_{ij}*v_j}
(matrix-*-matrix m n) returns the matrix p, where p_{ij} = {\sum_k m_{ik}*n_{kj}}
(transpose m) returns the matrix n, where n_{ij} = m_{ji}
We can define the dot product as4
(define (dot-product v w)
(accumulate + 0 (map * v w)))
Fill in the missing expressions in the following procedures for computing the other matrix
operations. (The procedure accumulate-n is defined in Exercise 2-36.)
(define (matrix-*-vector m v)
(map <??> m))
(define (transpose mat)
(accumulate-n <??> <??> mat))
(define (matrix-*-matrix m n)
(let ((cols (transpose n)))
(map <??> m)))
我的解答：
(define (accumulate op initial sequence)
(if (null? sequence)
initial
(op (car sequence)
(accumulate op initial (cdr sequence)))))
(define (accumulate-n op init seqs)
(if (null? (car seqs))
'()
(cons (accumulate op init (map (lambda (xs) (car xs)) seqs))
(accumulate-n op init (map (lambda (xs) (cdr xs)) seqs)))))
(define (dot-product v w)
(accumulate + 0 (map * v w)))
(define (matrix-*-vector m v)
(map (lambda (row) (dot-product row v))
m))
(define (transpose mat)
(accumulate-n cons '() mat))
(define (matrix-*-matrix m n)
(let ((cols (transpose n)))
(map (lambda (row) (matrix-*-vector cols row))
m)))
练习 2.38：
The accumulate procedure is also known as fold-right, because it combines the first element of the
sequence with the result of combining all the elements to the right. There is also a fold-left,
which is similar to fold-right, except that it combines elements working in the opposite direction:
(define (fold-left op initial sequence)
(define (iter result rest)
(if (null? rest)
result
(iter (op result (car rest))
(cdr rest))))
(iter initial sequence))
What are the values of
(fold-right / 1 (list 1 2 3))
(fold-left / 1 (list 1 2 3))
(fold-right list nil (list 1 2 3))
(fold-left list nil (list 1 2 3))
Give a property that op should satisfy to guarantee that fold-right and fold-left will produce the
same values for any sequence.
我的解答：
scheme@(guile-user)> (fold-right / 1 (list 1 2 3)) 3/2 scheme@(guile-user)> (fold-left / 1 (list 1 2 3)) 1/6 scheme@(guile-user)> (fold-right list '() (list 1 2 3)) (1 (2 (3 ()))) scheme@(guile-user)> (fold-left list '() (list 1 2 3)) (((() 1) 2) 3)
练习 2.39：
Complete the following definitions of reverse (Exercise 2-18) in terms of fold-right and fold-left from Exercise 2-38: (define (reverse sequence) (fold-right (lambda (x y) <??>) nil sequence)) (define (reverse sequence) (fold-left (lambda (x y) <??>) nil sequence))
我的解答：
(define (reverse1 sequence)
(fold-right (lambda (x y)
(append y (list x)))
'()
sequence))
(define (reverse2 sequence)
(fold-left (lambda (x y)
(cons y x))
'()
sequence))
练习 2.40：
Define a procedure unique-pairs that, given an integer n, generates the sequence of pairs (i,j) with 1 <= j< i <= n. Use unique-pairs to simplify the definition of prime-sum-pairs given above.
我的解答：
(define (prime? x)
(define (test divisor)
(cond ((> (* divisor divisor) x) #t)
((= 0 (remainder x divisor)) #f)
(else (test (+ divisor 1)))))
(test 2))
(define (enumerate-interval low high)
(if (> low high)
'()
(cons low (enumerate-interval (+ low 1) high))))
(define (accumulate op initial sequence)
(if (null? sequence)
initial
(op (car sequence)
(accumulate op initial (cdr sequence)))))
(define (flatmap proc seq)
(accumulate append '() (map proc seq)))
(define (prime-sum? pair)
(prime? (+ (car pair) (cadr pair))))
(define (make-pair-sum pair)
(list (car pair) (cadr pair) (+ (car pair) (cadr pair))))
(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：
Write a procedure to find all ordered triples of distinct positive integers i, j, and k less than or equal to a given integer n that sum to a given integer s.
我的解答：
(define (enumerate-interval low high)
(if (> low high)
'()
(cons low (enumerate-interval (+ low 1) high))))
(define (accumulate op initial sequence)
(if (null? sequence)
initial
(op (car sequence)
(accumulate op initial (cdr sequence)))))
(define (flatmap proc seq)
(accumulate append '() (map proc seq)))
(define (ordered-triples n)
(flatmap (lambda (i)
(map (lambda (x) (cons i x))
(flatmap (lambda (j)
(map (lambda (k) (list j k))
(enumerate-interval 1 (- j 1))))
(enumerate-interval 1 (- i 1)))))
(enumerate-interval 1 n)))
练习 2.42：
The “eight-queens puzzle” asks how to place eight queens on a chessboard so that no queen is in
check from any other (i.e., no two queens are in the same row, column, or diagonal). One possible
solution is shown in Figure 2-8. One way to solve the puzzle is to work across the board, placing a
queen in each column. Once we have placed k - 1 queens, we must place the kth queen in a position
where it does not check any of the queens already on the board. We can formulate this approach
recursively: Assume that we have already generated the sequence of all possible ways to place k - 1
queens in the first k - 1 columns of the board. For each of these ways, generate an extended set of
positions by placing a queen in each row of the kth column. Now filter these, keeping only the
positions for which the queen in the kth column is safe with respect to the other queens. This
produces the sequence of all ways to place k queens in the first k columns. By continuing this
process, we will produce not only one solution, but all solutions to the puzzle.
Figure 2.8: A solution to the eight-queens puzzle.
+---+---+---+---+---+---+---+---+
| | | | | | Q | | |
+---+---+---+---+---+---+---+---+
| | | Q | | | | | |
+---+---+---+---+---+---+---+---+
| Q | | | | | | | |
+---+---+---+---+---+---+---+---+
| | | | | | | Q | |
+---+---+---+---+---+---+---+---+
| | | | | Q | | | |
+---+---+---+---+---+---+---+---+
| | | | | | | | Q |
+---+---+---+---+---+---+---+---+
| | Q | | | | | | |
+---+---+---+---+---+---+---+---+
| | | | Q | | | | |
+---+---+---+---+---+---+---+---+
We implement this solution as a procedure queens, which returns a sequence of all solutions to the
problem of placing n queens on an n*n chessboard. Queens has an internal procedure queen-cols that
returns the sequence of all ways to place queens in the first k columns of the board.
(define (queens board-size)
(define (queen-cols k)
(if (= k 0)
(list empty-board)
(filter
(lambda (positions) (safe? k positions))
(flatmap
(lambda (rest-of-queens)
(map (lambda (new-row)
(adjoin-position new-row k rest-of-queens))
(enumerate-interval 1 board-size)))
(queen-cols (- k 1))))))
(queen-cols board-size))
In this procedure rest-of-queens is a way to place k - 1 queens in the first k - 1 columns, and
new-row is a proposed row in which to place the queen for the kth column. Complete the program by
implementing the representation for sets of board positions, including the procedure
adjoin-position, which adjoins a new row-column position to a set of positions, and empty-board,
which represents an empty set of positions. You must also write the procedure safe?, which
determines for a set of positions, whether the queen in the kth column is safe with respect to the
others. (Note that we need only check whether the new queen is safe—the other queens are already
guaranteed safe with respect to each other.)
我的解答：
(define (enumerate-interval low high)
(if (> low high)
'()
(cons low (enumerate-interval (+ low 1) high))))
(define (accumulate op initial sequence)
(if (null? sequence)
initial
(op (car sequence)
(accumulate op initial (cdr sequence)))))
(define (flatmap proc seq)
(accumulate append '() (map proc seq)))
(define (queens board-size)
(define empty-board '())
(define (safe? k positions)
(define (safe-pairs? pair1 pair2)
(let ((row1 (car pair1))
(row2 (car pair2))
(col1 (cdr pair1))
(col2 (cdr pair2)))
(and (not (= row1 row2))
(not (= (abs (- row1 row2))
(abs (- col1 col2)))))))
(let ((k-pair (car positions))
(rest-pairs (cdr positions)))
(accumulate (lambda (x y) (and x y))
#t
(map (lambda (pair) (safe-pairs? pair k-pair))
rest-pairs))))
(define (adjoin-position new-row k rest-of-queens)
(cons (cons new-row k)
rest-of-queens))
(define (queen-cols k)
(if (= k 0)
(list empty-board)
(filter (lambda (positions) (safe? k positions))
(flatmap (lambda (rest-of-queens)
(map (lambda (new-row)
(adjoin-position new-row k rest-of-queens))
(enumerate-interval 1 board-size)))
(queen-cols (- k 1))))))
(queen-cols board-size))
练习 2.43：
Louis Reasoner is having a terrible time doing Exercise 2-42. His queens procedure seems to work,
but it runs extremely slowly. (Louis never does manage to wait long enough for it to solve even the
6*6 case.) When Louis asks Eva Lu Ator for help, she points out that he has interchanged the order
of the nested mappings in the flatmap, writing it as
(flatmap
(lambda (new-row)
(map (lambda (rest-of-queens)
(adjoin-position new-row k rest-of-queens))
(queen-cols (- k 1))))
(enumerate-interval 1 board-size))
Explain why this interchange makes the program run slowly. Estimate how long it will take Louis's
program to solve the eight-queens puzzle, assuming that the program in Exercise 2-42 solves the
puzzle in time T.
这个不会，以后再做。
Feb 23, 2020 07:54:46 PM
Gradually, you have realized that your choice of home must have some freshening together. It can be as quick as sweeping in the floors, dusting that furniture or else your home requires a major maintaining session. Then again, you have a rather busy schedule and you just don’t enjoy the time or the actual to you want to keep home wash. Maybe you might rather spend time with family members or acquaintances. Whatever possible may end up, we could actually help. Our power team of competent cleaners could actually help save one from days or days of performing boring and even tedious loved ones chores.
Jan 13, 2024 10:48:53 PM
Instantly this web site will irrefutably frequently end up being notable regarding all weblog consumers, due to diligent reviews as well as checks