作业6: Scheme
Homework 6: Scheme

Due by 11:59pm on Thursday, November 5

查看英文原文

说明

下载 hw06.zip。在压缩包中，你会找到一个名为 hw06.scm 的文件，以及一份 ok 自动评分器。

提交：完成后使用python3 ok --submit来提交代码。你可以在截止日期前多次提交；只有最后一次提交会被评分。请检查你是否成功提交了代码到okpy.org。更多提交作业的说明请参见Lab0。

使用Ok:如果你对使用Ok有任何疑问，请参考本指南。

阅读材料：以下阅读材料可能对你有帮助

评分：作业评分基于正确性。每个错误的问题将使总分减少一分。课程大纲中有作业恢复政策。 本次作业满分为2分。

在解决问题时，code.cs61a.org/scheme 可能对你有用，它可以绘制环境图和框图，并允许你逐步执行代码（类似于 Python Tutor）。不过，不要忘记通过 Ok 提交你的代码！

Scheme 编辑器

在编写代码时，你可以使用 Scheme 编辑器进行调试。在你的 scheme 文件夹中，你会找到一个新的编辑器。要运行此编辑器，请执行 python3 editor。这应该会在你的浏览器中弹出一个窗口；如果没有，请手动访问 localhost:31415。

请确保在一个单独的标签页或窗口中运行 python3 ok，这样编辑器才能保持运行。

如果你发现代码在在线编辑器中可以运行，但在本地解释器中无法运行，可能是前面部分的代码存在错误，你需要进行调试。偶尔会有一些测试无法捕捉到的错误，如果你发现了，请告诉我们！

必答题

Scheme

Q1: Thane of Cadr

定义过程 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 -u --local
python3 ok -q cadr-caddr --local

Q2: 符号函数

使用 cond 表达式，定义一个过程 sign，它接受一个参数 num，如果 num 为负数，则返回 -1；如果 num 为零，则返回 0；如果 num 为正数，则返回 1。 

(define (sign num)
  'YOUR-CODE-HERE
)

使用 Ok 来解锁并测试你的代码：

python3 ok -q sign -u --local
python3 ok -q sign --local

Q3: 幂函数

实现一个过程 pow，用于计算 x 的 y 次幂，其中 y 是一个非负整数，使得运算次数呈对数增长，而不是线性增长（递归调用的次数应远小于输入 y）。例如，(pow 2 32) 应该只需 5 次递归调用，而不是 32 次。同样，(pow 2 64) 应该只需 6 次递归调用。

提示： 请考虑以下结果：

  1. b2k = (bk)2
  2. b2k+1 = b(bk)2

你可以使用内置谓词 even? 和 odd?。 Scheme 不支持与 Python 相同方式的迭代，因此请考虑其他解决方案。

(define (square x) (* x x))

(define (pow x y)
  'YOUR-CODE-HERE
)

使用 Ok 来解锁并测试你的代码：

python3 ok -q pow -u --local
python3 ok -q pow --local

Submit

Make sure to submit this assignment by running:

python3 ok --submit