Review: Lab05 & Hw05

Author

jjppp

Lab05

停止 yield 的方法:

  1. raise StopIteration
  2. return
def takeWhile(t, p):
    for x in t:
        if not p(x):
            return
        yield x

思路:

  1. 现在是第几轮：round
  2. 现在是第round轮的第几个：i
  3. round是偶数 => 跳过
  4. round是奇数 => yield
def backAndForth(t):
    i, round = 0, 1
    for x in t:
        i += 1
        if round % 2 == 1:
            yield x
        if i == round:
            i = 0
            round += 1

Cool stuff:

  1. 我们可以map一个list：
def map_list(f, lst):
    list(map(f, lst))
  1. 也可以map一个树（期中）：
def map_tree(f, t):
    return tree(f(label(t)), [map_tree(f, b) for b in branches(t)])
  1. 自然也可以map一个iterator：
def scale(it, multiplier):
    yield from map(lambda x: multiplier * x, it)

思路（期中merge_sorted）:

  1. a和b的iterator能记住现在到了序列中的第几个
  2. 用first_a和first_b记录a和b目前的第一个元素
  3. first_a > first_b => 对 iter_b 使用 next
  4. first_a < first_b => 对 iter_a 使用 next
  5. 相等，说明出现重复，随便丢掉一个
def merge(a, b):
    first_a, first_b = next(a), next(b)
    while True:
        if first_a == first_b:
            yield first_a
            first_a, first_b = next(a), next(b)
        elif first_a < first_b:
            yield first_a
            first_a = next(a)
        else:
            yield first_b
            first_b = next(b)
  1. 写一个 while 版本的算法
  2. 在必要的时候 yield
def hailstone(n):
    yield n
    while n != 1:
        if n % 2 == 0:
            n = n // 2
        else:
            n = n * 3 + 1
        yield n
  1. hailstone(n) 表示从 n 开始的 hailstone 数列
  2. hailstone(n) 的第一项就是 n
  3. 若 n 是 1，结束
  4. n 是奇数，从第二项起是以 n*3+1 为首的 hailstone 数列
  5. n 是偶数，从第二项起是以 n//2 为首的 hailstone 数列
def hailstone(n):
    yield n
    if n == 1:
        return
    elif n % 2 == 0:
        yield from hailstone(n // 2)
    else:
        yield from hailstone(n * 3 + 1)

Hw05

def make_withdraw(balance, password):
    history_pw = []
    def withdraw(amount, pw):
        nonlocal balance
        if len(history_pw) >= 3:
            return 'Your account is locked. Attempts: {}'.format(history_pw)
        if pw != password:
            history_pw.append(pw)
            return 'Incorrect password'
        if amount > balance:
            return 'Insufficient funds'
        balance -= amount
        return balance
    return withdraw

关键：

  1. 旧账户密码不受影响
  2. 新账户取钱，旧账户也扣
  3. 新账户输错密码，旧账户也记录
  4. 新账户的密码得是个正确的密码
def make_joint(withdraw, old_pass, new_pass):
    error = withdraw(0, old_pass)
    if type(error) == str:
        return error

    def joint_withdraw(amount, pw):
        if pw == new_pass:
            return withdraw(amount, old_pass)
        return withdraw(amount, pw)
    return joint_withdraw

关键：

  1. seq 可以是 generator，因此seq不一定能+（群聊）
  2. 但permutations yield出来的的一定是list（docstring）
  3. 解法一：无脑全转成list
  4. 解法二：先算permutations，再做拼接

思路：

  1. 空序列的全排列是空list
  2. 拿走第一个元素，求剩下的全排列，再把第一个元素拼回去（任意位置）
  3. 在恰当的时候yield
def permutations(seq):
    if not seq:
        yield []
    else:
        head, tail = seq[0], seq[1:]
        for perm in permutations(tail):
            for i in range(len(seq)):
                yield perm[:i] + [head] + perm[i:]

关键：

  1. 记下第一棵树上，label为k的节点的位置

  2. 在第二棵树上找到对应的位置，yield节点的label

    位置可以是：

    1. preorder的下标（教222/综合楼503）

    2. 记录下从root到当前节点每次走了第几个branch

      （从广州路门进，先左转再右转…）

    3. 用lambda函数编码（见答案）

坑：

  1. 刻舟求剑.jpg

    lst = []
for i in range(10):
    lst.append(lambda : print(i))
for f in lst:
    f()

  2. 群里给了一段测试代码

  3. 尝试理解答案里(lookup, i)做了什么

def lookups(k, key):
    if label(k) == key:
        yield label
    for i in range(len(branches(k))):
        for lookup in lookups(branches(k)[i], key):
            yield (lambda f, i: lambda v: f(branches(v)[i]))(lookup, i)