网址 https://inst.eecs.berkeley.edu/~cs61a/fa21/lab/lab05/#required-questions

• problem1:
• problem2:
• problem3:
• problem4:
• problem6:
• problem7：
• 全部代码

problem1:

    def factors_list(n):
        """Return a list containing all the numbers that divide `n` evenly, except
        for the number itself. Make sure the list is in ascending order.

        >>> factors_list(6)
        [1, 2, 3]
        >>> factors_list(8)
        [1, 2, 4]
        >>> factors_list(28)
        [1, 2, 4, 7, 14]
        """
        all_factors = []
        for i in range(1, int(n / 2) + 1):
            if n % i == 0:
                all_factors += [i]
        return all_factors

problem2:

用递归，这种一层一层的很适合用递归

    def flatten(s):
        """Returns a flattened version of list s.

        >>> flatten([1, 2, 3])     # normal list
        [1, 2, 3]
        >>> x = [1, [2, 3], 4]     # deep list
        >>> flatten(x)
        [1, 2, 3, 4]
        >>> x # Ensure x is not mutated
        [1, [2, 3], 4]
        >>> x = [[1, [1, 1]], 1, [1, 1]] # deep list
        >>> flatten(x)
        [1, 1, 1, 1, 1, 1]
        >>> x
        [[1, [1, 1]], 1, [1, 1]]
        """
        "*** YOUR CODE HERE ***"
        if not s :
            return []
        elif type(s[0] ) == list:
            return flatten(s[0] + flatten(s[1:]))
        else:
            return [s[0]] + flatten(s[1:])

problem3:

注意三和四问题不能破坏abstraction barrier

    def distance(city_a, city_b):
        """
        >>> city_a = make_city('city_a', 0, 1)
        >>> city_b = make_city('city_b', 0, 2)
        >>> distance(city_a, city_b)
        1.0
        >>> city_c = make_city('city_c', 6.5, 12)
        >>> city_d = make_city('city_d', 2.5, 15)
        >>> distance(city_c, city_d)
        5.0
        """
        "*** YOUR CODE HERE ***"
        return round(sqrt((get_lat(city_a) - get_lat(city_b))**2 + (get_lon(city_a) - get_lon(city_b))**2), 2)

problem4:

    def closer_city(lat, lon, city_a, city_b):
        """
        Returns the name of either city_a or city_b, whichever is closest to
        coordinate (lat, lon). If the two cities are the same distance away
        from the coordinate, consider city_b to be the closer city.

        >>> berkeley = make_city('Berkeley', 37.87, 112.26)
        >>> stanford = make_city('Stanford', 34.05, 118.25)
        >>> closer_city(38.33, 121.44, berkeley, stanford)
        'Stanford'
        >>> bucharest = make_city('Bucharest', 44.43, 26.10)
        >>> vienna = make_city('Vienna', 48.20, 16.37)
        >>> closer_city(41.29, 174.78, bucharest, vienna)
        'Bucharest'
        """
        "*** YOUR CODE HERE ***"
        now = make_city('now', lat, lon)
        if distance(now, city_a) <= distance(now, city_b):
            return get_name(city_a)
        else:
            return get_name(city_b)

problem6:

7和6也要注意不要破坏abstraction barrier
def berry_finder(t):
"""Returns True if t contains a node with the value 'berry' and
False otherwise.

        >>> scrat = tree('berry')
        >>> berry_finder(scrat)
        True
        >>> sproul = tree('roots', [tree('branch1', [tree('leaf'), tree('berry')]), tree('branch2')])
        >>> berry_finder(sproul)
        True
        >>> numbers = tree(1, [tree(2), tree(3, [tree(4), tree(5)]), tree(6, [tree(7)])])
        >>> berry_finder(numbers)
        False
        >>> t = tree(1, [tree('berry',[tree('not berry')])])
        >>> berry_finder(t)
        True
        """
        "*** YOUR CODE HERE ***"
        if label(t) == 'berry':
            return True
        for b in branches(t):
            if berry_finder(b):
                return True
        return False

problem7：

    def sprout_leaves(t, leaves):
        """Sprout new leaves containing the data in leaves at each leaf in
        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):
        #     #直接加一个叶子
        #     pass
        # for b in branches(t):
        #     if is_leaf(b):
        #         #加一个叶子
        #         pass
        #     else:
        #         sprout_leaves(b,leaves)
        # return t
        if is_leaf(t):
            return tree(label(t), [tree(leaf) for leaf in leaves])
        return tree(label(t), [sprout_leaves(s, leaves) for s in branches(t)])

全部代码

    def factors_list(n):
        """Return a list containing all the numbers that divide `n` evenly, except
        for the number itself. Make sure the list is in ascending order.

        >>> factors_list(6)
        [1, 2, 3]
        >>> factors_list(8)
        [1, 2, 4]
        >>> factors_list(28)
        [1, 2, 4, 7, 14]
        """
        all_factors = []
        for i in range(1, int(n / 2) + 1):
            if n % i == 0:
                all_factors += [i]
        return all_factors


    def flatten(s):
        """Returns a flattened version of list s.

        >>> flatten([1, 2, 3])     # normal list
        [1, 2, 3]
        >>> x = [1, [2, 3], 4]     # deep list
        >>> flatten(x)
        [1, 2, 3, 4]
        >>> x # Ensure x is not mutated
        [1, [2, 3], 4]
        >>> x = [[1, [1, 1]], 1, [1, 1]] # deep list
        >>> flatten(x)
        [1, 1, 1, 1, 1, 1]
        >>> x
        [[1, [1, 1]], 1, [1, 1]]
        """
        "*** YOUR CODE HERE ***"
        if not s :
            return []
        elif type(s[0] ) == list:
            return flatten(s[0] + flatten(s[1:]))
        else:
            return [s[0]] + flatten(s[1:])


    from math import sqrt


    def distance(city_a, city_b):
        """
        >>> city_a = make_city('city_a', 0, 1)
        >>> city_b = make_city('city_b', 0, 2)
        >>> distance(city_a, city_b)
        1.0
        >>> city_c = make_city('city_c', 6.5, 12)
        >>> city_d = make_city('city_d', 2.5, 15)
        >>> distance(city_c, city_d)
        5.0
        """
        "*** YOUR CODE HERE ***"
        return round(sqrt((get_lat(city_a) - get_lat(city_b))**2 + (get_lon(city_a) - get_lon(city_b))**2), 2)


    def closer_city(lat, lon, city_a, city_b):
        """
        Returns the name of either city_a or city_b, whichever is closest to
        coordinate (lat, lon). If the two cities are the same distance away
        from the coordinate, consider city_b to be the closer city.

        >>> berkeley = make_city('Berkeley', 37.87, 112.26)
        >>> stanford = make_city('Stanford', 34.05, 118.25)
        >>> closer_city(38.33, 121.44, berkeley, stanford)
        'Stanford'
        >>> bucharest = make_city('Bucharest', 44.43, 26.10)
        >>> vienna = make_city('Vienna', 48.20, 16.37)
        >>> closer_city(41.29, 174.78, bucharest, vienna)
        'Bucharest'
        """
        "*** YOUR CODE HERE ***"
        now = make_city('now', lat, lon)
        if distance(now, city_a) <= distance(now, city_b):
            return get_name(city_a)
        else:
            return get_name(city_b)

    def check_city_abstraction():
        """
        There's nothing for you to do for this function, it's just here for the extra doctest
        >>> change_abstraction(True)
        >>> city_a = make_city('city_a', 0, 1)
        >>> city_b = make_city('city_b', 0, 2)
        >>> distance(city_a, city_b)
        1.0
        >>> city_c = make_city('city_c', 6.5, 12)
        >>> city_d = make_city('city_d', 2.5, 15)
        >>> distance(city_c, city_d)
        5.0
        >>> berkeley = make_city('Berkeley', 37.87, 112.26)
        >>> stanford = make_city('Stanford', 34.05, 118.25)
        >>> closer_city(38.33, 121.44, berkeley, stanford)
        'Stanford'
        >>> bucharest = make_city('Bucharest', 44.43, 26.10)
        >>> vienna = make_city('Vienna', 48.20, 16.37)
        >>> closer_city(41.29, 174.78, bucharest, vienna)
        'Bucharest'
        >>> change_abstraction(False)
        """

    # Treat all the following code as being behind an abstraction layer,
    # you shouldn't need to look at it.


    def make_city(name, lat, lon):
        """
        >>> city = make_city('Berkeley', 0, 1)
        >>> get_name(city)
        'Berkeley'
        >>> get_lat(city)
        0
        >>> get_lon(city)
        1
        """
        if change_abstraction.changed:
            return {"name": name, "lat": lat, "lon": lon}
        else:
            return [name, lat, lon]


    def get_name(city):
        """
        >>> city = make_city('Berkeley', 0, 1)
        >>> get_name(city)
        'Berkeley'
        """
        if change_abstraction.changed:
            return city["name"]
        else:
            return city[0]


    def get_lat(city):
        """
        >>> city = make_city('Berkeley', 0, 1)
        >>> get_lat(city)
        0
        """
        if change_abstraction.changed:
            return city["lat"]
        else:
            return city[1]


    def get_lon(city):
        """
        >>> city = make_city('Berkeley', 0, 1)
        >>> get_lon(city)
        1
        """
        if change_abstraction.changed:
            return city["lon"]
        else:
            return city[2]


    def berry_finder(t):
        """Returns True if t contains a node with the value 'berry' and 
        False otherwise.

        >>> scrat = tree('berry')
        >>> berry_finder(scrat)
        True
        >>> sproul = tree('roots', [tree('branch1', [tree('leaf'), tree('berry')]), tree('branch2')])
        >>> berry_finder(sproul)
        True
        >>> numbers = tree(1, [tree(2), tree(3, [tree(4), tree(5)]), tree(6, [tree(7)])])
        >>> berry_finder(numbers)
        False
        >>> t = tree(1, [tree('berry',[tree('not berry')])])
        >>> berry_finder(t)
        True
        """
        "*** YOUR CODE HERE ***"
        if label(t) == 'berry':
            return True
        for b in branches(t):
            if berry_finder(b):
                return True
        return False


    def sprout_leaves(t, leaves):
        """Sprout new leaves containing the data in leaves at each leaf in
        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):
        #     #直接加一个叶子
        #     pass
        # for b in branches(t):
        #     if is_leaf(b):
        #         #加一个叶子
        #         pass
        #     else:
        #         sprout_leaves(b,leaves)
        # return t
        if is_leaf(t):
            return tree(label(t), [tree(leaf) for leaf in leaves])
        return tree(label(t), [sprout_leaves(s, leaves) for s in branches(t)])

    # Abstraction tests for sprout_leaves and berry_finder


    def check_abstraction():
        """
        There's nothing for you to do for this function, it's just here for the extra doctest
        >>> change_abstraction(True)
        >>> scrat = tree('berry')
        >>> berry_finder(scrat)
        True
        >>> sproul = tree('roots', [tree('branch1', [tree('leaf'), tree('berry')]), tree('branch2')])
        >>> berry_finder(sproul)
        True
        >>> numbers = tree(1, [tree(2), tree(3, [tree(4), tree(5)]), tree(6, [tree(7)])])
        >>> berry_finder(numbers)
        False
        >>> t = tree(1, [tree('berry',[tree('not berry')])])
        >>> berry_finder(t)
        True
        >>> 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
        >>> change_abstraction(False)
        """


    def change_abstraction(change):
        """
        For testing purposes.
        >>> change_abstraction(True)
        >>> change_abstraction.changed
        True
        """
        change_abstraction.changed = change


    change_abstraction.changed = False


    # Tree ADT

    def tree(label, branches=[]):
        """Construct a tree with the given label value and a list of branches."""
        if change_abstraction.changed:
            for branch in branches:
                assert is_tree(branch), 'branches must be trees'
            return {'label': label, 'branches': list(branches)}
        else:
            for branch in branches:
                assert is_tree(branch), 'branches must be trees'
            return [label] + list(branches)


    def label(tree):
        """Return the label value of a tree."""
        if change_abstraction.changed:
            return tree['label']
        else:
            return tree[0]


    def branches(tree):
        """Return the list of branches of the given tree."""
        if change_abstraction.changed:
            return tree['branches']
        else:
            return tree[1:]


    def is_tree(tree):
        """Returns True if the given tree is a tree, and False otherwise."""
        if change_abstraction.changed:
            if type(tree) != dict or len(tree) != 2:
                return False
            for branch in branches(tree):
                if not is_tree(branch):
                    return False
            return True
        else:
            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):
        """Returns True if the given tree's list of branches is empty, and False
        otherwise.
        """
        return not branches(tree)


    def print_tree(t, indent=0):
        """Print a representation of this tree in which each node is
        indented by two spaces times its depth from the root.

        >>> print_tree(tree(1))
        1
        >>> print_tree(tree(1, [tree(2)]))
        1
          2
        >>> numbers = tree(1, [tree(2), tree(3, [tree(4), tree(5)]), tree(6, [tree(7)])])
        >>> print_tree(numbers)
        1
          2
          3
            4
            5
          6
            7
        """
        print('  ' * indent + str(label(t)))
        for b in branches(t):
            print_tree(b, indent + 1)


    def copy_tree(t):
        """Returns a copy of t. Only for testing purposes.

        >>> t = tree(5)
        >>> copy = copy_tree(t)
        >>> t = tree(6)
        >>> print_tree(copy)
        5
        """
        return tree(label(t), [copy_tree(b) for b in branches(t)])