作业 3

模板

在终端输入下面的命令，把模板文件复制到当前目录（注意末尾有一个点）：

cp ~cs61as/autograder/templates/hw3.rkt .

或者，你也可以从这里下载模板。

自动评分器

如果你在实验室的计算机上工作，grader 命令会运行自动评分器（autograder）。如果你在自己的个人电脑上工作，你应该下载 grader.rkt 和 作业 3 测试。

练习 1：快速幂的不变式

下面是本课前面出现的 fast-expt 过程：

(define (even? n)
  (= (remainder n 2) 0))

(define (fast-expt b n)
  (cond ((= n 0) 1)
        ((even? n) (square (fast-expt b (/ n 2))))
        (else (* b (fast-expt b (- n 1))))))

设计一个过程，生成一个使用连续平方、并且像 fast-expt 一样只需对数级步数的迭代幂运算过程。

（提示：利用观察 $(b^{n/2})^2 = (b^2)^{n/2}$，除了指数 n 和底数 b 之外，再维护一个附加的状态变量 a，并这样定义状态变换：使乘积 abⁿ 在状态转移前后保持不变。过程开始时 a 取 1，过程结束时 a 的值就是答案。一般说来，定义一个在状态转移中保持不变的不变量，是思考迭代算法设计的强有力方法。）

练习 2：黄金比例（选做）

阅读 SICP 中关于寻找函数不动点的小节，并完成 练习 1.35。

练习 3：cont-frac

第 1 部分

无限连分数是形如下式的表达式：

$$f = N_1/(D_1 + N_2/(D_2 + N_3/(D_3 + ...)))$$

例如，可以证明

$$1/\varphi = 1/(1 + 1/(1 + 1/(1 + ...)))$$

其中 $\varphi = (1+\sqrt{5})/2$ 是黄金比例。逼近无限连分数的一种方法，是在给定项数之后截断展开式。这样的截断——所谓的 k 项有限连分数——形如：

$$N_1/(D_1 + N_2/(... + N_k/D_k))$$

假设 n 和 d 是各接受一个实参（项的序号 i）的过程，分别返回连分数第 i 项的 N 和 D。定义一个过程 cont-frac，使得求值 (cont-frac n d k) 能算出这个 k 项有限连分数的值。用下面的表达式逼近 1/φ 来检验你的过程：

(cont-frac (lambda (i) 1.0)
           (lambda (i) 1.0)
           k)

k 要取多大，才能得到精确到 4 位小数的逼近值？

第 2 部分

如果你的 cont-frac 过程生成的是递归过程，那就写一个生成迭代过程的版本；如果它生成的是迭代过程，那就写一个生成递归过程的版本。

第 3 部分

1737 年，瑞士数学家莱昂哈德·欧拉证明了：

$$e - 2 = N_1/(D_1 + N_2/(D_2 + N_3/(D_3 + ...)))$$

其中参数为：

• $N_i = 1$
• $D_i = 1, 2, 1, 1, 4, 1, 1, 6, 1, 1, 8, ...$

这里 e 是自然对数的底。写一个程序，用你的 cont-frac 过程，通过欧拉展开式逼近 e。

练习 4：next-perf

完美数（perfect number）定义为等于其所有小于自身的因子之和的数。例如，第一个完美数是 6，因为它的因子是 1、2、3 和 6，而 1+2+3=6。第二个完美数是 28，因为 1+2+4+7+14=28。那么第三个完美数是多少？

编写一个过程 (next-perf n)，从 n 开始逐个测试整数，直到找到一个完美数。然后你可以求值 (next-perf 29) 来解答这个问题。注意，你的过程应该能处理任意非负整数输入。

提示：你需要一个 sum-of-factors 子过程。

练习 5：交换基本情况

下面是本课前面 count-change 程序的定义：

(define (count-change amount)
  (cc amount `(50 25 10 5 1)))

说明交换 cc 过程中基本情况的检查顺序会有什么影响。

也就是说，完整地描述这样的实参数集合：对它们而言，原来的 cc 过程与下面这样编写的 cc 过程会返回不同的值或表现不同，并解释返回值会有什么差别。

(define (cc amount kinds-of-coins)
  (cond
    [(or (< amount 0) (empty? kinds-of-coins)) 0]
    [(= amount 0) 1]
    [else ... ] ) ) ; 与原版本相同

练习 6：幂运算的不变式

下面是本课前面的迭代幂运算过程：

(define (expt b n)
  (expt-iter b n 1))

(define (expt-iter b counter product)
  (if (= counter 0)
      product
      (expt-iter b
                (- counter 1)
                (* b product))))

给出一个代数公式，表达上面迭代幂运算过程中形参 b、n、counter 和 product 的值之间的关系。

（我们要找的答案形式类似：「b、n 与 counter 之和乘以 product 始终等于 37。」）

提交作业！

相关说明请参阅这份指南，其中涵盖基本终端命令和作业提交。

如果在提交过程中遇到任何麻烦，请随时向助教（TA）求助！