【CS61A】CS61A——Recursion

发表于 2025-02-05 更新于 2025-07-31 分类于 CS61A
本文字数： 1.3k 阅读时长 ≈ 2 分钟

Recursion

Recursive Functions

定义：在函数体中直接或间接调用自身的函数叫递归函数

即在执行函数体时还会调用若干次函数自身

递归函数的结构：

def头定义
条件语句用来判断基本条件，无递归调用（递归出口）
递归条件用来递归调用

判断递归是否正确：

验证基本条件
将递归函数看作函数抽象
假设f(n-1)正确，验证f(n)的正确性

e.g.1:用递归求各位数字和

def split(n):
    """把n分成最后一位与其他位两部分"""
    return n//10, n%10

def sum_digits(n):
    """求和各位数字"""
    if n<10:
        return n
    else:
        all_but_last,last = split(n)
        return sum_digits(all_but_last)+last

e.g.2:阶乘（使用diagram）

递归与迭代

递归转换到迭代：弄清需要通过迭代保持的状态

迭代转换到递归：迭代保持的状态可以通过参数传递

互递归（Mutual Recursion）

e.g. Luhn Algorithm

改算法常用于信用卡等的校验码计算，步骤如下：

步骤 1：反转数字

算法首先通过反转您正在检查的数字的数字。

步骤 2：每隔一个数字翻倍

从左侧的第一个数字开始（由于反转，现在是原始数字的最后一个数字），对每个第二个数字进行翻倍。

步骤 3：求乘积的数字之和

如果翻倍后的数字大于 9，则将乘积的数字相加（例如，翻倍 8 得到 16，因此相加 1 + 6 = 7）。

步骤 4：将所有数字相加

在上述操作后，将所有数字相加。

步骤 5：检查是否能被 10 整除

如果总和能被 10 整除（即以 0 结尾），则该数字根据 Luhn 算法是有效的。否则，它是无效的。

def split(n):
    """把n分成最后一位与其他位两部分"""
    return n//10, n%10

def sum_digits(n):
    """求和各位数字"""
    if n<10:
        return n
    else:
        all_but_last,last = split(n)
        return sum_digits(all_but_last)+last

def luhn_sum(n):
    if n<10:
        return n
    else:
        all_but_last, last = split(n)
        return luhn_sum_double(all_but_last)+last

def luhn_sum_double(n):
    all_but_last, last = split(n)
    luhn_digit = sum_digits(2*last)
    if n<10:
        return luhn_digit
    else:
        return luhn_sum(all_but_last)+luhn_digit

这里使用互递归让分离出来的数字奇数位不执行乘二操作，偶数位执行乘二操作

【CS61A】CS61A——Design

发表于 2025-02-05 更新于 2025-07-31 分类于 CS61A
本文字数： 1.2k 阅读时长 ≈ 2 分钟

Functional Abstraction

Lambda表达式所在的environment关系

如下例子

a = 1
def f(g):
    a = 2
    return lambda y:a*g(y)
f(lambda y: a+y)(a)

注意行4与行5的lambda函数的区别：

行4的lambda函数是f函数内定义的函数，他的父级为f，因此此时传入的a=2
行5的lambda函数是f函数外定义的函数，他的父级为global，因此此时传入的a=1

Choosing Names

给函数或变量命名时，要注重传达意思

命名需要传达与之相关值的意义或目的
值的类型最好记录在函数的docstring中
函数名一般包括它们的作用，表现或返回值
为一些重复使用的复合表达式命名
如果需要注释代码，命名可以长一些
如果用于数字，数学运算与函数抽象，命名可以短一些

Error&Traceback

报错有三种形式：

Syntax errors：执行前即可发现，通常由于表达式不正确引起
Runtime errors：执行时由python解释器发现的错误。当这些错误发生时，会得到一个Traceback，来提示是在哪里发生了何种错误，错误发生时程序在做什么
Logical error：不会被解释器发现，需要自己进行测试发现问题

Decorator

装饰器用于给现有模块（原函数）进行功能拓展，通过接受一个函数来返回一个新的函数或修改原来的函数

例如：

def trace1(fn):
    """
    return a version of fn that first print before it is called
    fn - a function of 1 argument
    """
    def traced(x):
        print("Calling",fn,"on argument",x)
        return fn(x)
    return traced

@trace1
def square(x):
    return x*x

等同于

def trace1(fn):
    """
    return a version of fn that first print before it is called
    fn - a function of 1 argument
    """
    def traced(x):
        print("Calling",fn,"on argument",x)
        return fn(x)
    return traced

def square(x):
    return x*x
square = trace1(square)

返回值都相同

>>> square(5)
Calling  on argument 5
25

【字符串】KMP

发表于 2025-02-03 更新于 2025-12-18 分类于算法与数据结构，字符串
本文字数： 2.1k 阅读时长 ≈ 4 分钟

介绍了KMP算法的原理与用法，用于字符串模式串在主串中的搜索

阅读全文 »

【字符串】字典树

发表于 2025-02-01 更新于 2025-12-18 分类于算法与数据结构，字符串
本文字数： 6k 阅读时长 ≈ 11 分钟

介绍了字典树的原理与使用

阅读全文 »

【CS61A】CS61A——Lab2

发表于 2025-01-30 更新于 2025-07-31 分类于 CS61A
本文字数： 3.1k 阅读时长 ≈ 6 分钟

WWPD部分省略

Composite Identity Function

题意：写一个函数，传入f与g两个函数，返回一个含有参数x的函数，用于判断\(f(g(x))\)是否等于\(g(f(x))\)

def composite_identity(f, g):
    """
    Return a function with one parameter x that returns True if f(g(x)) is
    equal to g(f(x)). You can assume the result of g(x) is a valid input for f
    and vice versa.

    >>> add_one = lambda x: x + 1        # adds one to x
    >>> square = lambda x: x**2          # squares x [returns x^2]
    >>> b1 = composite_identity(square, add_one)
    >>> b1(0)                            # (0 + 1) ** 2 == 0 ** 2 + 1
    True
    >>> b1(4)                            # (4 + 1) ** 2 != 4 ** 2 + 1
    False
    """
    return lambda x: f(g(x))==g(f(x))

按照题意返回一个lambda函数，传入x即可

Count Cond

predicate function: 返回True或False的函数

题意：写一个函数，传入一个两个参数的predicate function condition，返回一个含有参数n的函数，判断1-n中有几个数满足condition函数

def count_cond(condition):
    """Returns a function with one parameter N that counts all the numbers from
    1 to N that satisfy the two-argument predicate function Condition, where
    the first argument for Condition is N and the second argument is the
    number from 1 to N.

    >>> count_fives = count_cond(lambda n, i: sum_digits(n * i) == 5)
    >>> count_fives(10)   # 50 (10 * 5)
    1
    >>> count_fives(50)   # 50 (50 * 1), 500 (50 * 10), 1400 (50 * 28), 2300 (50 * 46)
    4

    >>> is_i_prime = lambda n, i: is_prime(i) # need to pass 2-argument function into count_cond
    >>> count_primes = count_cond(is_i_prime)
    >>> count_primes(2)    # 2
    1
    >>> count_primes(3)    # 2, 3
    2
    >>> count_primes(4)    # 2, 3
    2
    >>> count_primes(5)    # 2, 3, 5
    3
    >>> count_primes(20)   # 2, 3, 5, 7, 11, 13, 17, 19
    8
    """
    def judge(n):
        cnt = 0
        for i in range(1,n+1):
            if condition(n,i):
                cnt+=1
        return cnt
    return judge

遍历1-n，传入condition函数并计数即可

注意返回的是函数，传入n

Multiple

题意：写一个函数求参数a，b的最小公倍数

def multiple(a, b):
    """Return the smallest number n that is a multiple of both a and b.

    >>> multiple(3, 4)
    12
    >>> multiple(14, 21)
    42
    """
    def gcd(a,b):
        if b==0:
            return a
        return gcd(b,a%b)
    return a*b//gcd(a,b)

辗转相除法求gcd，用gcd求lcm

I Heard You Liked Functions…

题意：定义一个函数传入三个函数f1,f2,f3，返回一个参数为n的函数g，函数g返回一个参数为x的函数h

函数x将会循环传给函数f1，f2，f3，具体如下：

n=0时返回x，n=1时返回f1(x)，n=2时返回f2(f1(x))，n=3时返回f3(f2(f1(x)))，n=4时返回f1(f3(f2(f1(x))))，以此类推

def cycle(f1, f2, f3):
    """Returns a function that is itself a higher-order function.

    >>> def add1(x):
    ...     return x + 1
    >>> def times2(x):
    ...     return x * 2
    >>> def add3(x):
    ...     return x + 3
    >>> my_cycle = cycle(add1, times2, add3)
    >>> identity = my_cycle(0)
    >>> identity(5)
    5
    >>> add_one_then_double = my_cycle(2)
    >>> add_one_then_double(1)
    4
    >>> do_all_functions = my_cycle(3)
    >>> do_all_functions(2)
    9
    >>> do_more_than_a_cycle = my_cycle(4)
    >>> do_more_than_a_cycle(2)
    10
    >>> do_two_cycles = my_cycle(6)
    >>> do_two_cycles(1)
    19
    """
    def g(n):
        def h(f,g):
            return lambda x: f(g(x))
        if n==0:
            return lambda x : x
        elif n==1:
            return f1
        else:
            temp = f1
            i=2
            while i<=n:
                if i%3==1: temp= h(f1,temp)
                elif i%3==2: temp= h(f2,temp)
                else: temp= h(f3,temp)
                i+=1
            return temp
    return g

遍历1-n，每次取模3来判断该套哪个函数，注意0和1时特判，2开始从f1往外套

即执行顺序为\(i\%3=2 -> i\%3=0 -> i\%3=1 -> ...\)

【CS61A】CS61A——Environments

发表于 2025-01-30 更新于 2025-07-31 分类于 CS61A
本文字数： 1.7k 阅读时长 ≈ 3 分钟

Environments

Environments in Higher-orde function

Local Names

e.g.

def f(x,y):
    return g(x)
def g(a):
    return a+y

result = f(1,2)

该代码会报错NameError: global name 'y' is not defined

原因很明显：当执行到行4时，系统在g的作用域中找不到y，接着去全局作用域中也找不到y，因而报错

而对于嵌套函数，函数中定义的函数是可以直接使用嵌套外函数的参数的，因为在同一个作用于下

Function Composition

e.g.

def make_adder(n):
    def adder(k):
        return k+n
    return adder
def square(x):
    return x*x
def triple(x):
    return 3*x
def compose1(f,g):
    def h(x):
        return f(g(x))
    return h

compose1函数将两个函数结合起来计算

compose1(triple,square)(5)的结果为225

compose1(square,triple)(5)的结果为75

compose1(square, makek_adder(2))(3)的结果为25

该函数实际上开辟了两个environments用来分别计算两个函数的return值

如图中蓝色和绿色的两个environments，每个中都包含了三个作用域，分别用来计算square与make_adder(2)的值，其中make_adder还会先进入adder函数的作用域

Self-Reference

e.g.1

def print_all(x):
    print(x)
    return print_all

print_all(1)(3)(5)

该函数执行后会输出1

即print_all函数可以在函数体内以return值形式返回自身，因此该函数被调用的次数与第五行后面的括号数一致（即被调用几次）

e.g.2

def print_sums(x):
    print(x)
    def next_sum(y):
        return print_sums(x+y)
    return next_sum

print_sums(1)(3)(5)

函数会把括号后面的数依次相加，输出每次相加的和

首先传入x=1，打印1，定义next_sum函数，print_sums函数返回该函数，并传入y=3，next_sum返回print_sums函数，传入值为x+y=4

再次打印4，定义next_sum函数，print_sums函数返回该函数，并传入y=5，next_sum返回print_sums函数，传入值为x+y=9

再次打印9，没有参数传入，结束

因此要注意调用表达式中传入的参数去了哪里：

1传入了print_sums，而3和5传入了print_sums的返回值next_sum函数用于求和

Currying

注意以下两种函数

def make_adder(n):
    return lambda k:n+k

def add(x,y):
    return x+y

make_adder函数一次调用一个参数，返回一个函数再调用参数

add函数调用多个参数，返回最终结果

我们可以用以下函数将add函数转换为make_adder函数

def curry(f):
    def g(x):
        def h(y):
            return f(x,y)
        return h
    return g

这样，当我们把add函数传入curry函数，我们就可以通过一次调用一个参数的方法实现相同效果

add_three = curry(add)

add_three(3)(2) >>> 5

定义：柯里化（Currying）是一种处理多元函数的方法。它产生一系列连锁函数，其中每个函数固定部分参数，并返回一个新函数，用于传回其它剩余参数的功能。

即它可以把一个多元函数转换为一系列函数，每个函数传入一个参数，即将f(a,b,c)转换为f(a)(b)(c)

【数据结构】ST表

发表于 2025-01-28 更新于 2026-04-09 分类于算法与数据结构，数据结构
本文字数： 1.7k 阅读时长 ≈ 3 分钟

介绍了st表的原理，适用于离线寻找区间最值/gcd等

阅读全文 »

【数据结构】树状数组

发表于 2025-01-25 更新于 2025-12-17 分类于算法与数据结构，数据结构
本文字数： 3.7k 阅读时长 ≈ 7 分钟

介绍了树状数组的原理与用法，主要用于高效区间修改与区间查询

阅读全文 »

【算法】滑动窗口

发表于 2025-01-23 更新于 2025-12-17 分类于算法与数据结构， (或许是)基础算法
本文字数： 3.3k 阅读时长 ≈ 6 分钟

介绍了滑动窗口，用于处理子数组相关问题

阅读全文 »

【数据结构】优先队列

发表于 2025-01-22 更新于 2025-12-17 分类于算法与数据结构，数据结构
本文字数： 1k 阅读时长 ≈ 2 分钟

介绍了优先队列的用法，可以方便的按照优先级存取元素

阅读全文 »