作业 7 | CS 61A 2024 春季学期

作业 7：Scheme

hw07.zip

截止时间：4 月 4 日周四晚上 11:59

操作指南

下载 hw07.zip。压缩包内包含一个名为 hw07.scm 的文件，以及 ok 自动评分器的副本。

提交方式： 完成作业后，请将您编辑的所有代码文件上传至 Gradescope。您可以在截止日期前多次提交；只有最终提交会被评分。请检查您是否已成功在 Gradescope 上提交了您的代码。有关提交作业的更多说明，请参阅 Lab 0。

使用 Ok： 如果您对使用 Ok 有任何疑问，请参阅本指南。

阅读材料： 您可能会发现以下参考资料很有用：

评分： 家庭作业根据正确性评分。每个不正确的问题将使总分减少一分。此家庭作业满分为 2 分。

每个 Scheme 作业都包含 61A Scheme 解释器。要启动它，请在终端中键入 python3 scheme。要加载名为 f.scm 的 Scheme 文件，请键入 python3 scheme -i f.scm。要退出 Scheme 解释器，请键入 (exit)。

Scheme 编辑器

所有 Scheme 作业都包含一个基于 Web 的编辑器，可以轻松运行 ok 测试并可视化环境。在终端中键入 python3 editor，编辑器将在浏览器窗口中打开（位于 http://127.0.0.1:31415/）。要停止运行编辑器并返回到命令行，请在启动编辑器的终端中键入 Ctrl-C。

“运行”按钮加载当前作业的 .scm 文件并打开 Scheme 解释器，允许您尝试评估不同的 Scheme 表达式。

“测试”按钮运行该作业的所有 ok 测试。单击失败测试的“查看案例”，然后单击“调试”以逐步执行其评估。

必做题

入门视频

要观看这些视频，您应该登录您的 berkeley.edu 电子邮件。

YouTube 链接

Q1: Pow

实现一个名为 pow 的函数，该函数计算 base 的 exp 次幂，其中 exp 为非负整数。要求递归调用 pow 的次数随 exp 的增长呈对数关系，而非线性关系。例如，(pow 2 32) 应该只递归调用 5 次 pow，而不是 32 次。

提示：
$x^{2y} = (x^y)^2$
$x^{2y+1} = x \cdot (x^y)^2$
例如， $2^{16} = (2^8)^2$ 且 $2^{17} = 2 \cdot (2^8)^2$ 。
你可以使用内置的 even? 和 odd? 函数。另外，square 函数已经定义好了。
Scheme 没有 while 或 for 语句，所以使用递归来解决这个问题。

(define (square n) (* n n))

(define (pow base exp)
  'YOUR-CODE-HERE
)

用 Ok 来测试你的代码吧：

python3 ok -q pow

Q2: Repeatedly Cube

实现 repeatedly-cube 函数，它接受一个数字 x，并对其进行 n 次立方运算。

以下是一些 repeatedly-cube 函数的例子，展示了它的预期行为：

scm> (repeatedly-cube 100 1) ; 1 经过 100 次立方运算后还是 1
1
scm> (repeatedly-cube 2 2) ; (2^3)^3
512
scm> (repeatedly-cube 3 2) ; ((2^3)^3)^3
134217728

有关 let 的信息，请参阅 Scheme 规范。

(define (repeatedly-cube n x)
    (if (zero? n)
        x
        (let
            (_________________)
            (* y y y))))

使用 Ok 来测试你的代码：

python3 ok -q repeatedly-cube

Q3: Cadr

注意： Scheme 列表在 4 月 3 日星期三的讲座视频中介绍。

定义 cadr 函数，它返回列表的第二个元素；并定义 caddr 函数，返回列表的第三个元素。

(define (cddr s)
  (cdr (cdr s)))

(define (cadr s)
  'YOUR-CODE-HERE
)

(define (caddr s)
  'YOUR-CODE-HERE
)

使用 Ok 来测试你的代码：

python3 ok -q cadr-caddr

作业 7 | CS 61A 2024 春季学期

作业 7：Scheme​

操作指南​

Scheme 编辑器​

推荐的 VS Code 扩展​

必做题​

入门视频​

Q1: Pow​

Q2: Repeatedly Cube​

Q3: Cadr​