【CS61A 2024秋】Python入门课，全过程记录P4（Week7 Generators开始，更新于2025/1/30）

关于

个人博客，里面偶尔更新，最近比较忙。发一些总结的帖子和思考。

江湖有缘相见🤝。如果读者想和我交个朋友可以加我好友（见主页or个人博客），共同学习。笔者是学生，课业还是比较繁重的，可能回复不及时。笔者也正在四处寻找一些可以兼职锻炼知识并且补贴一些生活的工作，如果读者需要一些详细的辅导，或者帮助完成一些简易的lab也可以找我，笔者还是学生，自以为才学有限，也没有高价的理由📖。

基本介绍👋

CS61A是加州大学伯克利分校（UC Berkeley）计算机科学专业的入门课程，全名为Structure and Interpretation of Computer Programs。

这是入门的Python课程，因此这篇博客会默认读者没有很多的编程背景，讲的东西会比较基础，有编程经验的读者可以快速浏览。

首先贴上课程网址。
CS61A课程主页

新的问题

可以发现，cs61a归档了，而这个网站是需要Berkeley账号的，还是没法登录。这时候笔者决定使用档案馆网站，去翻网页的归档了。虽然有点难受，但是还能用orz。

对了，textbook是可以直接访问的，在这里

更好的解决方案

我在GitHub上找到了cs61a 2024 fall的归档，这里给出连接link

Week7

Mon Generators

阅读材料

Generator也是相当重要的概念，之前没怎么遇到过，学习起来也是抽象一些。

 >>> def plus_minus(x): 
		yield x 
		yield -x 
>>> t = plus_minus(3) 
>>> next(t) 
3 
>>> next(t) 
-3 
>>> t 
<generator object plus_minus ...

generator的函数不用return而是用yield，调用后返回一个generator对象，可以对其使用next，指向到下一个yield的元素。

这里调用第三次就到尽头了。generator特别适合那种无限生成的数列。比如斐波那契数列。

Lab 05: Iterators, Mutability

Q1: WWPD: List-Mutation

问答题。略。

Q2: Insert Items

在所有值为before的元素后面插入after。

def insert_items(s, before, after):
    """Insert after into s after each occurrence of before and then return s.

    >>> test_s = [1, 5, 8, 5, 2, 3]
    >>> new_s = insert_items(test_s, 5, 7)
    >>> new_s
    [1, 5, 7, 8, 5, 7, 2, 3]
    >>> test_s
    [1, 5, 7, 8, 5, 7, 2, 3]
    >>> new_s is test_s
    True
    >>> double_s = [1, 2, 1, 2, 3, 3]
    >>> double_s = insert_items(double_s, 3, 4)
    >>> double_s
    [1, 2, 1, 2, 3, 4, 3, 4]
    >>> large_s = [1, 4, 8]
    >>> large_s2 = insert_items(large_s, 4, 4)
    >>> large_s2
    [1, 4, 4, 8]
    >>> large_s3 = insert_items(large_s2, 4, 6)
    >>> large_s3
    [1, 4, 6, 4, 6, 8]
    >>> large_s3 is large_s
    True
    """
    "*** YOUR CODE HERE ***"
    i = 0
    while i < len(s):
        if s[i] == before:
            s.insert(i + 1, after)
            i += 1
        i += 1
    return s

Q3: Group By

将容器里的元素，根据传入的fn的函数值分组。

def group_by(s, fn):
    """Return a dictionary of lists that together contain the elements of s.
    The key for each list is the value that fn returns when called on any of the
    values of that list.

    >>> group_by([12, 23, 14, 45], lambda p: p // 10)
    {1: [12, 14], 2: [23], 4: [45]}
    >>> group_by(range(-3, 4), lambda x: x * x)
    {9: [-3, 3], 4: [-2, 2], 1: [-1, 1], 0: [0]}
    """
    grouped = {}
    for x in s:
        key = fn(x)
        if key in grouped:
            grouped[key].append(x)
        else:
            grouped[key] = [x]
    return grouped

Q4: WWPD: Iterators

略。

Q5: Count Occurrences

使用next，查看前n个元素中有多少元素等于x。

def count_occurrences(t, n, x):
    """Return the number of times that x is equal to one of the
    first n elements of iterator t.

    >>> s = iter([10, 9, 10, 9, 9, 10, 8, 8, 8, 7])
    >>> count_occurrences(s, 10, 9)
    3
    >>> t = iter([10, 9, 10, 9, 9, 10, 8, 8, 8, 7])
    >>> count_occurrences(t, 3, 10)
    2
    >>> u = iter([3, 2, 2, 2, 1, 2, 1, 4, 4, 5, 5, 5])
    >>> count_occurrences(u, 1, 3)  # Only iterate over 3
    1
    >>> count_occurrences(u, 3, 2)  # Only iterate over 2, 2, 2
    3
    >>> list(u)                     # Ensure that the iterator has advanced the right amount
    [1, 2, 1, 4, 4, 5, 5, 5]
    >>> v = iter([4, 1, 6, 6, 7, 7, 6, 6, 2, 2, 2, 5])
    >>> count_occurrences(v, 6, 6)
    2
    """
    "*** YOUR CODE HERE ***"
    cnt = 0
    has = 0
    while cnt < n:
        cnt += 1
        if next(t) == x:
            has += 1
    return has

Q6: Repeated

连续出现k次的数。

def repeated(t, k):
    """Return the first value in iterator t that appears k times in a row,
    calling next on t as few times as possible.

    >>> s = iter([10, 9, 10, 9, 9, 10, 8, 8, 8, 7])
    >>> repeated(s, 2)
    9
    >>> t = iter([10, 9, 10, 9, 9, 10, 8, 8, 8, 7])
    >>> repeated(t, 3)
    8
    >>> u = iter([3, 2, 2, 2, 1, 2, 1, 4, 4, 5, 5, 5])
    >>> repeated(u, 3)
    2
    >>> repeated(u, 3)
    5
    >>> v = iter([4, 1, 6, 6, 7, 7, 8, 8, 2, 2, 2, 5])
    >>> repeated(v, 3)
    2
    """
    assert k > 1
    "*** YOUR CODE HERE ***"
    last_v = -1
    cnt = 0
    while True:
        x = next(t)
        if x != last_v:
            cnt = 1
            last_v = x
        else:
            cnt += 1
        if cnt == k:
            return last_v

Q7: Sprout Leaves

在树的末端添加新的分支叶子，sprout是发芽的意思。

def sprout_leaves(t, leaves):
    """Sprout new leaves containing the labels in leaves at each leaf of
    the original tree t and return the resulting tree.

    >>> t1 = tree(1, [tree(2), tree(3)])
    >>> print_tree(t1)
    1
      2
      3
    >>> new1 = sprout_leaves(t1, [4, 5])
    >>> print_tree(new1)
    1
      2
        4
        5
      3
        4
        5

    >>> t2 = tree(1, [tree(2, [tree(3)])])
    >>> print_tree(t2)
    1
      2
        3
    >>> new2 = sprout_leaves(t2, [6, 1, 2])
    >>> print_tree(new2)
    1
      2
        3
          6
          1
          2
    """
    "*** YOUR CODE HERE ***"
    if is_leaf(t):
        return tree(label(t), [tree(leaf) for leaf in leaves])
    new_branch = []
    for b in branches(t):
        new_branch.append(sprout_leaves(b, leaves))
    return tree(label(t), new_branch)

Q8: Partial Reverse

翻转从start开始的列表。

def partial_reverse(s, start):
    """Reverse part of a list in-place, starting with start up to the end of
    the list.

    >>> a = [1, 2, 3, 4, 5, 6, 7]
    >>> partial_reverse(a, 2)
    >>> a
    [1, 2, 7, 6, 5, 4, 3]
    >>> partial_reverse(a, 5)
    >>> a
    [1, 2, 7, 6, 5, 3, 4]
    """
    "*** YOUR CODE HERE ***"
    i, j = start, len(s) - 1
    while i < j:
        s[i], s[j] = s[j], s[i]
        i += 1
        j -= 1

Wed Objects

阅读材料

一个典型的Python类。

Disc 06: Generators

Q1: Big Fib

使用generator的性质，获取第一个大于2024的斐波那契数。filter和next功能强大啊。

def gen_fib():
    n, add = 0, 1
    while True:
        yield n
        n, add = n + add, n

next(filter(lambda n: n > 2024, gen_fib()))

这样写就能获取到一个大于2024的数了。

Q2: Something Different