一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 336|回复: 4
收起左侧

[CS61A]disc04

[复制链接] |试试Instant~ |关注本帖
sky420 发表于 2015-5-23 00:11:50 | 显示全部楼层 |阅读模式

[其他]CS61A #2 - 04@UCBerkely

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
disc04: http://gaotx.com/cs61a//disc/disc04.pdf
My solution: http://gaotx.com/blogs/2015/05/14/cs61a-disc04/
wuxiaomin98 发表于 2015-6-2 09:44:07 | 显示全部楼层
# This is for cs61a discussion 4

def foo(lst):
    """
    1.1.2
    >>> x = [1, 2, 3, 4, 5, 6]
    >>> foo(x)
    [0, 6, 20]
    """
    return [i * lst[i] for i in range(len(lst)) if i % 2 == 0 ]

def square_tree(t):
    """
    2.2.1
    Return a tree with the square of every element in t
    """

    sq_branches = [square_tree(subtree) for subtree in branches(t)]
    return tree(root(t) ** 2, sq_branches)

def height(t):
    """
    2.2.2
    Return the height of a tree
    """

    if is_leaf(t):
        return 0
    return 1 + max([height(subtree) for subtree in branches(t)])

def tree_size(t):
    """
    2.2.3
    Return the size of a tree.
    """
    if is_leaf(t):
        return 1
    return 1 + sum([tree_size(subtree) for subtree in branches(t)])

def tree_max(t):
    """
    2.2.4
    Return the max of a tree
    """

    if is_leaf(t):
        return root(t)
    return max([root(t)] + [tree_max(subtree) for subtree in branches(t)]


   
回复 支持 反对

使用道具 举报

reasonapp 发表于 2015-6-20 17:19:57 | 显示全部楼层
关于list的lab,挺简单的,没碰到啥障碍。就是看了Q5的答案之后发现自己智商欠费。代码如下:
# Q4
def get_seven_a(x):
    """
    >>> x = [1, 3, [5, 7], 9]
    >>> get_seven_a(x)
    7
    """
    "*** YOUR CODE HERE ***"
    return x[1][0]

def get_seven_b(x):
    """
    >>> x = [[7]]
    >>> get_seven_b(x)
    7
    """
    "*** YOUR CODE HERE ***"
    return [0][0]

def get_seven_c(x):
    """
    >>> x = [1, [2, [3, [4, [5, [6, [7]]]]]]]
    >>> get_seven_c(x)
    7
    """
    "*** YOUR CODE HERE ***"
    return [1][1][1][1][1][1][0]

# Q5
def reverse_recursive(lst):
    """Returns the reverse of the given list.

    >>> reverse_recursive([1, 2, 3, 4])
    [4, 3, 2, 1]
    """
    "*** YOUR CODE HERE ***"
    if len(lst) == 1:
        return [lst[0]]
    else:
        l = len(lst)
        return [lst[l-1]] + reverse_recursive(lst[:l-1])
        
# Q6
def merge(lst1, lst2):
    """Merges two sorted lists recursively.

    >>> merge([1, 3, 5], [2, 4, 6])
    [1, 2, 3, 4, 5, 6]
    >>> merge([], [2, 4, 6])
    [2, 4, 6]
    >>> merge([1, 2, 3], [])
    [1, 2, 3]
    >>> merge([5, 7], [2, 4, 6])
    [2, 4, 5, 6, 7]
    """
    "*** YOUR CODE HERE ***"
    lst = []
    for item in lst1:
        lst = lst + [item]
    for item in lst2:
        lst = lst + [item]
    lst.sort()
    print lst
   
# Q8
from math import sqrt

def is_square(n):
    return float(sqrt(n)) == int(sqrt(n))

def squares(seq):
    """Returns a new list containing elements of the original list that are
    perfect squares.

    >>> seq = [49, 8, 2, 1, 102]
    >>> squares(seq)
    [49, 1]
    >>> seq = [500, 30]
    >>> squares(seq)
    []
    """
    "*** YOUR CODE HERE ***"
    return [item for item in seq if is_square(item)]

回复 支持 反对

使用道具 举报

reasonapp 发表于 2015-6-22 00:51:50 | 显示全部楼层
这四道题我想了八个小时。。求大米,求安慰,不过最终搞懂了真心很开心,代码如下:
# -*- coding: utf-8 -*-
#disc 04
#Q1.1_2
def foo(lst):
    """
    >>> x = [1, 2, 3, 4, 5, 6]
    >>> foo(x)
    [0, 6, 20]
    """
    return [i * lst[i] for i in range(len(lst)) if i % 2 == 0]
   
#Q2.2_1
# Constructor
def tree(value, branches=[]):
    for branch in branches:
        assert is_tree(branch)
    return [value] + list(branches)

# Selectors
def root(tree):
    return tree[0]
def branches(tree):
    return tree[1:]
def is_leaf(tree):
    return not branches(tree)
def is_tree(tree):
    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 square_tree(t):
    """Return a tree with the square of every element in t"""
    if is_tree(t):
        return tree(root(t) ** 2, [square_tree(subtree) for subtree in branches(t)])
    return t[0] ** 2            
   
#Q2.2_2
def height(t):
    """Return the height of a tree"""
    if is_leaf(t):
        return 0
    return max(height(subtree) for subtree in branches(t)) + 1

#Q2.2_3
def tree_size(t):
    """Return the size of a tree."""
    if is_leaf(t):
        return 1
    return 1 + sum(tree_size(subtree) for subtree in branches(t))
   
#Q2.2_4
def tree_max(t):
    """Return the max of a tree."""
    if is_leaf(t):
        return t[0]
    sub_max = max(tree_max(subtree) for subtree in branches(t))
    return max(sub_max, root(t))
回复 支持 反对

使用道具 举报

Liaeve 发表于 2016-2-25 00:03:14 | 显示全部楼层
tree结构学的时候就觉得理解的不清楚,做起题来更捉急。extra做到最后一题,看着答案都觉得脑袋要炸了。必须再多刷题,多巩固

# 1.1.2
def foo(lst):
        """
        >>> x = [1, 2, 3, 4, 5, 6]
        >>> foo(x)
        [0, 6, 20]
        """

        return [lst[i] * i for i in range(len(lst)) if i % 2 == 0]

# 2
# Constructor
def tree(value, branches=[]):
        for branch in branches:
                assert is_tree(branch)
        return [value] + list(branches)

# Selectors
def root(tree):
        return tree[0]
def branches(tree):
        return tree[1:]

def is_leaf(tree):
        return not branches(tree)
def is_tree(tree):
        if type(tree) != list or len(tree) < 1:
                return False
        for branch in branches(tree):
                if not is_tree(branch):
                        return False
        return True

# 2.2.1
def square_tree(t):
        """Return a tree with the square of every element in t"""

        return tree(root(t)**2, [square_tree(branch) for branch in branches(t)])

# 2.2.2
def height(t):
        """Return the height of a tree"""

        if is_leaf(t):
                return 0
        return 1 + max([height(branch) for branch in branches(t)])

# 2.2.3
def tree_size(t):
        """Return the size of a tree."""

        if is_leaf(t):
                return 1
        return 1 + sum([tree_size(branch) for branch in branches(t)])

# 2.2.4
def tree_max(t):
        """Return the max of a tree."""
        if is_leaf(t):
                return root(t)
        return max([root(t)]+[tree_max(branch) for branch in branches(t)])

#2.3.1
def reduce(fn, s, init):
        reduced = init
        for x in s:
                reduced = fn(reduced, x)
        return reduced

def apply_to_all(fn, s):
        return [fn(x) for x in s]

from operator import add, mul
def eval_tree(tree):
        """Evaluates an expression tree with functions as root
        >>> eval_tree(tree(1))
        1
        >>> expr = tree(mul, [tree(2), tree(3)])
        >>> eval_tree(expr)
        6
        >>> eval_tree(tree(add, [expr, tree(4)]))
        10
        """

        if is_leaf(tree):
                return root(tree)
        if root(tree) == mul:
                init = 1
        else:
                init = 0
        return reduce(root(tree), apply_to_all(eval_tree, branches(tree)), init)

#2.3.2
def hailstone_tree(n, h):
        """Generates a tree of hailstone numbers that will reach N, with height H.
        >>> hailstone_tree(1, 0)
        [1]
        >>> hailstone_tree(1, 4)
        [1, [2, [4, [8, [16]]]]]
        >>> hailstone_tree(8, 3)
        [8, [16, [32, [64]], [5, [10]]]]
        """

        if h == 0:
                return tree(n)
        h_b = [hailstone_tree(2 * n, h - 1)]
        if (n - 1) % 3 == 0 and (n - 1) // 3 > 1:
                h_b += [hailstone_tree((n - 1) // 3, h - 1)]
        return tree(n, h_b)

#2.3.3
def find_path(tree, x):
        """ Return a path in a tree to a leaf with value X,
        None if such a leaf is not present.
        >>> t = tree(2, [tree(7, [tree(3), tree(6, [tree(5), tree(11)])]), tree(15)])
        >>> find_path(t, 5)
        [2, 7, 6, 5]
        >>> find_path(t, 6)
        [2, 7, 6]
        >>> find_path(t, 10)
        """

        if root(tree) == x:
        return [x]
    for path in [find_path(branch, x) for branch in branches(tree)]:
        if path:
            return [root(tree)] + path
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-5 17:19

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表