作业2: 递归
Homework 2: Recursion

hw02.zip

Due by 11:59pm on Thursday, September 24

查看英文原文

说明

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

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

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

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

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

必答题

Q1: 数字8的个数

编写一个递归函数 num_eights，该函数接受一个正整数 x 并返回数字 8 在 x 中出现的次数。请使用递归实现 —— 如果使用了赋值语句，测试将无法通过。

def num_eights(x):
    """Returns the number of times 8 appears as a digit of x.

    >>> num_eights(3)
    0
    >>> num_eights(8)
    1
    >>> num_eights(88888888)
    8
    >>> num_eights(2638)
    1
    >>> num_eights(86380)
    2
    >>> num_eights(12345)
    0
    >>> from construct_check import check
    >>> # ban all assignment statements
    >>> check(HW_SOURCE_FILE, 'num_eights',
    ...       ['Assign', 'AugAssign'])
    True
    """
    "*** YOUR CODE HERE ***"

观看下面的提示视频来获得一些初步的指导

使用 Ok 来测试你的代码：

python3 ok -q num_eights --local

Q2: 乒乓数列

乒乓数列从 1 开始计数，并且始终在递增或递减。在第 k 个元素处，如果 k 是 8 的倍数或包含数字 8，则改变计数方向。下列是乒乓数列的前 30 个元素，其中在第 8、16、18、24 和 28 个元素处使用括号标记了计数方向的切换：

Index	1	2	3	4	5	6	7	[8]	9	10	11	12	13	14	15	[16]	17	[18]	19	20	21	22	23
PingPong Value	1	2	3	4	5	6	7	[8]	7	6	5	4	3	2	1	[0]	1	[2]	1	0	-1	-2	-3

Index (cont.)	[24]	25	26	27	[28]	29	30
PingPong Value	[-4]	-3	-2	-1	[0]	-1	-2

实现一个函数 pingpong，返回乒乓数列的第 n 个元素，且不得使用任何赋值语句。

你可以使用在上一题中定义的函数 num_eights。

请使用递归实现 —— 如果使用了赋值语句，测试将无法通过。

提示：如果卡住了，可以先尝试使用赋值语句和 while 循环来实现 pingpong。然后，为了将其转换为递归的解法，可以编写一个辅助函数，让它的参数涵盖 while 循环中所有会变化的变量。

def pingpong(n):
    """Return the nth element of the ping-pong sequence.

    >>> pingpong(8)
    8
    >>> pingpong(10)
    6
    >>> pingpong(15)
    1
    >>> pingpong(21)
    -1
    >>> pingpong(22)
    -2
    >>> pingpong(30)
    -2
    >>> pingpong(68)
    0
    >>> pingpong(69)
    -1
    >>> pingpong(80)
    0
    >>> pingpong(81)
    1
    >>> pingpong(82)
    0
    >>> pingpong(100)
    -6
    >>> from construct_check import check
    >>> # ban assignment statements
    >>> check(HW_SOURCE_FILE, 'pingpong', ['Assign', 'AugAssign'])
    True
    """
    "*** YOUR CODE HERE ***"

观看下面的提示视频来获得一些初步的指导

使用 Ok 来测试你的代码：

python3 ok -q pingpong --local

Q3: 缺失的数字

编写一个递归函数 missing_digits，该函数接受一个按递增顺序排列的数字 n （例如，12289 是有效的，但 15362 和 98764 不是）。它返回 n 中缺失的数字个数。缺失数字指的是在 n 的首位和末位数字之间但未出现在 n 中的数字。 请使用递归实现 —— 如果使用了 while 或 for 循环，测试将无法通过。

def missing_digits(n):
    """Given a number a that is in sorted, increasing order,
    return the number of missing digits in n. A missing digit is
    a number between the first and last digit of a that is not in n.
    >>> missing_digits(1248) # 3, 5, 6, 7
    4
    >>> missing_digits(1122) # No missing numbers
    0
    >>> missing_digits(123456) # No missing numbers
    0
    >>> missing_digits(3558) # 4, 6, 7
    3
    >>> missing_digits(35578) # 4, 6
    2
    >>> missing_digits(12456) # 3
    1
    >>> missing_digits(16789) # 2, 3, 4, 5
    4
    >>> missing_digits(19) # 2, 3, 4, 5, 6, 7, 8
    7
    >>> missing_digits(4) # No missing numbers between 4 and 4
    0
    >>> from construct_check import check
    >>> # ban while or for loops
    >>> check(HW_SOURCE_FILE, 'missing_digits', ['While', 'For'])
    True
    """
    "*** YOUR CODE HERE ***"

观看下面的提示视频来获得一些初步的指导

使用 Ok 来测试你的代码：

python3 ok -q missing_digits --local

Q4: 计算硬币组合

给定一个正整数 total，如果一组硬币的总面值等于 total，则该组硬币可以用于找零。这里我们使用标准的美国硬币面值：1、5、10、25。例如，以下几种硬币组合可以凑成 15：

15 枚 1 美分硬币
10 枚 1 美分硬币，1 枚 5 美分硬币
5 枚 1 美分硬币，2 枚 5 美分硬币
5 枚 1 美分硬币，1 枚 10 美分硬币
3 枚 5 美分硬币
1 枚 5 美分硬币，1 枚 10 美分硬币

因此，总共有 6 种方法可以凑出 15。请编写一个递归函数 count_coins，它接受一个正整数 total，并返回使用硬币凑出 total 的不同组合数。请使用提供的 next_largest_coin 函数来计算当前硬币面值的下一个更大面值。例如： next_largest_coin(5) = 10。

提示： 参考分割数的实现，该函数展示了如何使用较小的部分来计算总和的不同方式。如果在递归调用中需要跟踪多个值，可以考虑编写一个辅助函数。

def next_largest_coin(coin):
    """Return the next coin. 
    >>> next_largest_coin(1)
    5
    >>> next_largest_coin(5)
    10
    >>> next_largest_coin(10)
    25
    >>> next_largest_coin(2) # Other values return None
    """
    if coin == 1:
        return 5
    elif coin == 5:
        return 10
    elif coin == 10:
        return 25

def count_coins(total):
    """Return the number of ways to make change for total using coins of value of 1, 5, 10, 25.
    >>> count_coins(15)
    6
    >>> count_coins(10)
    4
    >>> count_coins(20)
    9
    >>> count_coins(100) # How many ways to make change for a dollar?
    242
    >>> from construct_check import check
    >>> # ban iteration
    >>> check(HW_SOURCE_FILE, 'count_coins', ['While', 'For'])                                          
    True
    """
    "*** YOUR CODE HERE ***"

观看下面的提示视频来获得一些初步的指导

使用 Ok 来测试你的代码：

python3 ok -q count_coins --local

Submit

Make sure to submit this assignment by running:

python3 ok --submit

趣味问题

这个问题展示了如何在全局框架(Global Frame) 中，不使用函数名称来编写递归函数。

Q5: 匿名阶乘

递归实现的阶乘函数可以通过使用条件表达式将其写成一个单一的表达式。

>>> fact = lambda n: 1 if n == 1 else mul(n, fact(sub(n, 1)))
>>> fact(5)
120

然而，这个实现依赖于 fact 的名字。在上面的例子中， fact 有一个名字，我们在 fact 的主体中引用了这个名字。为了编写递归函数，我们通常会使用 def 或赋值语句为函数命名，以便我们可以在函数体内引用它。在这个问题中，你的任务是递归地定义fact，而不为它命名！

写一个表达式，计算 n 的阶乘，仅使用调用表达式、条件表达式和lambda表达式（不使用赋值或 def 语句）。特别注意，你不允许在返回表达式中使用 make_anonymous_factorial。 operator 模块中的 sub 和 mul 函数是解决这个问题所需的唯一内置函数：

from operator import sub, mul

def make_anonymous_factorial():
    """Return the value of an expression that computes factorial.

    >>> make_anonymous_factorial()(5)
    120
    >>> from construct_check import check
    >>> # ban any assignments or recursion
    >>> check(HW_SOURCE_FILE, 'make_anonymous_factorial', ['Assign', 'AugAssign', 'FunctionDef', 'Recursion'])
    True
    """
    return 'YOUR_EXPRESSION_HERE'

使用 Ok 来测试你的代码：

python3 ok -q make_anonymous_factorial --local