期中考试1 详细解答
逆向环境图
考试中共有三种可能的变体，基本内容相同，只是变量名和参数顺序有所不同。
你可以在 PythonTutor 中查看各自的代码：
其中两道题有多个可能的答案，你必须选择所有可能的答案才能获得满分。答案必须是一个能够求值为真值的逻辑条件，而且每个图都有多个条件求值为 True。例如，上面的代码使用了 y < 0，但许多其他条件也有效：x < 0、y <= 0、x <= 0。如果你遗漏了其他条件，请务必仔细阅读题目，看看它是否是"选择所有适用的"类型，然后考虑哪些条件会导致相同的图。
以下是解答逆向环境图问题的一般策略：
- 加载 PythonTutor
- 在空白处填入一些默认值以查看完整的环境图（添加随机数字/字符串/lambda）
- 逐行执行代码，看看能否将某些默认值更新为预期输出
- 对于"选择所有适用的"，考虑该行代码中出现的变量，分析每种情况会如何改变控制流
消失的文档字符串之谜
正确答案是"返回 L 中正数元素的平均值，如果没有此类元素则返回零。"
以下是其他选项不正确的原因：
返回 L 中所有元素的平均值，如果没有元素则返回零。
- 代码在循环中有
if item > 0:，只有在该条件下才会累加值，因此它不是对所有元素求平均值，而只是对大于 0 的元素求平均值。
- 代码在循环中有
返回 L 中奇数索引位置元素的平均值，如果没有此类元素则返回零。
- 没有检查元素是否具有奇数索引的条件（这种条件大概会是
if i % 2 == 1）。
- 没有检查元素是否具有奇数索引的条件（这种条件大概会是
返回 L 中 >= 0 的元素平均值，如果没有此类元素则返回零。
- 代码中是
if item > 0，而不是if item >= 0，所以不完全正确。
- 代码中是
魔法测试编织者
这道题的灵感来源于 2月8日"函数示例"讲座中的 interleave_digits。
答案需要非常仔细地阅读文档字符串：
""" Assuming A and B are positive integers with the same number of base-10 digits
and C is a positive integer < 10, return the number whose base-10
representation is the interleaving of digits in A and B (alternating
first one from A then one from B) from all positions where the
two digits in A and B at that position are both >= C. Return 0 if there
are no such positions. Raises an exception if preconditions are not met."""还需要理解以下术语：
- 正数：大于 0 的数。我们在考试期间做了澄清：0 不是正数，因为有很多人询问。
- 整数：整数是完整数字（不是分数）。
- 前置条件：前置条件描述了函数输入参数的要求（与描述输出要求的后置条件相对）。
- 异常：当代码引发异常且该异常未被显式处理时，整个程序停止运行并显示异常信息。参见教材中的异常处理或 2月5日的"设计 + 异常"讲座。
正确答案只有：
>>> magic_weave(456, 567, 5)
5667以下是其他选项不正确的原因：
>>> magic_weave(123, 456, 5)
56^ 这个测试包含两个来自第二个数字的数字，而没有来自第一个数字的数字。按照文档字符串的描述和通过测试的 doctest，这不是交替交织。
>>> magic_weave(234, 456, 5)
3546^ 这个测试交替交织了两个数字的第二和第三位数字。然而，文档字符串指明只有两个数字在该位置上都 >= 第三个参数时才能交织。因为 3 和 4 都小于 5，所以这两对数字都不应该被交织。
>>> magic_weave(0, 0, 5)
0^ 这个测试为 A 和 B 都传入了 0。然而，0 不是正数，而文档字符串指明如果前置条件不满足会引发异常。异常与答案 0 不是一回事，所以这不是一个能通过的 doctest。（不过，如果你同时选择了这个和下面那个前置条件失败的案例，我们给了部分分数，因为我们在课堂上没有展示过检查异常的 doctest。）
>>> magic_weave(101, 202, 0)
120012^ 这个测试为 C 传入了 0。然而，0 不是正整数，所以这个函数调用同样应该引发异常，而不是返回 0。（不过，如果你同时选择了这个和上面的那个，我们给了部分分数。）
>>> magic_weave(567, 899, 10)
586979^ 这个测试有两个问题。第一个问题是它只应该交织每个位置上 >= C 的数字，而没有一位数字 >= 10（因为单个数位不可能 >= 10）。另一个问题是前置条件指明 C 必须 < 10，所以这实际上应该引发异常。
定义域与值域
这道题要求你编写高阶函数来限制函数的定义域和值域。这些函数的灵感来源于生产代码中常用的用于检查函数输入参数是否有效的函数。它们非常实用，尤其是与 Python 装饰器结合使用时。
限制定义域
这个解法检查给定的 n 是否超出范围，如果是则返回 -Infinity，否则返回 f(n)。
def restrict_domain(f, min_d, max_d):
def helper(n):
if n < min_d or n > max_d:
return float("-inf")
return f(n)
return helper反过来做也是有效的：检查 n 是否在范围内，如果是则返回 f(n)。
def restrict_domain(f, min_d, max_d):
def helper(n):
if n >= min_d and n <= max_d:
return f(n)
return float("-inf")
return helper文档字符串说明范围是闭区间，即包含范围的开始和结束。因此，使用 n > min_d and n < max_d 是不正确的，因为 min_d 或 max_d 的值在这种情况下会被排除。请注意在问题中使用 >= 还是 >，以及是否有 doctest 检查范围的边界，因为这是编程中常见的错误来源。
限制值域
这个解法先计算 f(n) 的结果并将其存储在变量中。如果结果超出范围，则返回 -Infinity，否则返回结果。
def restrict_range(f, min_r, max_r):
def helper(n):
result = f(n)
if result < min_r or result > max_r:
return float("-inf")
return result
return helper另一个有效的方法是将 if 反过来：
def restrict_range(f, min_r, max_r):
def helper(n):
result = f(n)
if result >= min_r and result <= max_r:
return result
return float("-inf")
return helper有些解法选择不将结果存储在临时变量中：
def restrict_range(f, min_r, max_r):
def helper(n):
if f(n) >= min_r and f(n) <= max_r:
return f(n)
return float("-inf")
return helper这种方法需要调用 f(n) 三次，而 f(n) 可能是昂贵的计算，因此这不是最有效的解法。然而，我们给了满分，因为我们没有要求效率，而且对此讨论不多。此外，这个函数可以用在计算简单或已缓存的环境中，因此重复调用函数不会显著浪费计算时间。
同时限制
这道题要求你编写一个单一的高阶函数，依次调用两个函数来同时限制定义域和值域。
最简单的解法是组合这两个函数：
def restrict_both(f, min_d, max_d, min_r, max_r):
return restrict_range(restrict_domain(f, min_d, max_d), min_r, max_r)有些同学想出了更长但仍能工作并获得满分的解法，例如：
def restrict_both3(f, low_d, high_d, low_r, high_r):
def helper(x):
a1 = restrict_domain(f, low_d, high_d)(x)
if a1 != float("-inf"):
a2 = restrict_range(f, low_r, high_r)(x)
if a2 != float("-inf"):
return f(x)
return float("-inf")
return helper像这样的解法，先检查定义域再检查值域是很重要的。如果检查顺序不是这样，doctest 就会失败，因为测试 lambda 如果被传入 0 会导致 DivisionByZero 错误。如果有时间，请务必在 code.cs61a.org 中检查你的解法，并通过点击红色试管按钮运行 doctest，这可以帮助发现错误和边界情况。
如果你没有通过这道题，建议复习：
你可以清除之前的工作，重新尝试这些题目，看看这些概念是否已经理解。
数字替换器
这道题需要分解数字并重新组合的能力。我们在多个题目中练习过，从实验 1：数字求和开始。记住：
(n // 10)去掉数字的最后一位（345 // 10结果是 34）。(n % 10)获取数字的最后一位（345 % 10结果是 5）。(n * 10**pow)创建一个在pow次方位置上为n的数字（3 * 10**2结果是 300）。
我们通常从最右边的数字到最左边的数字依次处理，因为获取最右边的数字（使用 %）比获取最左边的数字更容易。
让我们看看如何将这些技巧用于迭代和递归解法。
迭代法
这个解法将新数字初始化为 0，10 的幂次初始化为 0，然后开始处理最右边的数字。如果 pred(digit) 为真，则计算 transform(digit)。然后将该位数字乘以当前的 10 的幂次并加到新数字中。递增 10 的幂次，去掉数字的最后一位，在循环的下一次迭代中继续。
def digit_replacer(pred, transform):
def func(n):
new_number = 0
power_of_ten = 0
while n > 0:
digit = n % 10
if pred(digit):
digit = transform(digit)
new_number += digit * 10**power_of_ten
power_of_ten += 1
n = n // 10
return new_number
return func因此，对于 n 为 345，如果不考虑数字变换，循环每次迭代的值如下：
| 循环开始 | n | digit | new_number | power_of_ten | n | 循环结束 |
| 345 | 5 | 5 (from 0 + 5 * 10**0) | 1 | 34 | ||
| 34 | 4 | 45 (from 5 + 4 * 10**1) | 2 | 3 | ||
| 3 | 3 | 345 (from 45 + 3 * 10**2) | 3 | 0 |
结合数字变换步骤后，加到新数字中的位数值可以根据需要改变。
递归法
递归解法使用类似的技巧。以下是一种解法：
def digit_replacer(pred, transform):
def func(n):
if n == 0:
return 0
digit = n % 10
if pred(digit):
digit = transform(digit)
return func(n // 10) * 10 + digit
return func基本情况是 n == 0，这与迭代方法中循环停止的情况相同。在考虑用迭代和递归两种方法解决同一问题时，请记住这一点——循环条件通常与基本情况相关。
递归调用通过传入去掉末尾的数字（n // 10）来分解问题，然后乘以 10 并加上该位数字。这与迭代方法中的 digit * 10**power_of_ten 非常相似。但是，它不需要乘以 10 的幂次，因为递归会自动处理（每次调用都会在下一个结果上加上 * 10）。你可以在这个关于交替数字（一个类似的问题）的视频中了解为什么这样可以工作。
递归方法有多种变体，也都获得了满分。它们主要在长度和中间变量的使用上有所不同。以下是一个例子：
def digit_replacer(pred, transform):
def replacer(n):
if n == 0:
return 0
if p(n % 10):
return replacer(n // 10) * 10 + f(n % 10)
return replacer(n // 10) * 10 + (n % 10)
return replacer如果你没有通过这道题，可以尝试做讲座 9（函数示例）中的题目，并复习讨论中的合并数字问题。
跑步检测器
这道题展示了如何使用嵌套函数来记住函数之前的输入。我们在 Hog 项目中的 commentary 和 say 函数中使用了类似的技巧。
以下是建议的解法：
def run_checker(condition, result):
def f(two_ago, one_ago):
def g(input):
if condition(two_ago, one_ago, input):
print(result(two_ago, one_ago, input))
else:
print("No run!")
return f(one_ago, input)
return g
return f(-1, -1)让我们逐步分析 doctest 示例：
>>> f = run_checker(lambda a, b, c: a > b > c and a >= 10,
lambda a, b, c: a*(b+c))当 run_checker 首次被调用时，它返回 f(-1, -1)，这返回对 g 函数的引用。这个 g 引用定义在 two_ago 为 -1、one_ago 为 -1 的环境中。
>>> f = f(15)对 f 的这次调用实际上是对 g 引用以输入 15 进行的调用。它检查 condition(-1, -1, 15)，发现其为 False，打印 "No run!"。然后返回 f(-1, 15)，这返回一个新的 g 函数引用。这个 g 引用定义在 two_ago 为 -1、one_ago 为 15 的环境中。
>>> f = f(10)对 f 的这次调用实际上是对最近的 g 引用以输入 10 进行的调用。它检查 condition(-1, 15, 10)，发现其为 False，打印 "No run!"。然后返回 f(15, 10)，这返回一个新的 g 函数引用。这个 g 引用定义在 two_ago 为 15、one_ago 为 10 的环境中。
>>> f = f(5)对 f 的这次调用实际上是对最近的 g 引用以输入 5 进行的调用。它检查 condition(15, 10, 5)，发现其为 True，打印 result(15, 10, 5)，即 225。然后返回 f(10, 5)，这返回一个新的 g 函数引用。这个 g 引用定义在 two_ago 为 10、one_ago 为 5 的环境中。
你可以继续跟踪 doctest（并在 PythonTutor 中尝试），但希望这能让你了解这类函数的工作方式。理解 Python 如何在环境中查找名称的值，以及认识到程序运行期间返回的每个 g 函数都有不同的环境，这一点很重要。
类似的问题：
- 考试准备：我的最后三个脑细胞（几乎一样！）
- 考试准备：自然链
两次测量，一次装杯
这本质上是一个划分计数问题。如果你之前从未见过，这会是一个相当困难的问题（尤其是在考试中）。 然而，我们在教材、讲座 7（幻灯片 39-45）和作业（硬币计数）中都见过这类问题。你在这门课中应该培养的一个能力是识别问题类型，并思考你过去学过哪些算法可以解决这类问题。然后你可以考虑具体的问题，它与学过的解法有什么不同，并相应地调整你的方法。
经典的 count_partitions(n, m) 问题计算用最大大小为 m 的部分组合成数字 n 有多少种方式。例如，count_partitions(6, 4) 结果是 9，因为用最大为 4 的数字组成 6 有九种方式：
- 6 = 2 + 4
- 6 = 1 + 1 + 4
- 6 = 3 + 3
- 6 = 1 + 2 + 3
- 6 = 1 + 1 + 1 + 3
- 6 = 2 + 2 + 2
- 6 = 1 + 1 + 2 + 2
- 6 = 1 + 1 + 1 + 1 + 2
- 6 = 1 + 1 + 1 + 1 + 1 + 1
count_coins(change) 问题计算用硬币组成 change 金额有多少种方式。因此，count_change(15) 结果是 6，因为用美国硬币组成 15 美分有六种方式：
- 15 个 1 美分硬币
- 10 个 1 美分，1 个 5 美分硬币
- 5 个 1 美分，2 个 5 美分硬币
- 5 个 1 美分，1 个 10 美分硬币
- 3 个 5 美分硬币
- 1 个 5 美分，1 个 10 美分硬币
这两个问题之间有一些差异：
count_partitions使用整数作为划分大小，因此它可以简单地递增 1 来找到下一个最大的划分大小。当划分大小 > m 时停止。（或者递减 1，当划分大小为 0 时停止）。count_coins使用硬币面值，因此必须使用一个函数来找到下一个最大的硬币面值。当硬币面值为None时停止。
这意味着我们可以对每个问题使用非常相似的方法，但需要改变找到下一个划分大小的方式和停止逻辑。
以下是 count_partitions 的教材解法：
def count_partitions(n, m):
"""Count the ways to partition n using parts up to m."""
if n == 0:
return 1
elif n < 0:
return 0
elif m == 0:
return 0
else:
return count_partitions(n-m, m) + count_partitions(n, m-1)通过重新解答或查看官方解法来复习 count_coins 的解法。
有哪些相同之处？
- 两者都有两个相同的基本情况：找到一个成功的划分时返回 1，超出范围时返回 0。
- 两者都返回两个递归调用的和：一个调用计算使用下一个最大部分的划分，另一个调用计算使用当前部分的划分。
有哪些不同之处？
count_coins函数使用了一个辅助函数，帮助我们跟踪当前硬币面值（因为count_coins只有一个参数，不足以用于跟踪）。- 与之相关的是，它调用一个函数来确定下一个硬币面值，而不是简单地递减。
- 它们的第三个基本情况条件不同，用于判断何时用完了划分大小。
count_partitions检查m == 0，而count_coins检查无效的最小硬币。
这引出了 measure_methods(grams_needed, available_sizes)。这个变体传入一个杯子尺寸列表，我们必须从该列表中选择划分大小。
以下是一个与 count_coins 解法相似的解法：
def measure_methods(grams_needed, available_sizes):
def measurer(grams_needed, cup_index):
if grams_needed < 0:
return 0
if grams_needed == 0:
return 1
if cup_index >= len(available_sizes):
return 0
without_cup = measurer(grams_needed, cup_index + 1)
with_cup = measurer(grams_needed - available_sizes[cup_index], cup_index)
return without_cup + with_cup
return measurer(grams_needed, 0)有哪些相同之处？前两个基本情况、两个递归调用的求和、以及使用辅助函数跟踪当前杯子尺寸。
有哪些不同之处？
- 辅助方法使用第二个参数跟踪当前列表索引（而不是当前硬币面值）。它从 0 开始，因为这是列表的第一个索引，然后在计算下一个最大杯子的划分的递归调用中加 1。
- 为了获取当前尺寸，它通过索引访问数组：
available_sizes[cup_index] - 第三个基本情况检查索引是否超出数组长度，使用
cup_index >= len(available_sizes)。
这道题有不少正确的解法，但它们本质上都做了同样的事情：找出某种方式来跟踪我们在数组中的位置并计算划分数，要么向上计数要么向下计数。
以下是一个向下计数的解法：
def measure_methods(total_needed, cup_sizes):
def helper(total_needed, curr_i):
if total_needed < 0:
return 0
elif curr_i < 0:
return 0
elif total_needed == 0:
return 1
else:
with_cup = helper(total_needed - cup_sizes[curr_i], curr_i)
without_cup = helper(total_needed, curr_i - 1)
return with_cup + without_cup
return helper(total_needed, len(cup_sizes) - 1)试着找出两种方法的差异！
如果你没有通过这道题，请重新尝试并复习 count_cups。如果你对两个递归调用如何完成划分计数感到困惑，你甚至可以画出完整的递归调用树。你会看到以 1 结尾的路径是正确的划分，而以 0 结尾的路径不是（要么因为总数太大，要么因为试图使用不存在的划分大小）。用任何能帮助你理解这种方法的方式来学习！:)