Homework 4

Sequence

Q1: Deep Map

写一个函数deep_map，使得传入的列表s（s可能是嵌套列表）中的每一个元素替换为该元素传入函数f后的返回值

每一个元素包括嵌套列表中的每一个元素

提示：type(a)==list会返回True如果a是列表

def deep_map(f, s):
    """Replace all non-list elements x with f(x) in the nested list s.

    >>> six = [1, 2, [3, [4], 5], 6]
    >>> deep_map(lambda x: x * x, six)
    >>> six
    [1, 4, [9, [16], 25], 36]
    >>> # Check that you're not making new lists
    >>> s = [3, [1, [4, [1]]]]
    >>> s1 = s[1]
    >>> s2 = s1[1]
    >>> s3 = s2[1]
    >>> deep_map(lambda x: x + 1, s)
    >>> s
    [4, [2, [5, [2]]]]
    >>> s1 is s[1]
    True
    >>> s2 is s1[1]
    True
    >>> s3 is s2[1]
    True
    """

    for i in range(len(s)):
        if type(s[i])==list:
            deep_map(f,s[i])
        else:
            s[i]=f(s[i])

遍历列表下标i，如果发现内部有嵌套列表，就递归进入遍历嵌套列表，若当前位置为一般元素，则调用函数并将结果替换

Data Abstraction

要用到的ADT

Mobile：一种悬挂雕像

一个mobile一定有一个左arm和一个右arm
一个arm有一个正数大小的长度，且尾端一定挂着一个mobile或一个planet
一个planet有一个正数大小的质量，且没有东西挂在上面

Q2: Mass

补充完成构造器planet与选择器mass

使得每一格planet用一个二元列表表示：['planet', mass]

其中total_mass函数可以用来计算一个planet或一个mobile的质量

def planet(mass):
    """Construct a planet of some mass."""
    assert mass > 0
    return ['planet', mass]

def mass(p):
    """Select the mass of a planet."""
    assert is_planet(p), 'must call mass on a planet'
    return p[1]

按照提示构造即可

Q3: Balanced

实现balanced函数，判断m是否是一个”balanced mobile”

“balanced mobile”的定义如下：

左arm的扭矩等于右arm的扭矩，其中扭矩为左arm的长度与挂在左arm上的质量之积
挂在arm尾端的mobile自身为balanced mobile，planet自身也是balanced的

提示：使用total_mass函数，选择器函数，不要逾越ADT的屏障

def balanced(m):
    """Return whether m is balanced.

    >>> t, u, v = examples()
    >>> balanced(t)
    True
    >>> balanced(v)
    True
    >>> p = mobile(arm(3, t), arm(2, u))
    >>> balanced(p)
    False
    >>> balanced(mobile(arm(1, v), arm(1, p)))
    False
    >>> balanced(mobile(arm(1, p), arm(1, v)))
    False
    >>> from construct_check import check
    >>> # checking for abstraction barrier violations by banning indexing
    >>> check(HW_SOURCE_FILE, 'balanced', ['Index'])
    True
    """
    if is_planet(m):
        return True
    else:
        torque_left = length(left(m))*total_mass(end(left(m)))
        torque_right = length(right(m))*total_mass(end(right(m)))
        return torque_left == torque_right and balanced(end(left(m))) and balanced(end(right(m)))

这个结构类似树，我们可以递归的求解这个问题

Base case：若传入的是一个planet，则返回True，因为planet在这个结构中类似叶子节点，是整个mobile的终点
递归：每次需要比较mobile的左右扭矩是否相等，同时递归比较左右arm下的左右扭矩是否相等，直到递归到planet直接返回True

Trees

Q4: Maximum Path Sum

写一个函数，返回树上从根节点到叶子节点的所有路径中节点权值总和最大值

def max_path_sum(t):
    """Return the maximum root-to-leaf path sum of a tree.
    >>> t = tree(1, [tree(5, [tree(1), tree(3)]), tree(10)])
    >>> max_path_sum(t) # 1, 10
    11
    >>> t2 = tree(5, [tree(4, [tree(1), tree(3)]), tree(2, [tree(10), tree(3)])])
    >>> max_path_sum(t2) # 5, 2, 10
    17
    """
    max_n = -1
    if is_leaf(t):
        return label(t)

    for b in branches(t):
        max_n=max(max_path_sum(b),max_n)

    return max_n+label(t)

使用递归遍历

先直接深入到叶子节点，发现叶子节点则返回节点权值，再往前返回，每上一个节点返回已经求和的值+当前节点权值，且每次遍历取当前不同路径的最大值

红魔咖啡馆

【CS61A】CS61A——Homework 4