SICP-2.2.1节练习
SICP-2.2.3节练习

SICP-2.2.2节练习

lispor posted @ Mar 05, 2011 03:13:28 PM in Scheme with tags SICP , 1795 阅读

练习 2.24 - 2.32

练习 2.24:
Suppose we evaluate the expression (list 1 (list 2 (list 3 4))). Give the result printed by the
interpreter, the corresponding box-and-pointer structure, and the interpretation of this as a tree
(as in Figure 2-6).
我的解答:
解释器打印如下:
scheme@(guile-user)> (list 1 (list 2 (list 3 4)))
(1 (2 (3 4)))
盒子指针结构如下:
(1 (2 (3 4))):
+---+---+         +---+---+
|   |   |         |   |  /|
| o | o-+-------->+ o | / |
| | |   |         | | |/  |
+-+-+---+         +-+-+---+
  |                 |
  |                 |
  v                 v
+-+-+             +-+-+---+           +---+---+
|   |             |   |   |           |   |  /|
| 1 |             | o | o-+---------->| o | / |
|   |             | | |   |           | | |/  |
+---+             +-+-+---+           +-+-+---+
                    |                   |
                    |                   |
                    v                   v
                  +-+-+               +-+-+---+         +---+---+
                  |   |               |   |   |         |   |  /|
                  | 2 |               | o | o-+-------->+ o | / |
                  |   |               | | |   |         | | |/  |
                  +---+               +-+-+---+         +-+-+---+
                                        |                 |
                                        |                 |
                                        v                 v
                                      +-+-+             +-+-+
                                      |   |             |   |
                                      | 3 |             | 4 |
                                      |   |             |   |
                                      +---+             +---+
 
练习 2.25:
Give combinations of cars and cdrs that will pick 7 from each of
the following lists:
(1 3 (5 7) 9)
((7))
(1 (2 (3 (4 (5 (6 7))))))
我的解答:
scheme@(guile-user)> (car (cdr (car (cdr (cdr '(1 3 (5 7) 9))))))
7
scheme@(guile-user)> (car (car '((7))))
7
scheme@(guile-user)> (car (cdr (car (cdr (car (cdr (car (cdr (car (cdr (car (cdr '(1 (2 (3 (4 (5 (6 7))))))))))))))))))
7
 
练习 2.26:
Suppose we define x and y to be two lists:
(define x (list 1 2 3))
(define y (list 4 5 6))
What result is printed by the interpreter in response to evaluating each of the following
expressions:
(append x y)
(cons x y)
(list x y)
我的解答:
scheme@(guile-user)> (define x (list 1 2 3))
scheme@(guile-user)> (define y (list 4 5 6))
scheme@(guile-user)> (append x y)
(1 2 3 4 5 6)
scheme@(guile-user)> (cons x y)
((1 2 3) 4 5 6)
scheme@(guile-user)> (list x y)
((1 2 3) (4 5 6))
 
练习 2.27:
Modify your reverse procedure of Exercise 2-18 to produce a deep-reverse procedure that takes a list
as argument and returns as its value the list with its elements reversed and with all sublists
deep-reversed as well. For example,
(define x (list (list 1 2) (list 3 4)))
x
((1 2) (3 4))
(reverse x)
((3 4) (1 2))
(deep-reverse x)
((4 3) (2 1))
我的解答:
(define (deep-reverse xss)
  (cond  ((null? xss)
          '())
         ((not (pair? (car xss)))
          (append (deep-reverse (cdr xss)) (list (car xss))))
         (else
          (append (deep-reverse (cdr xss)) (list (deep-reverse (car xss)))))))
 
练习 2.28:
Write a procedure fringe that takes as argument a tree (represented as a list) and returns a list
whose elements are all the leaves of the tree arranged in left-to-right order. For example,
(define x (list (list 1 2) (list 3 4)))
(fringe x)
(1 2 3 4)
(fringe (list x x))
(1 2 3 4 1 2 3 4)
我的解答:
(define (fringe xss)
  (cond ((null? xss)
         '())
        ((not (pair? (car xss)))
         (cons (car xss) (fringe (cdr xss))))
        (else
         (append (fringe (car xss)) (fringe (cdr xss))))))
 
练习 2.29:
A binary mobile consists of two branches, a left branch and a right branch. Each branch is a rod of
a certain length, from which hangs either a weight or another binary mobile. We can represent a
binary mobile using compound data by constructing it from two branches (for example, using list):
(define (make-mobile left right)
  (list left right))
A branch is constructed from a length (which must be a number) together with a structure, which may
be either a number (representing a simple weight) or another mobile:
(define (make-branch length structure)
  (list length structure))

a.Write the corresponding selectors left-branch and right-branch, which return the branches of a
mobile, and branch-length and branch-structure, which return the components of a branch.

b.Using your selectors, define a procedure total-weight that returns the total weight of a mobile.

c.A mobile is said to be balanced if the torque applied by its top-left branch is equal to that
applied by its top-right branch (that is, if the length of the left rod multiplied by the weight
hanging from that rod is equal to the corresponding product for the right side) and if each of the
submobiles hanging off its branches is balanced. Design a predicate that tests whether a binary
mobile is balanced.

d.Suppose we change the representation of mobiles so that the constructors are
(define (make-mobile left right)
  (cons left right))
(define (make-branch length structure)
  (cons length structure))
How much do you need to change your programs to convert to the new representation?
我的解答:
a,b,c:
(define (make-mobile left right)
  (list left right))

(define (left-branch mobile)
  (car mobile))

(define (right-branch mobile)
  (car (cdr mobile)))

(define (make-branch length structure)
  (list length structure))

(define (branch-length branch)
  (car branch))

(define (branch-structure branch)
  (car (cdr branch)))

(define (total-weight mobile)
  (if (real? mobile)
      mobile
      (+ (total-weight (branch-structure (left-branch mobile)))
         (total-weight (branch-structure (right-branch mobile))))))

(define (balance? mobile)
  (if (real? mobile)
      #t
      (let ((left (left-branch mobile))
            (right (right-branch mobile)))
        (let ((left-torque (* (branch-length left)
                              (total-weight (branch-structure left))))
              (right-torque (* (branch-length right)
                               (total-weight (branch-structure right)))))
          (and (= left-torque right-torque)
               (balance? (branch-structure (left-branch mobile)))
               (balance? (branch-structure (right-branch mobile))))))))

d:
(define (make-mobile left right)
  (cons left right))

(define (left-branch mobile)
  (car mobile))

(define (right-branch mobile)
  (cdr mobile))

(define (make-branch length structure)
  (cons length structure))

(define (branch-length branch)
  (car branch))

(define (branch-structure branch)
  (cdr branch))
 
练习 2.30:
Define a procedure square-tree analogous to the square-list procedure of Exercise 2-21. That is,
square-list should behave as follows:
(square-tree
 (list 1
       (list 2 (list 3 4) 5)
       (list 6 7)))
(1 (4 (9 16) 25) (36 49))
Define square-tree both directly (i.e., without using any higher-order procedures) and also by using
map and recursion.
我的解答:
(define (square x)
  (* x x))

(define (square-tree-1 tree)
  (cond ((null? tree)
         '())
        ((not (pair? tree))
         (square tree))
        (else
         (cons (square-tree-1 (car tree))
               (square-tree-1 (cdr tree))))))

(define (square-tree-2 tree)
  (map (lambda (sub-tree)
         (if (pair? sub-tree)
             (square-tree-2 sub-tree)
             (square sub-tree)))
       tree))
 
练习 2.31:
Abstract your answer to Exercise 2-30 to produce a procedure tree-map with the property that
square-tree could be defined as
(define (square-tree tree) (tree-map square tree))
我的解答:
(define (tree-map proc tree)
  (cond ((null? tree)
         '())
        ((not (pair? tree))
         (proc tree))
        (else
         (cons (tree-map proc (car tree))
               (tree-map proc (cdr tree))))))

(define (square-tree-3 tree)
  (tree-map square tree))
 
练习 2.32:
We can represent a set as a list of distinct elements, and we can represent the set of all subsets
of the set as a list of lists. For example, if the set is (1 2 3), then the set of all subsets is
(() (3) (2) (2 3) (1) (1 3) (1 2) (1 2 3)). Complete the following definition of a procedure that
generates the set of subsets of a set and give a clear explanation of why it works:
(define (subsets s)
  (if (null? s)
      (list nil)
      (let ((rest (subsets (cdr s))))
        (append rest (map <??> rest)))))
我的解答:

(define (subsets s)
  (if (null? s)
      '(())
      (let ((rest (subsets (cdr s))))
        (append rest (map (lambda (x) (cons (car s) x))
                          rest)))))

 

celebrity heights 说:
Jun 12, 2023 08:11:03 PM

It's a good chance to know more about these stories, very interesting and meaningful. And please take a look at this site, where I find the all the information I need about celeb height wiki


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter