huangzworks/sicp-answers

我的 SICP 解题集

请到 sicp.readthedocs.org 在线阅读文档。

sicp-answers's Issues

练习 2.27 的实现只能处理二叉树

http://sicp.readthedocs.org/en/latest/chp2/27.html#comment-637720680

想办法进一步泛化实现。

练习 2.6 的加法定义有误？

http://sicp.readthedocs.org/en/latest/chp2/6.html#comment-719123777

练习 3.42

不是很理解你是怎么理解的，但是我觉得这里你的想法是错的。所谓的串行化环境，本质上就是在进入前加锁（互斥量，mutex），离开前解锁。每一个(make-serializer)返回的对象里头都应当包含一个mutex，当它保护的串行化环境被某个process占用时，其他试图占用这个环境的process都应当被阻塞在加锁的位置，所以不会影响程序的正确性。

如果你有兴趣，可以参考我基于Guile的mutex实现的make-serializer（以及parallel-execute）：https://github.com/felix021/sicp/blob/master/code/3.4-parallel.scm

这里是另一个解答的意见：http://community.schemewiki.org/?sicp-ex-3.42

3.18 exist a bug

The following cases are not considered:

(define l2 (list 1 2))
(set-car! (last-pair l2) l2)

My solution:

(define (have-cycle? x)
    (define (help x path)
        (if (not (pair? x))
            #f
            (or 
                (not (false? (memq x path)))
                (help (car x) (cons x path))
                (help (cdr x) (cons x path)))))
    (help x '()))

3.3.3表格的表示 代码有错

(define (insert! key-1 key-2 value)
(let ((subtable (assoc key-1 (cdr local-table))))
(if subtable
(let ((record (assoc key-2 (cdr subtable))))
(if record
(set-cdr! record value)
(set-cdr! subtable
(cons (key-2 value)
(cdr subtable)))))
(set-cdr! local-table
(cons (list key-1
(cons key-2 value))
(cdr local-table)))))
'ok)

第8行有错

练习3.3 balance unknown 拼写错误

练习3.47的疑问 这里在release的时候是不是也需要给n加锁 还是说默认这里的set!就是原子化的

;;; 47-semaphore-using-test-and-set.scm

(define (make-semaphore n)

(define (acquire)
    (if (test-and-set! n)
        (acquire)
        'ok))

(define (release)
    (set! n (+ n 1))
    'ok)

(define (dispatch mode)
    (cond ((eq? mode 'acquire)
            (acquire))
          ((eq? mode 'release)
            (release))
          (else
            (error "Unknown mode MAKE-SEMAPHORE" mode))))

dispatch)

(define (test-and-set! n)
(if (= n 0)
#t
(begin (set! n (- n 1))
#f)))

#|
; 根据注释 174
; 以下是一个可以在采用时间片模型的单处理器的 MIT Scheme 里实际运行的 test-and-set!

(define (test-and-set! n)
(without-interrupts
(lambda ()
(if (= n 0)
#t
(begin (set! n (- n 1))
#f)))))

|#

练习 3.47

基于 test-and-set! 的实现是错误的，因为在 release 里的 (set! n (+ n 1)) 仍然会出现竞争，可能导致信号量的实际值逐渐减小到1，因此逻辑上仍然是有问题的。

另外，你的实现已经不是用 test-and-set! 了，而是用你的 "test-and-add!"。按照题目的意思，应当是直接使用书上的 test-and-set! 来实现。

我的实现供参考： https://github.com/felix021/sicp/blob/master/code/3-47.scm

2.5

I'll suggest a corner case to your algorithm: 40, which can't be reduced to the product of 2^a and 3^b.

练习1.10

不知道什么原因，书中示例和维基百科上关于阿克曼函数的定义是不一致的。我修改了代码，但是不知道是否正确，希望能有人看一下。

(define (A x y)
    (cond ((= y 0) (A (- x 1) 1))
        ((= x 0) (+ y 1))
        (else (A (- x 1) (A x (- y 1)))))
)

2.25 你的解答并没有按照题目要求做

2.25 你的解答并没有按照题目要求做

要求是使用car和cdr的组合。
(car (cdr (car (cdr (cdr '(1 3 (5 7) 9))))))
(car (car '((7))))
(car (cdr(car (cdr(car (cdr(car (cdr(car (cdr(car (cdr '(1 (2 (3 (4 (5 (6 7)))))) ))))))))))))

3.38，b) 修正结果依然有问题

你俩说的都不对，@ruandao 说的是对的，peter先加10快x变成110，mary这个时候来了，第一次去取值为110,然后就在此时，paul开始动了，并把钱设置为90,然后mary第二次取值 90/2=45 ，设置值为 110-45=65，gg!!

1.10作者出题并非此意？

在您的题解中给出的做法是写出代码，对于较小的n进行尝试然后找规律。
但我认为，作者出这道题的目的是让读者学会通过观察程序来了解它的执行结果（正如1.2导语所说）？
因此我觉得可以改成：
$f(n)=2n$直接观察得到。
$g(n)=f(g(n-1))=2g(n-1)=2^n$
$h(n)=g(h(n-1))=2^{h(n-1)}=2^{2^{2^{2}}}$ n个2

练习 3.37

37-cv.scm里的cv给忘了贴出来啦。。。

"""
(define (cv x)
(let ((c (make-connector)))
(constant x c)
c))
"""

修复离线版不可用的问题

下载解压之后只有 index.html ，其他文件都不存在。

Exercise 2.24 中的Box-and-pointer structure 结果有误

每个list中的最后一个元素是个pair，并且该pair的cdr是nil

1.11：n为负数的情况

(define (f n)
f_iter(2, 1, 0, n))

(define (f_iter a, b, c, count)
(if (< count 3)
(- (+ count a) 2)
(f_iter (+ a (* 2 b) (* 3 c))
a
b
(- count 1))))

关于ex-3.42的问题

我以为这样的修改是安全的。在并发性方面也没有什么显著变化。

我对解释中的这句话不太认同“因为运行中的串行化进程是不能被其他过程所干扰的”。我觉得并行应该是发生在不同的进程中，比如进程一在运行 (protected-withdraw 10)时，进程二想要并发的运行 (protected-withdraw 20)，但是它发现它所要调运的过程protected-withdraw正在进程一中运行者，因此它等待进程一运行protected-withdraw结束，再开始运行。我的理由是p211小节中第一段的这句话“如果某个集合里有过程正在进行，而‘另一进程’企图执行这个集合里的‘任何’过程时，它就必须等待到前一过程的执行结束”。我觉得里面有这样的意思，不同的进程是可以调用同一个过程的，但显然由于（串行化的）同一个过程是在同一个集合下的，因此不同进程间需要等待。

我也不是很确定，貌似Ben老是提出一些不靠谱的建议~~~~~美国人怎么知道Ben就是笨啊？这个我也没想明白~~

练习2.73

我觉得操作-类型表主要是要实现一套通用的接口，求导通用的操作有'deriv和'make两个（因为product需求make-sum），所以只需要两条put，那些addend make-sum都是不必要的，只要放在package的闭包中就行了。

底下的(define (addend ...))更是没有必要，deriv函数根本没有调用这些函数，如果必须定义这些特化的接口，就和通用接口的理念背道而驰了。

我的代码 http://codepad.org/LWlwlN1D

1.33 素数之和

按照题解上面给出的结果为18，但是1不是素数，在前面的prime?中应该做一下判断吧，把1过滤出去。

也关联到了1.22等素数判断的一些解答，多加一些判断，比如在next-odd里对0和1过滤。

添加双端链表实现到练习 3.23

练习 3.52

huangz同学你最后的结论错了，答案是410不是420……这里稍微有点坑，因为…
…
…
…
…
…
(define z ...) 的时候，已经计算了1,2,3,4，(display-stream z)并不是从1重新开始计算，而是从5开始计算，也就是说，第二层次计算会少算一次1,2,3,4，因此最后的结果是 10 + 200 + 200 = 410。这还是在注释了(define y ...)的情况下得出的结果。如果加上(define y ...)，结果会变成415，而序列z也完全不同了。

修复练习 3.38 和 3.40

http://sicp.readthedocs.org/en/latest/chp3/38.html

http://sicp.readthedocs.org/en/latest/chp3/40.html

2.43的答案有问题

2.42的函数每计算一次queen-col k需要既然一次queen-col (k-1)，计算一次queen (k-2)，计算一次queen (k-3)...最终只需计算一次queen-col 1。
而Louis的函数每计算一次queen-col l需计算board-size次queen-col (k-1), 计算queen-col (k-1) 需要计算board-size次 queen-col (k-2).故计算queen-col board-size需要计算board-size的board-size次方次queen-col 1。
故Louis的函数需要pow(board-size,board-size)*T的时间。

1.28的题解有问题

非平凡平方根的检测是针对每次要square的那个值，而不是一直是a。

可参考下面的实现：
https://github.com/ajkitson/sicp/blob/master/ch1/1.28.scm
https://github.com/kenspirit/SICP/blob/master/c-1/1.28-miller-rabin-test.md
http://community.schemewiki.org/?sicp-ex-1.28

2.49 给的链接失效了

原来是 http://www.biwascheme.org/repos/demo/pictlang.html ，现在是http://www.biwascheme.org/demo/pictlang.html

练习 3.39

给出的序列是正确的，但是对序列2的解释错了。

(set! x ?) 实际上是计算sa的过程，也就是说序列2应当为：

[计算 sa=100] => (set! x (+ 10 1) => x = 11 => (set! x sa) => x = 100

练习 2.24的图是用什么工具自动生成的呀？

练习 2.24的图是用什么工具画的呀？

(1 (2 (3 4))) ((2 (3 4)))
[]---------------> []
| |
| |
v v (2 (3 4)) ((3 4))
1 []---------------> []
| |
| |
v v (3 4) (4)
2 []---------------> []---------------> '()
| |
| |
v v
3 4

(1 (2 (3 4)))
*
/
/ \ (2 (3 4))
1 *
/
/ \ (3 4)
2 *
/
/
3 4

添加排序解法到练习 1.3

http://sicp.readthedocs.org/en/latest/chp1/3.html#comment-680681656

练习2.43

对练习2.43运行时间的估计，我觉得不是乘上board-size倍。

我的答案：
棋盘大小为b, n<=b, 如果n列耗时T(n)，则T(n) = b * T(n - 1), T(n - 1) = b * T(n - 2) ... ，应该是 b^b，但是考虑到实际运行时不会遍历到太多的情况，实际执行时间比理论上界小很多。
(修改了一下回答，用拼音输入法打字出错了)
这个是我的答案，不知道对不对？

cdnjs.cloudflare.com 拖慢了页面速度

MathJax使用了 cloudflare 的 CDN https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.7/latest.js?config=TeX-AMS-MML_HTMLorMML
但是现在，此JS文件（在大陆）已经不可以访问。

可以在 conf.py 中增加

mathjax_path = 'https://cdn.rawgit.com/mathjax/MathJax/2.7.1/MathJax.js'

希望有人能提个pr

3.39结果不对

考虑这个，
第一个过程执行 set! x (sa) , sa =100 刚执行完，sb来了，设置x=11，然后继续 set! x (sa)=100，结果是100

不兼容windows的文件名问题

hi
我在clone的时候提示checkout失败，我看到是有类似“ chp2/code/37-matrix-*-matrix-another.scm ”这种文件名里带星号的文件，在windows下是非法的所以无法创建文件成功。
是否可以修改一下呢？

谢谢。

可以把题目附上么？

答案不全问题？

你好，sicp中2.7-2.16的答案不全吗？

修复练习 3.6 的答案

http://sicp.readthedocs.org/en/latest/chp3/6.html#comment-770974238

需要一种根据相同 state 生成连续随机数的 random 函数，比如：

(rand-init 10086)
(random) => r1
(random) => r2
(random) => r3

(rand-init 10086)
(random) => r21
(random) => r22
(random) => r23

其中 r1 == r21 、 r2 == r22 、 r3 == 23 。

1.45补充

这里提供一个自适应的求n次方根的函数（所谓自适应是指，不需要提前知道要进行几次平均阻尼）

(define (average-damp f)
  (lambda (x) (/ (+ x (f x)) 2)))

(define (adapt-fixed-point f first-guess)
  (define (close-enough? guess next)
    (let ((tolerance 0.00001)) (< (abs (- guess next)) tolerance)))
  (define (try guess times damped-f damped-times)
    (let ((times-thr 100000)
          (next (damped-f guess)))
      (cond ((> times times-thr) (try first-guess 1 (average-damp damped-f) (+ damped-times 1)))
            ((close-enough? guess next) (display "damped-times=") (display damped-times) (newline) next)
            (else (try next (+ times 1) damped-f damped-times)))))
  (try first-guess 1 (average-damp f) 1))

(define (nrt x n)
  (adapt-fixed-point (lambda (y) (/ x (expt y (- n 1)))) 1.0)

link:https://github.com/jiakai0419/SICP/blob/master/chapter-1/exercise-1.45.scm

验证 1.29 的积分下界是否需要设为 0

http://sicp.readthedocs.org/en/latest/chp1/29.html#comment-775467789

练习 3.43

huangz同学你问题2的流程出错了。

左边((acc-1 'withdraw) -10)执行之前，acc-1的余额已经被右边改成30了，所以acc-1最后的余额应当是40。

而题目中问题3的结论是正确的……所有情况都列出来比较麻烦，但是实际上很好理解，因为不论如何交叉，每个difference总是被加一次、减一次，应此对总和是没有影响的。

ex 4.11 題目意思理解有誤

原来表的序对是这样的话

( ( a b ... ) 1 2 ... )

约束（名字-值序对）的表的意思应该是这样的吧

( ( a . 1 ) ( b . 2 ) ... )

2.31 tree-map 定义

http://sicp.readthedocs.org/en/latest/chp2/31.html

注释有问题 定义二 ; 递归处理左右分支

并没有左右分支吧！应该是递归处理 从左至右

练习3.29 或门的延迟计算与练习3.30加法器的延迟计算

这里的答案指出“整个 or-gate 共调用了三次 inverter ，一次 and-gate ，因此 or-gate 的延迟等于 3 * inverter-delay + and-gate-delay”

但前两个非门是并联关系的，它们的延迟应该不是叠加的，所以我认为or-gate的延迟等于2* inverter-delay + and-gate-delay

同理 联系3.30的计算可能也有问题，半加器S的延迟为max(or, and+inverter)+and, C的延迟为and, 全加器S的延迟与半加器相同，C的延迟为max(or, and+inverter)+2and+or, 级联加法器的延迟为 n(全加器C的延迟)

不知道我的理解是否正确，望讨论下

练习 3.30

huangz同学你的代码似乎有问题。 ripple-carry-adder 这个函数只是完成了各个信号的关联，并没有完成计算；而你在 iter 里面 get-signal/set-signal ，实际上是试图在关联的时候完成计算，而在关联的时候，A-list、B-list里是没有值的（或者说是它们的值是无意义的）；实际的计算逻辑应当发生在set-signal以后。于是你的代码在关联的时候少关联了进位，在计算的时候又没能把进位计算进去……这是我的代码，供参考：https://github.com/felix021/sicp/blob/master/code/3-30.scm

练习 3.35

huangz同学如果你不加这句 (error "Neither a nor b has value") 的话，process-forget-value 里面加一句 (process-new-value) 也不会出错的……所以这不是作者的陷阱，是你自己掉进自己挖的坑了啊……

修复练习 3.16

http://sicp.readthedocs.org/en/latest/chp3/16.html#comment-771430500

纠错1.3.1第二段代码

product（迭代版本）
迭代的第一个参数应该是(next a)
而不是(+ a 1)

BUG ex-4.8

当前答案

(define (fib n)
(let ((fib-iter
(lambda (a b count)
(if (= count 0)
b
(fib-iter (+ a b) a (- c 1))))))
(fib-iter 1 0 n)))

按这样展开的 let 表达式在运行中会找不到 fib-iter

49 ;; ATTENTION !!!!! the following modification do NOT work
50 ;; (define (let->combination exp)
51 ;; (if (let-named? exp)
52 ;; (make-let (list (list (let-named-name exp)
53 ;; (make-lambda (let-named-parameters exp)
54 ;; (let-named-body exp))))
55 ;; (list (cons (let-named-name exp)
56 ;; (let-named-arguments exp))))
57 ;; (cons (make-lambda (let-parameters exp)
58 ;; (let-body exp))
59 ;; (let-arguments exp))))

以上是按照Huang提供的思路展开的 let 表达式，经过测试出错，问题在于
(lambda (a b count)
(if (= count 0)
b
(fib-iter (+ a b) a (- c 1))))
该 lambda 创建的过程的环境指向运行 fib 时的创建的环境，记为E1，而 let 实际上是另一个lambda过程，该过程在运行时将创建环境 E2 指向 E1，在这个环境中将绑定形式参数 fib-iter 到上述 lambda 过程，然而这个 lambda 过程所指向环境是E1（如上述），这个过程在运行时创建环境E3，指向E1，而不是E2，所以从E3开始寻找 fib-iter 将沿着E3-->E1--> global 的路线进行，是不可能找到 fib-iter 的。

也就是说，事实上，第四章中定义的 EVAL 要求 let 的（形式）参数不能是一个需要递归调用自身的过程。否则将在递归时因为找不到过程名（那个形式参数）而报错。

练习 1.7 的实现代码错误

http://sicp.readthedocs.org/en/latest/chp1/7.html#comment-657507692

练习 1.7 goodenough 的判断

其中 goodenough 的判断应该是 <.

goodenough 为 true 的条件应该是 old-guess 和 new-guess 足够接近, 所以应该是差的绝对值越小越好. 而且如果使用 >, 大部分情况下, 例如 x = 2, 在第一轮判断中, old-guess = 1, new-guess = 1.5. 则绝对值的差为 0.5, 大于 0.01, 直接跳出递归.

(define (good-enough? old-guess new-guess)
    (< 0.01
       (/ (abs (- new-guess old-guess))
          old-guess)))

考虑到不对原有定义的破坏, 我建议将 old-guess 和 new-guess 的比较放在 goodenough 中处理, 如下:

(define (goodenough? guess x)
  (< (/ (abs (- guess
		(improve guess x)))
        guess)
     (expt 0.1 4)))

完整的代码可以点击这里, 供参考.

练习 2.4 疑问

大佬的答案：

(car (cons 1 2))

(car (lambda (m) (m 1 2)))          ; 展开 cons

((lambda (z) (z (lambda (p q) p)))  ; 展开 car ，代换 z
    (lambda (m) (m 1 2)))

((lambda (m) (m 1 2))               ; 代换 m
    (lambda (p q) p))

((lambda (p q) p)                   ; 代换 p
    1 2)

1

第二步 展开 car，代换 z 不是很理解，为什么把 z 变成了 lambda 表达式，而不是把 z 看作一个过程，随后是把过程 (lambda (p q) p)) 当做过程 z 的参数？

下面是我的理解：

(car (cons 1 2))

(car (lambda (m) (m 1 2)))          ; 展开 cons

((lambda (m) (m 1 2)) (lambda (p q) p)))  ; 展开 car

((lambda (p q) p)                   ; 过程参数代入 m
    1 2)

1