Week5-Lecture11-12

2026-09-162026-09-16

Presidents' Day¶

Lab 03: Recursion, Python Lists¶

Python
# 1.close
def close(s: list[int], k: int) -> int:
    assert k >= 0
    count = 0
    for i in range(len(s)):  # Use a range to loop over indices
        if abs(s[i] - i) <= k:
            count += 1
    return count

# 2.close_list
def close_list(s: list[int], k: int) -> list[int]:
    assert k >= 0
    return [s[i] for i in range(len(s)) if abs(s[i] - i) <= k]

# 3.recursive double_eights
def double_eights(n: int) -> bool:
    if n % 100 == 88:
        return True
    if n == 0:
        return False
    return double_eights(n // 10)

# 4.make_onion
def make_onion(f, g):
    def can_reach(x, y, limit):
        if limit < 0:
            return False
        elif x == y:
            return True
        else:
            return can_reach(f(x), y, limit - 1) or can_reach(g(x), y, limit - 1)
    return can_reach

# 5.repeater
def make_func_repeater(f, x):
    def repeat(k):
        if k == 1:
            return f(x)
        else:
            return f(repeat(k-1))
    return repeat

Lecture 11 Sequence¶

Reading 2.1 Introduction of building abstractions with data¶

Effective use of built-in and user-defined data types are fundamental to data processing applications

2.1.1 Native data types¶

Python中的每个值都有一个决定其类型的类。

Python
type() #使用type函数来检查任何值的类

literals（字面量）evaluate to values of native types
built-in functions and operators to manipulate values of native types

python包含3种原生数值类型：int, float, complex
非数值类型：非常多

Reading 2.3 Sequences¶

A sequence is an ordered collection of values.

length: a sequence has a finite length
element selection: 索引

2.3.1 Lists¶

列表的基本操作

2.3.2 Sequence Iteration¶

使用for语句来遍历

Python
for <name> in <expression>:
    <suite>

sequence unpacking: 将多个名称绑定到多个值

Ranges: 创建range对象，前闭后开

2.3.3 Sequence Processing¶

序列是一种常见的复合数据形式，一个程序经常围绕着一种序列抽象编排。序列作为模块输入/输出配合管道，可以完成很复杂且每个模块很清晰/专门的数据操作。

列表推导式

Python
[<map expression> for <name> in <sequence expression> if <filterr expression>]

aggregation
把序列里的所有值聚合为单个值，如sum, min, max

Higher-Order Functions

Conventional Names 惯用名称，
apply_to_all: map
keep_if: filter

2.3.4 Sequence Abstraction¶

Membership: 用in/not in 判断一个值是否在一个序列里面
slicing: 切片

关于抽象：抽象的属性越多能满足越多要求，但负面后果是需要更多的时间去学习

2.3.5 Strings¶

字符串是另一种抽象，需要大量时间去掌握

2.3.6 Trees¶

如果组合数据值的结果本身能够使用相同的方法进行再次组合，那么这种组合方法就具有闭包属性。

树有一个根标签和一系列分支。树的每个分支本身也是一棵树。没有分支的树是叶子。树中每个子树的根都是一个节点

Python
def tree(root_label, branches=[]):
    for branch in branches:
        assert is_tree(branch), 'branches must be trees'
    return [root_label] + list(branches)

def label(tree):
    return tree[0]

def branches(tree):
    return tree[1:]

def is_tree(tree):
    if type(tree) != list or len(tree) < 1:
        return False
    for branch in branches(tree):
        if not is_tree(branch):
            return False
    return True

def is_leaf(tree):
    return not branches(tree)

def fib_tree(n):
    if n == 0 or n == 1:
        return tree(n)
    else:
        left, right = fib_tree(n-2), fib_tree(n-1)
        fib_n = label(left) + label(right)
        return tree(fib_n, [left, right])

def count_leaves(tree):
    if is_leaf(tree):
        return 1
    else:
        branch_count = [count_leaves(b) for b in branches(tree)]
        return sum(branch_count)

分区树（partition trees）

2.3.7 Linked Lists¶

A common representation of a sequence constructed from nested pairs is called a linked list.

Disc04: Tree Recursion¶

Python
def paths(m, n):
    if m == 1 or n == 1:
        return 1 
    return paths(m-1, n) + paths(m, n-1)

def max_product(s):
    if s == []:
        return 1
    elif len(s) == 1:
        return s[0]
    else:
        return max(max_product(s[2:]) * s[0], max_product(s[1:]))

def sums(n, m):
    if n < 0:
        return []
    if n == 0:
        sums_to_zero = []     # The only way to sum to zero using positives
        return [sums_to_zero] # Return a list of all the ways to sum to zero
    result = []
    for k in range(1, m + 1):
        result = result + [[k] + rest for rest in sums(n-k, m) if rest == [] or rest[0] != k]
    return result

def fit(total, n):
    def f(total, n, k):
        if total == 0 and n == 0: 
            #递归结束条件
            return True
        elif total < k * k:
            return False
        else:
            return f(total, n, k + 1) or f(total - k*k, n-1, k) 
            #对于每个数字，决定用或者不用，会形成一棵树
    return f(total, n, 1)

Lecture 12 Containers¶

Project2 Cats¶

Project2-Cats