免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
最近访问板块 发新帖
查看: 15351 | 回复: 56
打印 上一主题 下一主题

SICP 习题参考答案,3.5 [复制链接]

论坛徽章:
0
跳转到指定楼层
1 [收藏(0)] [报告]
发表于 2008-09-02 15:50 |只看该作者 |倒序浏览

  1. 本贴用与存放 SICP 3.5 节的习题参考答案。为保持可读性,请勿直接回复本贴。讨论请另开新贴。
复制代码




[ 本帖最后由 win_hate 于 2008-9-13 16:59 编辑 ]

论坛徽章:
0
2 [报告]
发表于 2008-09-02 15:52 |只看该作者

Exercise 3.50.

Exercise 3.50.  Complete the following definition, which generalizes stream-map to allow procedures that take multiple arguments, analogous to map in section 2.2.3, footnote 12.


  1. (define (stream-map proc . argstreams)
  2.   (if (<??> (car argstreams))
  3.       the-empty-stream
  4.       (<??>
  5.        (apply proc (map <??> argstreams))
  6.        (apply stream-map
  7.               (cons proc (map <??> argstreams))))))
复制代码

[ 本帖最后由 win_hate 于 2008-9-2 15:54 编辑 ]

论坛徽章:
0
3 [报告]
发表于 2008-09-02 15:53 |只看该作者

Exercise 3.50. 答案


  1. (define (stream-map proc . argstreams)
  2.   (if (stream-null? (car argstreams))
  3.       the-empty-stream
  4.       (cons-stream
  5.         (apply proc (map stream-car argstreams))
  6.         (apply stream-map
  7.                (cons proc (map stream-cdr argstreams))))))
复制代码

论坛徽章:
0
4 [报告]
发表于 2008-09-02 15:54 |只看该作者

Exercise 3.51.

Exercise 3.51.  In order to take a closer look at delayed evaluation, we will use the following procedure, which simply returns its argument after printing it:

(define (show x)
  (display-line x)
  x)

What does the interpreter print in response to evaluating each expression in the following sequence?59

(define x (stream-map show (stream-enumerate-interval 0 10)))
(stream-ref x 5)
(stream-ref x 7)

论坛徽章:
0
5 [报告]
发表于 2008-09-02 15:56 |只看该作者

Exercise 3.51 答案


  1. 0       ;;<- define
  2. 1       ;;<- ref 5
  3. 2
  4. 3
  5. 4
  6. 5
  7. 6       ;;<- ref 7
  8. 7
复制代码


本题想说,force 有记忆。 show 有输出的副作用,但如果只提取已有的值,则无需执行 show.

[ 本帖最后由 win_hate 于 2009-4-15 15:36 编辑 ]

论坛徽章:
0
6 [报告]
发表于 2008-09-02 15:57 |只看该作者

Exercise 3.52

Exercise 3.52.  Consider the sequence of expressions


  1. (define sum 0)
  2. (define (accum x)
  3.   (set! sum (+ x sum))
  4.   sum)
  5. (define seq (stream-map accum (stream-enumerate-interval 1 20)))
  6. (define y (stream-filter even? seq))
  7. (define z (stream-filter (lambda (x) (= (remainder x 5) 0))
  8.                          seq))
  9. (stream-ref y 7)
  10. (display-stream z)
复制代码


What is the value of sum after each of the above expressions is evaluated? What is the printed response to evaluating the stream-ref and display-stream expressions? Would these responses differ if we had implemented (delay <exp>) simply as (lambda () <exp>) without using the optimization provided by memo-proc ? Explain.

[ 本帖最后由 win_hate 于 2008-9-2 16:00 编辑 ]

论坛徽章:
0
7 [报告]
发表于 2008-09-02 15:59 |只看该作者

Exercise 3.52. 答案

[解]

  1. (define seq (stream-map accum (stream-enumerate-interval 1 20)))
复制代码


此语句执行后,sum=1

  1. (define y (stream-filter even? seq))
复制代码


此语句执行后, sum=1+2+3=6

  1. (define z (stream-filter (lambda (x) (= (remainder x 5) 0))
  2.                          seq))
复制代码


此语句执行后, sum=6+4=10


  1. (stream-ref y 7)
复制代码


此语句执行时,seq 前 4 项已知,后面的要动态计算,取其中第 8 个偶数。seq 的第 n 项为正整数列的前 n 项之和 n(n+1)/2,为偶数仅当 n=3,0 (mod 4)。所以 n=3, 4, 7, 8, 11, 12, 15, 16.

(stream-ref y 7) 的值为 16(16+1)/2=136. 如果在交互环境,输出 135,如果是脚本运行模式,没有输出。


  1. (display-stream z)
复制代码


此语句输出 seq 中的全部能被 5 整除的数。n(n+1)/2 为 5 的倍数,当且仅当 n=4,0 (mod 5)。所以 n 取 4,5,9,10,14,15,19,20. 由于

(map (lambda (n) (/ (* n (+ n 1)) 2)) '(4 5 9 10 14 15 19 20))

得到

(10 15 45 55 105 120 190 210)

所以输出为:

10
15
45
55
105
120
190
210


========================================


如果没有使用 memo-proc 优化,则 force 不保存首次求值的结果。

(1) define seq, sum=1

(2) define y, sum=6

(3) define z,

由于 seq 的第一项不是 promise,所以不产生累加 sum 的副作用。

sum=6+2+3+4=15

(4) (stream-ref y 7)

从流 y 中提第 8 个数,即用 stream-filter 在 seq 中提取第 8 个偶数。此时 seq 的通项为

s(n)=15+n(n+1)/2-6,其中 n>=4

s(n) 为偶数,相当于  n(n+1)/2=1 (mod 4),化简有 (n-1)(n-2)=0 (mod 4),即 n=1,2 (mod 4)

这样的 n 依次为 5, 6, 9, 10, 13, 14, 17. 所以 (stream-ref y 7) 的值,也就是 sum 的当前值为 s(17)=162

(5) (display-steam z)

此表达式遍历流 z,而 z 是 stream-filter 过滤 seq, 提取 5 的倍数得到的列表。

此时 seq 的通项为:

t(n)=162+n(n+1)/2-10,其中 4 < n < 21

5|t(n),相当于 n(n+1)/2=3 (mod 5),化简有 (n-2)^2=0 (5).
即 n=2 (mod 5)

这样的 n 依次为 7, 12 17。所以该语句的输出为:15, t(7), t(12), t(17), 即

15
180
230
305

而 sum 的当前值为 t(20)=362.

[ 本帖最后由 win_hate 于 2008-9-2 23:36 编辑 ]

论坛徽章:
0
8 [报告]
发表于 2008-09-03 11:56 |只看该作者

Exercise 3.53.

Exercise 3.53.  Without running the program, describe the elements of the stream defined by

(define s (cons-stream 1 (add-streams s s)))

论坛徽章:
0
9 [报告]
发表于 2008-09-03 11:57 |只看该作者

Exercise 3.53 答案

每一项是前一项的两倍,得到序列 {2^n, n in  N}.

[ 本帖最后由 win_hate 于 2008-9-3 12:57 编辑 ]

论坛徽章:
0
10 [报告]
发表于 2008-09-03 11:58 |只看该作者

Exercise 3.54

Exercise 3.54.  Define a procedure mul-streams, analogous to add-streams, that produces the elementwise product of its two input streams. Use this together with the stream of integers to complete the following definition of the stream whose nth element (counting from 0) is n + 1 factorial:

(define factorials (cons-stream 1 (mul-streams <??> <??>)))
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

  

北京盛拓优讯信息技术有限公司. 版权所有 京ICP备16024965号-6 北京市公安局海淀分局网监中心备案编号:11010802020122 niuxiaotong@pcpop.com 17352615567
未成年举报专区
中国互联网协会会员  联系我们:huangweiwei@itpub.net
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP