作业 10

模板

在终端输入下面的命令，即可复制本作业的模板：

cp ~cs61as/autograder/templates/hw10.scm .

也可以点击此处下载。

练习 1

阅读 SICP 3.5.1，然后回答：

1. (delay (+ 1 27)) 的值的类型是什么？
2. (force (delay (+ 1 27))) 的值的类型是什么？

练习 2

求值下面这个表达式会产生错误：

(stream-cdr (stream-cdr (cons-stream 1 '(2 3))))

请解释原因。

练习 3

考虑下面两个过程：

(define (enumerate-interval low high)
  (if (> low high)
      '()
      (cons low (enumerate-interval (+ low 1) high))))

(define (stream-enumerate-interval low high)
  (if (> low high)
      the-empty-stream
      (cons-stream low (stream-enumerate-interval (+ low 1) high))))

下面两个表达式有什么区别？

(delay (enumerate-interval 1 3))
(stream-enumerate-interval 1 3

练习 4

数论中有一个未解之谜，涉及用下面的算法构造正整数序列 $s_1, s_2, \ldots$，其中 $s_1$ 是某个正整数，且对一切 $n > 1$：

• 若 $s_n$ 为奇数，则 $s_{n+1} = 3s_n + 1$；
• 若 $s_n$ 为偶数，则 $s_{n+1} = s_n \div 2$。

无论 $s_1$ 取什么起始值，这条序列（称为冰雹序列）似乎总是以 1, 4, 2, 1, 4, 2, 1, … 这样的循环值结尾。然而，这是否总是成立，目前仍无人知晓。

1. 编写过程 num-seq，它接受一个正整数 n 作为参数，返回 n 对应的冰雹序列。例如，(num-seq 7) 应返回表示序列 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1, 4, 2, 1, … 的流。

2. 编写过程 seq-length，它接受一条由 num-seq 产生的流，返回序列中直到（并包括）第一个 1 为止的值的个数。例如，(seq-length (num-seq 7)) 应返回 17。你可以假设序列中某处存在一个 1。

练习 5

又到做 SICP 的时候了——本作业的 SICP 部分！

完成以下练习：3.50、3.51、3.52、3.53、3.54、3.55、3.56、3.64、3.66、3.68。

练习 6

编写并测试两个函数，用来处理非负的真分数。

第一个函数 fract-stream 接受一个由两个非负整数组成的列表（分子和分母），其中分子小于分母。它返回一条无穷流，由该分数小数展开的数字组成。

第二个函数 approximation 接受两个参数：一条分数流和一个非负整数 numdigits。它返回一个列表（不是流），包含小数展开的前 numdigits 个数字。

一些提示：

• (fract-stream '(1 7)) 应返回表示 1/7 小数展开的流，即 0.142857142857142857…
• (stream-car (fract-stream '(1 7))) 应返回 1。
• (stream-car (stream-cdr (stream-cdr (fract-stream '(1 7))))) 应返回 2。
• (approximation (fract-stream '(1 7)) 4) 应返回 (1 4 2 8)。
• (approximation (fract-stream '(1 2)) 4) 应返回 (5 0 0 0)。

提交作业！

提交方法请参阅这份指南，其中涵盖基本的终端命令和作业提交流程。

提交过程中如有任何困难，别犹豫，尽管问助教！