跳转至

高阶函数、递归和homework 2

hw2: Recursion

作业地址：Homework 2 | CS 61A Fall 2020

第二题：Ping-pong

题目描述：Ping-pong

“Ping-pong”序列从1起数，要么递增要么递减。对于第k个元素，如果k能被8整除，或者k含有8，那么递增/递减的方向将改变。例如，第8、16、18、24、28个元素后，序列计数方向将改变。

实现一个函数pingpong，在不使用任何赋值语句的情况下，返回第n个元素的值。

Implement a function pingpong that returns the nth element of the ping-pong sequence without using any assignment statements.

提示：可以使用num_eights（第一题所做函数）来判断数字中是否存在8。

这个题我是横竖没想到怎么在不用赋值语句的情况下确定方向的，直到我看了hint video，然后发现老师直接整了个closure......这属于是绕开了检测程序了属于是，本质上还是在赋值：

Ping-pong
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
def pingpong(n):

    def pp_helper(index, dir, ppn):
        if n == 1:
            return 1
        elif index == n:
            return ppn
        else:
            if index % 8 == 0 or num_eights(index) != 0:
                return pp_helper(index + 1, -dir, ppn-dir)
            else:
                return pp_helper(index + 1, dir, ppn+dir)
    return pp_helper(1,1,1)
说白了，闭包函数pp_helper里的三个参数可以都算作assignment statements（赋值语句），相当于index,dir,ppn = 1,1,1，三者的意义分别是（1）ping-pong序列的序号；（2）变化方向,dir = 1递增，dir = -1递减；（3）ppn是ping-pong序列第index个值。

那么，经过了这种特殊的“赋值”，一切就变得明朗，直接通过pp_helper的参数来做递归，index == n了就输出ppn，一切就很水到渠成。而且序号符合变向条件时，也是在下一个值上变向，所以不需要在前一个序号上考虑变向。

我唯一感到疑惑的是if n == 1: return 1这句，去掉这个判断，运行pingpong(1)同样可以得到1，因为elif index == n: return ppn得到的结果相同，通过PythonTutor Visualizer做函数结构的可视化，得到的结果也是相同的。

第四题：Count coins

这道题属于是Tree Recursion：

Count coins
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
def count_coins(total):
    def total_helper(least, n):
        if least is None: #next_largest_coin(25) = None
            return 0
        elif least == n: #递归吸收1：最小硬币面值恰好为n，只有一种
            return 1
        elif least > n: #递归吸收2：最小硬币面值大于n，没有可能
            return 0
        with_c = total_helper(least, n - least)
        without_c = total_helper(next_largest_coin(least), n)
        return with_c + without_c
    return total_helper(1, total)

我们假定当前最小面值为least，还没有配出来的余额为n，那么接下来有两个情况：

  1. 下一个硬币仍然是当前的“最小面值”least，但这样的话还没有配出的额度为n-least；
  2. 下一个硬币是当前最小面值的下一个稍大的面值(next_largest_coin(least))。这样的话，只是调整了least的设定，而没有真正地配置一个硬币进去。

每一种情况都继续向下分裂为上面所说的两种情况，从而将每一种吸收的情况都讨论到（也就是最上面的if-elif-elif），然后把这些情况中返回的0或1加起来。

Lab04: Recursion

类似的Tree Recursion还有Lab04的第四题（Insect Combinatorics）：Lab 4 Q4

给定M行N列的矩形地图，一个昆虫只能向右或向上移动，求出从左下角(0,0)到右上角(M-1,N-1)的可能路径数。直接给出代码：

Insect Combinatorics
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
def paths(m, n):

    def path_helper(x,y):
        if x >= m:
            return 0
        elif y >= n:
            return 0
        elif x == m-1 and y == n-1:
            return 1
        right = path_helper(x, y+1)
        upward = path_helper(x+1, y)
        return right + upward

    return path_helper(0,0)
闭包确实有好使的时候，但我老是想不到。

还有第五题，这个题讨论的是留不留最后一位：

maximum subsequence
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
def max_subseq(n, t):

    if n == 0 or t == 0:
        return 0
    elif n <= 10**t:
        return n
    with_ones = max_subseq(n // 10, t-1) * 10 + n % 10
    not_with = max_subseq(n // 10, t)
    if with_ones > not_with:
        return with_ones
    else:
        return not_with

评论