【CS61A】CS61A——Homework 5

Homework 5

Q1: Infinite Hailstone

写一个生成器函数来生成从n开始的冰雹猜想序列，当到达序列尾后，生成器会一直声称1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

def hailstone(n):
    """Q1: Yields the elements of the hailstone sequence starting at n.
       At the end of the sequence, yield 1 infinitely.

    >>> hail_gen = hailstone(10)
    >>> [next(hail_gen) for _ in range(10)]
    [10, 5, 16, 8, 4, 2, 1, 1, 1, 1]
    >>> next(hail_gen)
    1
    """
    yield n
    if n==1:
        n=1
    elif n%2==0:
        n=int(n/2)
    else:
        n=3*n+1
    yield from hailstone(n)

使用递归，结合yield from生成迭代器

Q2: Merge

写一个merge函数，传入两个无限生成器a,b按照给定起始位置与步长生成非重复上升序列，返回一个生成器包含两个生成器中的所有元素，且去重

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

def merge(a, b):
    """Q2:
    >>> def sequence(start, step):
    ...     while True:
    ...         yield start
    ...         start += step
    >>> a = sequence(2, 3) # 2, 5, 8, 11, 14, ...
    >>> b = sequence(3, 2) # 3, 5, 7, 9, 11, 13, 15, ...
    >>> result = merge(a, b) # 2, 3, 5, 7, 8, 9, 11, 13, 14, 15
    >>> [next(result) for _ in range(10)]
    [2, 3, 5, 7, 8, 9, 11, 13, 14, 15]
    """
    gene_a = next(a)
    gene_b = next(b)
    while True:
        if gene_a == gene_b:
            yield gene_a
            gene_a = next(a)
            gene_b = next(b)
        elif gene_a> gene_b:
            yield gene_b
            gene_b = next(b)
        else:
            yield gene_a
            gene_a = next(a)

Q3: Yield Paths

定义一个生成器函数，传入一棵树与一个值v，返回生成器从树的根到含有v的节点的每一条路径

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

def yield_paths(t, value):
    """Q4: Yields all possible paths from the root of t to a node with the label
    value as a list.

    >>> t1 = tree(1, [tree(2, [tree(3), tree(4, [tree(6)]), tree(5)]), tree(5)])
    >>> print_tree(t1)
    1
      2
        3
        4
          6
        5
      5
    >>> next(yield_paths(t1, 6))
    [1, 2, 4, 6]
    >>> path_to_5 = yield_paths(t1, 5)
    >>> sorted(list(path_to_5))
    [[1, 2, 5], [1, 5]]

    >>> t2 = tree(0, [tree(2, [t1])])
    >>> print_tree(t2)
    0
      2
        1
          2
            3
            4
              6
            5
          5
    >>> path_to_2 = yield_paths(t2, 2)
    >>> sorted(list(path_to_2))
    [[0, 2], [0, 2, 1, 2]]
    """
    if label(t) == value:
        yield [value]
    for b in branches(t):
        for p in yield_paths(b, value):
            yield [label(t)]+p

If our current label is equal to value, we’ve found a path from the root to a node containing value containing only our current label, so we should yield that. From there, we’ll see if there are any paths starting from one of our branches that ends at a node containing value. If we find these “partial paths” we can simply add our current label to the beginning of a path to obtain a path starting from the root.

In order to do this, we’ll create a generator for each of the branches which yields these “partial paths”. By calling yield_paths on each of the branches, we’ll create exactly this generator! Then, since a generator is also an iterable, we can iterate over the paths in this generator and yield the result of concatenating it with our current label.