CS61A_Exam 1复盘

洛筱的行星观察笔记 / 2023-08-29 / 原文

从没有想过一些小小求余函数能给自己带来这么大的困扰。Exam1是一个很好

Q1 Run，K，Run

代码思路较为简单，但以填空的思路来思考，可以提升自身代码的规范性。为后续题目提供了方法的参考。

Q2 High Source

For the purposes of this problem, a score function is a pure function which takes a single number s as input and outputs another number, referred to as the score of s. Complete the best_k_segmenter function, which takes in a positive integer k and a score function score.

best_k_segmenter returns a function that takes in a single number n as input and returns the best k-segment of n, where a k-segment is a set of consecutive digits obtained by segmenting n into pieces of size k and the best segment is the segment with the highest score as determined by score. The segmentation is right to left.

For example, consider 1234567. Its 2-segments are 1, 23, 45 and 67 (a segment may be shorter than k if k does not divide the length of the number; in this case, 1 is the leftover, since the segmenation is right to left). Given the score function lambda x: -x, the best 2-segment is 1. With lambda x: x, the best segment is 67.

题目翻译：

看不懂题目描述，不会，求助Claude。得到代码如下。

def best_k_segmenter(k, score):
     partitioner = lambda x: (x // (10 * k), x % (10 * k))
    def best_getter(n):
        assert n > 0
        best_seg = None
        while n > 0:
            n, seg = partitioner(n)
            if best_seg is None or score(seg) > score(best_seg):
                best_seg = seg
        return best_seg
    return best_getter

乍一看觉得没有毛病，样例只通过了四个。这种情况下用PythonTutor来进行分析是较好的解决办法

从图上可以看出，是对n的分割出现了问题，应该分割的是10的次方 10^k,而不是10*k。出现问题的原因是Claude的部分代码未识别成代码，自己看的时候没有去想，想当然觉得他是对的。

应该修改为

partitioner = lambda x: (x // pow(10,k), x % pow(10,k))

代码分析

刚开始看到这种代码确实会非常头大，不知道如何分析。通过PythonTutor的逐帧分析可以系统地理解函数调用的逻辑。

（PS.帧（Frame）为CS61A中新了解的概念，之前仅知道全局/局部变量，函数调用栈等。具体参看（待填坑）

以本题的代码，结合上图为例来逐帧分析参数为函数，返回值为函数，以及传递匿名函数等问题。

全局帧

定义了best_k_segmenter函数
语句：largest_pair_getter = best_k_segmenter(2, lambda x: x)

这个函数调用了f1 best_k_segmenter,在f1的帧里面定义了f3 匿名函数以及 f2 best_getter，但其并未执行。f1 best_k_segmenter的作用是返回f2 best_getter函数。即这条语句执行之后，largest_pair_getter即表示f2 best_getter(带有两个f1帧的实际参数）
largest_pair_getter(12345)
这句代码才是真正执行了 best_getter（12345）
best_getter中， n, seg = partitioner(n)则调用了匿名函数，传入的参数为形参n的实参取值12345。匿名函数的两个表达式值分别复制给n，seg
至此这个函数的条理就清晰了。多借用PythonTutor，更好地看懂代码。