实验 3：序列与递归

截止时间：7 月 2 日（星期四）晚上 11:59。

起始文件

下载 lab03.zip.

出勤要求

要获得实验课学分，除了到场参加实验课外，你还需要提交实验题目。

如果你因合理原因（例如生病或时间冲突）缺席实验课，或者由于某种原因未能完成签到，请在一周内发送邮件至 cs61a@berkeley.edu ，以补记出勤学分。

主题

如果需要复习本实验涉及的知识，可以阅读这一部分。你也可以直接跳到 题目部分 ，遇到困难时再回来查阅。

列表

列表是一种保存有序数据集合的数据结构。其中的每一项称为元素，可以是数字、字符串，甚至是其他列表等任意数据类型。把一组用逗号分隔的表达式放在方括号中即可创建列表：

>>> list_of_values = [2, 1, 3, True, 3]
>>> nested_list = [2, [1, 3], [True, [3]]]

列表中的每个位置都有索引，最左侧元素的索引为 0.

>>> list_of_values[0]
2
>>> nested_list[1]
[1, 3]

负索引从末尾开始计数，最右侧元素的索引为 -1.

>>> nested_list[-1]
[True, [3]]

列表相加会创建一个更长的新列表，其中依次包含参与相加的各列表元素。

>>> [1, 2] + [3] + [4, 5]
[1, 2, 3, 4, 5]

列表推导式

列表推导式描述列表中的元素，并求值得到一个包含这些元素的新列表。

列表推导式有两种形式：

[<expression> for <element> in <sequence>]
[<expression> for <element> in <sequence> if <conditional>]

下面的例子从 [1, 2, 3, 4]开始，使用 2 和 4 选出其中的偶数，再使用 if i % 2 == 0把每个偶数平方。 i*i在这里， for i 的作用是为 [1, 2, 3, 4].

>>> [i*i for i in [1, 2, 3, 4] if i % 2 == 0]
[4, 16]

这个列表推导式会求值得到：

  • 表达式 i*i
  • 对每个元素 i （它来自序列 [1, 2, 3, 4]
  • ），如果满足 i % 2 == 0

换句话说，这个列表推导式会创建一个新列表，其中包含原列表中每个偶数的平方。 [1, 2, 3, 4].

我们还可以把列表推导式改写成等价的 for 语句。以上面的例子为例：

>>> result = []
>>> for i in [1, 2, 3, 4]:
...     if i % 2 == 0:
...         result = result + [i*i]
>>> result
[4, 16]

for 语句

for 语句会对列表、range 等序列中的每个元素执行一次代码。每次执行时，紧跟在 for 后面的名称都会绑定到序列中的一个不同元素。

for <name> in <expression>:
    <suite>

首先，对 <expression> 求值，其结果必须是一个序列。随后按顺序遍历序列中的每个元素，并把

  1. <name> 绑定到当前元素。
  2. <suite> 会被执行。

下面是一个例子：

for x in [-1, 4, 2, 0, 5]:
    print("Current elem:", x)

它会显示：

Current elem: -1
Current elem: 4
Current elem: 2
Current elem: 0
Current elem: 5

Range 序列

range 是保存整数序列的数据结构，可以通过以下方式创建：

  • range(stop) 包含 0、1、……、 stop - 1
  • range(start, stop) 包含 start、 start + 1、……、 stop - 1

请注意，range 函数不包含 stop 这个值；它生成的数字会一直到 stop 为止，但不包含该值本身。

例如：

>>> for i in range(3):
...     print(i)
...
0
1
2

虽然 range 和列表都属于 序列，但 range 对象并不是列表。可以调用 list()将 range 转换为列表：

>>> range(3, 6)
range(3, 6)  # this is a range object
>>> list(range(3, 6))
[3, 4, 5]  # list() converts the range object to a list
>>> list(range(5))
[0, 1, 2, 3, 4]
>>> list(range(1, 6))
[1, 2, 3, 4, 5]

类型检查

说明： 类型检查虽然很有用，但在本课程中更应把它当作辨别输入与输出类型的练习。有些场景所需的类型检查语法超出课程范围；尽管如此，请阅读下面的说明，并在适合时尽量使用类型检查。

类型提示可以写在 assignment 和 def 语句（以及少数其他位置）中，用来标明变量应具有的值类型，或函数应返回的类型。

下面是不带类型提示的例子：

x = 4

def pair(y, z):
    return [y, z]

下面是同一个例子，其中类型提示说明 x、 y和 z 都是整数，且 pair 函数返回一个整数列表：

x: int = 4

def pair(y: int, z: int) -> list[int]:
    return [y, z]

无论是否添加类型提示，代码的运行行为都完全相同。更多信息请阅读 类型提示 文章。

自动类型检查：可以配置 VS Code，让它标出变量被赋予了非预期类型值的位置。要开启类型检查，请打开 VS Code 设置：Mac 上同时按 Command 与 , 键；Windows 上同时按 Control 与 , 键。在搜索栏中输入 type checking ，应该会出现下图所示的 Type Checking 选项。使用下拉菜单，把类型检查从默认的 off 改为 basic.

type-hints

如果没有出现这些类型检查选项，可能需要安装 Pylance 扩展。Mac 上同时按住 Shift、Command 和 X ，Windows 上同时按住 Shift、Control 和 X ，打开扩展视图。在搜索栏中输入 Pylance ，然后单击安装按钮。

要确认类型检查已经启用，请在 Python 文件中输入：

a: int = 'not an int'

你应该会在 'not an int'下方看到红色波浪线。把鼠标悬停在 'not an int'上时，VS Code 会显示错误信息，说明 'not an int' 与预期类型 int不匹配。编写代码时请留意这类错误，它们通常能提示 bug 所在的位置。

必做题

入门视频

这些视频可能会为解决本次作业中的编程题提供一些思路。

观看视频前，请先登录你的 berkeley.edu 邮箱账户。

YouTube 视频链接

列表

问题 1：WWPD——列表与 Range

使用 Ok 完成下面的“Python 会显示什么？”（WWPD）题，检查你对知识的掌握情况：

python3 ok -q lists-wwpd -u

Important: 对于所有 WWPD 题，如果你认为答案是 Function ，请输入 <function...>、 Error ；如果会报错，输入 Nothing ；如果没有任何显示，则输入

预测把下面的内容输入交互式解释器后 Python 会显示什么，然后实际运行以检查答案。

>>> s = [7//3, 5, [4, 0, 1], 2]
>>> s[0]

______
2

>>> s[2]

______
[4, 0, 1]

>>> s[-1]

______
2

>>> len(s)

______
4

>>> 4 in s

______
False

>>> 4 in s[2]

______
True

>>> s[2] + [3 + 2]

______
[4, 0, 1, 5]

>>> 5 in s[2]

______
False

>>> s[2] * 2

______
[4, 0, 1, 4, 0, 1]

>>> list(range(3, 6))

______
[3, 4, 5]

>>> range(3, 6)

______
range(3, 6)

>>> r = range(3, 6)
>>> [r[0], r[2]]

______
[3, 5]

>>> range(4)[-1]

______
3

问题 2：展开嵌套列表

请编写函数 flatten ，它接收列表 s 并返回一个 新列表 ，也就是将 s“展开”后的版本。不要修改原列表。

Note: 输入列表可能嵌套得很深，也就是列表中可能还有多层列表。请确保你的答案能处理这种情况。

提示：可以使用内置 type 函数检查某个对象是否为列表。例如：

>>> type(3) == list
False
>>> type([1, 2, 3]) == list
True
def flatten(s: list) -> list:
    """Returns a flattened version of list s.

    >>> flatten([1, 2, 3])
    [1, 2, 3]
    >>> deep = [1, [[2], 3], 4, [5, 6]]
    >>> flatten(deep)
    [1, 2, 3, 4, 5, 6]
    >>> deep                                # input list is unchanged
    [1, [[2], 3], 4, [5, 6]]
    >>> very_deep = [['m', ['i', ['n', ['m', 'e', ['w', 't', ['a'], 't', 'i', 'o'], 'n']], 's']]]
    >>> flatten(very_deep)
    ['m', 'i', 'n', 'm', 'e', 'w', 't', 'a', 't', 'i', 'o', 'n', 's']
    """
    "*** YOUR CODE HERE ***"

使用 Ok 测试你的代码：

python3 ok -q flatten

列表推导式

问题 3：WWPD——列表推导式

使用 Ok 完成下面的“Python 会显示什么？”（WWPD）题，检查你对知识的掌握情况：

python3 ok -q list-comprehensions-wwpd -u

Important: 对于所有 WWPD 题，如果你认为答案是 Function ，请输入 <function...>、 Error ；如果会报错，输入 Nothing ；如果没有任何显示，则输入

预测把下面的内容输入交互式解释器后 Python 会显示什么，然后实际运行以检查答案。

>>> [2 * x for x in range(4)]

______
[0, 2, 4, 6]

>>> [y for y in [6, 1, 6, 1] if y > 2]

______
[6, 6]

>>> [[1] + s for s in [[4], [5, 6]]]

______
[[1, 4], [1, 5, 6]]

>>> [z + 1 for z in range(10) if z % 3 == 0]

______
[1, 4, 7, 10]

问题 4：接近索引的元素

请实现 close_list，它接收整数列表 s 以及非负整数 k。它返回一个列表，其中包含 s 中与自身索引之差不超过 k 的元素。也就是说，元素与其索引之差的绝对值应小于或等于 k.

def close_list(s: list[int], k: int) -> list[int]:
    """Return a list of the elements of s that are within k of their index.

    >>> t = [6, 2, 4, 3, 5]
    >>> close_list(t, 0)  # Only 3 is equal to its index
    [3]
    >>> close_list(t, 1)  # 2, 3, and 5 are within 1 of their index
    [2, 3, 5]
    >>> close_list(t, 2)  # 2, 3, 4, and 5 are all within 2 of their index
    [2, 4, 3, 5]
    """
    assert k >= 0
    return [___ for i in range(len(s)) if ___]

使用 Ok 测试你的代码：

python3 ok -q close_list

递归

问题 5：列表排序

排序是计算机科学中的重要主题。本题将尝试用递归对列表进行排序。

首先编写函数 remove_first ，它接收列表 lst，删除数字在列表中的第一次出现。 elem.

def remove_first(lst: list, elem: int) -> list:
    """ This function removes the first appearance of elem in list lst.

    >>> remove_first([3, 4] , 3)
    [4]
    >>> remove_first([3, 4, 3] , 3)
    [4, 3]
    >>> remove_first([2, 4] , 3)
    [2, 4]
    >>> remove_first([] , 0)
    []
    """
    "*** YOUR CODE HERE ***"

使用 Ok 测试你的代码：

python3 ok -q remove_first

接下来编写函数 sort ，它接收列表 lst ，返回该列表排序后的版本。请使用递归！

提示：请使用刚刚定义的 remove_first 函数以及内置 min 函数。

def sort(lst: list) -> list:
    """This function returns a sorted version of the list lst.

    >>> sort([6, 2, 5])
    [2, 5, 6]
    >>> sort([2, 3])
    [2, 3]
    >>> sort([3])
    [3]
    >>> sort([])
    []
    """
    "*** YOUR CODE HERE ***"

使用 Ok 测试你的代码：

python3 ok -q sort

问题 6：层层加工

请编写函数 make_onion ，它接收两个单参数函数 f 和 g。它返回一个接收三个参数的函数： x、 y和 limit。如果能从 True 出发，在最多 y 次调用 x 或 limit 后得到 f 和 g和 False ，返回的函数就返回真；否则返回假。

例如，如果 f 会加 1，而 g 会翻倍，那么从 5 出发，经过四次调用就能得到 25： f(g(g(f(5)))).

def make_onion(f, g):
    """Return a function can_reach(x, y, limit) that returns
    whether some call expression containing only f, g, and x with
    up to limit calls will give the result y.

    >>> up = lambda x: x + 1
    >>> double = lambda y: y * 2
    >>> can_reach = make_onion(up, double)
    >>> can_reach(5, 25, 4)      # 25 = up(double(double(up(5))))
    True
    >>> can_reach(5, 25, 3)      # Not possible
    False
    >>> can_reach(1, 1, 0)      # 1 = 1
    True
    >>> add_ing = lambda x: x + "ing"
    >>> add_end = lambda y: y + "end"
    >>> can_reach_string = make_onion(add_ing, add_end)
    >>> can_reach_string("cry", "crying", 1)      # "crying" = add_ing("cry")
    True
    >>> can_reach_string("un", "unending", 3)     # "unending" = add_ing(add_end("un"))
    True
    >>> can_reach_string("peach", "folding", 4)   # Not possible
    False
    """
    def can_reach(x, y, limit: int) -> bool:
        if limit < 0:
            return ____
        elif x == y:
            return ____
        else:
            return can_reach(____, ____, limit - 1) or can_reach(____, ____, limit - 1)
    return can_reach

使用 Ok 测试你的代码：

python3 ok -q make_onion

在本地检查得分

你可以运行以下命令，在本地检查本次作业每道题的得分：

python3 ok --score

这不会提交作业！ 确认得分符合预期后，请将作业提交到 Gradescope，以获得作业学分。

提交作业

请上传所有你修改过的文件，将本次作业提交到 对应的 Gradescope 作业入口。 Lab 00 中提供了详细说明。

正确完成所有题目可得 1 分。 Please ensure your TA has taken your attendance before leaving.

可选题

以下题目为选做题。即使不完成，你仍能获得本次作业的学分；不过它们很适合用来练习，建议还是做一做！

问题 7：函数重复器

请定义函数 make_fn_repeater ，它接收一个单参数函数 f 以及一个整数 x。它应返回另一个单参数函数，该函数再接收一个整数，并返回把 f 改为 x 应用指定次数后的结果。

请确保在答案中使用递归。

def make_func_repeater(f, x: int):
    """
    >>> increment_repeater = make_func_repeater(lambda x: x + 1, 1)
    >>> increment_repeater(2) #same as f(f(x))
    3
    >>> increment_repeater(5)
    6
    """
    def repeat(____):
        if ____:
            return ____
        else:
            return ____
    return ____

使用 Ok 测试你的代码：

python3 ok -q make_func_repeater

这道题与一道家庭作业题很相似，不过这里要求递归实现。如果时间允许，建议完成它；它以一种很有意思的方式把递归和高阶函数联系起来。请把它与函数自引用进行比较，并说明为什么这并不是自引用：从行为上看，这里一次函数调用会引发一系列计算，而不是产生许多函数调用；从实现上看，这里对 repeat 的调用会 调用 repeat 本身，而不是返回一个新的 repeat 函数。）

问题 8：和为 10 的数位对

请编写一个函数，接收正整数 n 并返回其中“十数对”的数量。十数对是指 n 中两个数位之和为 10 的一对数位。

数字 7,823,952 中有 3 个十数对：第一位与第四位之和为 7+3=10，第二位与第三位之和为 8+2=10，第二位与最后一位之和也为 8+2=10。

重要说明：

  • 同一个数位可以属于多个十数对。
  • 单独一个 5 不能与自己组成十数对。

建议：请补全并使用辅助函数 count_digit ，计算某个数位在 n.

Important: 请使用递归；如果使用任何循环（for 或 while），测试将不会通过。

def ten_pairs(n: int) -> int:
    """Return the number of ten-pairs within positive integer n.

    >>> ten_pairs(7823952) # 7+3, 8+2, and 8+2
    3
    >>> ten_pairs(55055)
    6
    >>> ten_pairs(9641469) # 9+1, 6+4, 6+4, 4+6, 1+9, 4+6 
    6
    >>> # ban iteration
    >>> from construct_check import check
    >>> check(SOURCE_FILE, 'ten_pairs', ['While', 'For'])
    True
    """
    "*** YOUR CODE HERE ***"

def count_digit(n: int, digit: int) -> int:
    """Return how many times digit appears in n.

    >>> count_digit(55055, 5) # digit 5 appears 4 times in 55055
    4
    >>> from construct_check import check
    >>> # ban iteration
    >>> check(SOURCE_FILE, 'count_digits', ['While', 'For'])
    True
    """
    "*** YOUR CODE HERE ***"

使用 Ok 测试你的代码：

python3 ok -q ten_pairs