一亩三分地论坛

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

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

[CS61A]Lab07

[复制链接] |试试Instant~ |关注本帖
sky420 发表于 2015-6-1 14:40:25 | 显示全部楼层 |阅读模式

[其他]CS61A #3 - 04@UCBerkely

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

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

x
Lab Link: http://gaotx.com/cs61a/lab/lab07/
My solution: http://gaotx.com/blogs/2015/05/28/cs61a-lab07/

评分

1

查看全部评分

karte_polo 发表于 2015-6-3 23:33:32 | 显示全部楼层
def insert(link, value, index):
    """Insert a value into a Link at the given index.

    >>> link = Link(1, Link(2, Link(3)))
    >>> insert(link, 9001, 0)
    >>> link
    Link(9001, Link(1, Link(2, Link(3))))
    >>> insert(link, 100, 2)
    >>> link
    Link(9001, Link(1, Link(100, Link(2, Link(3)))))
    >>> insert(link, 4, 5)
    Index out of bounds!
    """
    "*** YOUR CODE HERE ***"
    if index == 0:
        link.rest = Link(link.first,link.rest)
        link.first = value
    elif index > len(link):
        return 'Index out of bounds!'
    else:
        insert(link.rest,value,index-1)

class Tree:
    def __init__(self, entry, branches=()):
        self.entry = entry
        for branch in branches:
            assert isinstance(branch, Tree)
        self.branches = branches

    def __repr__(self):
        if self.branches:
            branches_str = ', ' + repr(self.branches)
        else:
            branches_str = ''
        return 'Tree({0}{1})'.format(self.entry, branches_str)

    def is_leaf(self):
        return not self.branches

def square_tree(t):
    """Mutates a Tree t by squaring all its elements.

    >>> t = Tree(1, [Tree(3, [Tree(5)]), Tree(7)])
    >>> square_tree(t)
    >>> t
    Tree(1, [Tree(9, [Tree(25)]), Tree(49)])
    """
    "*** YOUR CODE HERE ***"
    t.entry = t.entry**2
    for b in t.branches:
        square_tree(b)

def list_to_link(lst):
    """Takes a Python list and returns a Link with the same elements.

    >>> list_to_link([1, 2, 3])
    Link(1, Link(2, Link(3)))
    """
    "*** YOUR CODE HERE ***"
    if lst:
        return Link(lst[0],list_to_link(lst[1:]))
    else:
        return Link.empty

def link_to_list(link):
    """Takes a Link and returns a Python list with the same elements.

    >>> link = Link(1, Link(2, Link(3, Link(4))))
    >>> link_to_list(link)
    [1, 2, 3, 4]
    >>> link_to_list(Link.empty)
    []
    """
    "*** YOUR CODE HERE ***"
    if link is Link.empty:
        return []
    else:
        return [link.first]+link_to_list(link.rest)

def mutate_reverse(link):
    """Mutates the Link so that its elements are reversed.

    >>> link = Link(1)
    >>> mutate_reverse(link)
    >>> link
    Link(1)

    >>> link = Link(1, Link(2, Link(3)))
    >>> mutate_reverse(link)
    >>> link
    Link(3, Link(2, Link(1)))
    """
    "*** YOUR CODE HERE ***"
    def digin(l,n):
        if n==0:
            return l
        else:
            return digin(l.rest,n-1)
    n = len(link)
    i = 0
    while i<=n//2-1:
        t = link[i]
        digin(link,i).first = link[n-i-1]
        digin(link,n-i-1).first = t
        i+=1

def leaves(t):
    """Returns a list of all the entries of the leaf nodes of the Tree t.

    >>> leaves(Tree(1))
    [1]
    >>> leaves(Tree(1, [Tree(2, [Tree(3)]), Tree(4)]))
    [3, 4]
    """
    "*** YOUR CODE HERE ***"
    if t.is_leaf():
        return [t.entry]
    else:
        r=[]
        for b in t.branches:
            r+=leaves(b)
    return r


def cumulative_sum(t):
    """Return a new Tree, where each entry is the sum of all entries in the
    corresponding subtree of t.

    >>> t = Tree(1, [Tree(3, [Tree(5)]), Tree(7)])
    >>> cumulative = cumulative_sum(t)
    >>> t
    Tree(1, [Tree(3, [Tree(5)]), Tree(7)])
    >>> cumulative
    Tree(16, [Tree(8, [Tree(5)]), Tree(7)])
    >>> cumulative_sum(Tree(1))
    Tree(1)
    """
    "*** YOUR CODE HERE ***"
    branches = [cumulative_sum(st) for st in t.branches]
    nt = Tree(sum(st.entry for st in branches)+t.entry,branches)
    return nt

def same_shape(t1, t2):
    """Returns whether two Trees t1, t2 have the same shape. Two trees have the
    same shape if they have the same number of branches and each of their
    children have the same shape.

    >>> t, s = Tree(1), Tree(3)
    >>> same_shape(t, t)
    True
    >>> same_shape(t, s)
    True
    >>> t = Tree(1, [Tree(2), Tree(3)])
    >>> same_shape(t, s)
    False
    >>> s = cumulative_sum(t)
    >>> same_shape(t, s)
    True
    """
    "*** YOUR CODE HERE ***"
    if not (t1.is_leaf() and t2.is_leaf()):
        b1,b2 = t1.branches,t2.branches
        is_equal = len(b1)==len(b2)
        sub_equal =[same_shape(x,y) for x,y in zip(b1,b2)]
        return is_equal and (False in sub_equal)
    return True
   
def foldl(link, fn, z):
    """ Left fold
    >>> lst = Link(3, Link(2, Link(1)))
    >>> foldl(lst, sub, 0) # (((0 - 3) - 2) - 1)
    -6
    >>> foldl(lst, add, 0) # (((0 + 3) + 2) + 1)
    6
    >>> foldl(lst, mul, 1) # (((1 * 3) * 2) * 1)
    6
    """
    if link is Link.empty:
        return z
    "*** YOUR CODE HERE ***"
    return foldl(link.rest, fn, fn(z,link.first))        
        

def foldr(link, fn, z):
    """ Right fold
    >>> lst = Link(3, Link(2, Link(1)))
    >>> foldr(lst, sub, 0) # (3 - (2 - (1 - 0)))
    2
    >>> foldr(lst, add, 0) # (3 + (2 + (1 + 0)))
    6
    >>> foldr(lst, mul, 1) # (3 * (2 * (1 * 1)))
    6
    """
    "*** YOUR CODE HERE ***"
    if link is Link.empty:
        return z
    return fn(link.first,foldr(link.rest,fn,z))

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

西风吹草 发表于 2015-6-5 02:59:35 | 显示全部楼层
Question 2:
def insert(link, value, index):
        if index >= len(link):
                print('Index out of bounds!')
        elif index == 0:
                link.rest = Link(link.first, link.rest)
                link.first = value
        else:
                insert(link.rest, value, index - 1)

Question 4:
def square_tree(t):
        t.entry = t.entry ** 2
        if t.branches:
                for branch in t.branches:
                        square_tree(branch)

Question 5:
def list_to_link(lst):
        if not lst:
                return Link.empty
        return Link(lst[0], list_to_link(lst[1:]))

Question 6:
def link_to_list(link):
        if link is Link.empty:
                return []
        return [link.first] + link_to_list(link.rest)

Question 7:
def reverse(link):
        lst = link_to_list(link)
        lst.reverse()
        return list_to_link(lst)

Question 8:
def leaves(t):
        if t.is_leaf():
                return [t.entry]
        else:
                return sum([leaves(branch) for branch in t.branches], [])

Question 9:
def cumulative_sum(t):
        new_branches = [cumulative_sum(subtree) for subtree in t.branches]
        new_entry = sum(subtree.entry for subtree in new_branches) + t.entry
        return Tree(new_entry, new_branches)

Question 11:
def foldl(link, fn, z):
        if link is Link.empty:
                return z
        return foldl(link.rest, fn, fn(z, link.first))

Question 12:
def foldr(link, fn, z):
        if link is Link.empty:
                return z
        return fn(link.first, foldr(link.rest, fn, z))

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

wuxiaomin98 发表于 2015-6-6 05:31:11 | 显示全部楼层
## Recursive Objects ##

# Linked Lists

class Link:
    """A linked list.

    >>> s = Link(1, Link(2, Link(3, Link(4))))
    >>> len(s)
    4
    >>> s[2]
    3
    >>> s
    Link(1, Link(2, Link(3, Link(4))))
    """
    empty = ()

    def __init__(self, first, rest=empty):
        assert rest is Link.empty or isinstance(rest, Link)
        self.first = first
        self.rest = rest

    def __getitem__(self, i):
        if i == 0:
            return self.first
        else:
            return self.rest[i-1]

    def __len__(self):
        return 1 + len(self.rest)

    def __repr__(self):
        if self.rest is not Link.empty:
            rest_str = ', ' + repr(self.rest)
        else:
            rest_str = ''
        return 'Link({0}{1})'.format(repr(self.first), rest_str)

def insert(link, value, index):
    """Insert a value into a Link at the given index.

    >>> link = Link(1, Link(2, Link(3)))
    >>> insert(link, 9001, 0)
    >>> link
    Link(9001, Link(1, Link(2, Link(3))))
    >>> insert(link, 100, 2)
    >>> link
    Link(9001, Link(1, Link(100, Link(2, Link(3)))))
    >>> insert(link, 4, 5)
    Index out of bounds!
    """
    "*** YOUR CODE HERE ***"
    if index == 0:
        link.rest = Link(link.first, link.rest)
        link.first = value
    elif link.rest is Link.empty:
        print('Index out of bounds!')
    else:
        insert(link.rest, value, index - 1)

# Trees

class Tree:
    def __init__(self, entry, branches=()):
        self.entry = entry
        for branch in branches:
            assert isinstance(branch, Tree)
        self.branches = branches

    def __repr__(self):
        if self.branches:
            branches_str = ', ' + repr(self.branches)
        else:
            branches_str = ''
        return 'Tree({0}{1})'.format(self.entry, branches_str)

    def is_leaf(self):
        return not self.branches

def square_tree(t):
    """Mutates a Tree t by squaring all its elements.

    >>> t = Tree(1, [Tree(3, [Tree(5)]), Tree(7)])
    >>> square_tree(t)
    >>> t
    Tree(1, [Tree(9, [Tree(25)]), Tree(49)])
    """
    "*** YOUR CODE HERE ***"
    t.entry = t.entry ** 2
    for subtree in t.branches:
        square_tree(subtree)

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

liyimeng 发表于 2016-2-21 12:09:35 | 显示全部楼层
偷懒只把必做题做了。。Extra就没有理。。。
lab07.png

代码:
lab07.py
  1. ## Recursive Objects ##

  2. # Linked Lists

  3. class Link:
  4.         """A linked list.

  5.         >>> s = Link(1, Link(2, Link(3, Link(4))))
  6.         >>> len(s)
  7.         4
  8.         >>> s[2]
  9.         3
  10.         >>> s
  11.         Link(1, Link(2, Link(3, Link(4))))
  12.         """
  13.         empty = ()

  14.         def __init__(self, first, rest=empty):
  15.                 assert rest is Link.empty or isinstance(rest, Link)
  16.                 self.first = first
  17.                 self.rest = rest

  18.         def __getitem__(self, i):
  19.                 if i == 0:
  20.                         return self.first
  21.                 else:
  22.                         return self.rest[i-1]

  23.         def __len__(self):
  24.                 return 1 + len(self.rest)

  25.         def __repr__(self):
  26.                 if self.rest is not Link.empty:
  27.                         rest_str = ', ' + repr(self.rest)
  28.                 else:
  29.                         rest_str = ''
  30.                 return 'Link({0}{1})'.format(repr(self.first), rest_str)

  31. def insert(link, value, index):
  32.         """Insert a value into a Link at the given index.

  33.         >>> link = Link(1, Link(2, Link(3)))
  34.         >>> insert(link, 9001, 0)
  35.         >>> link
  36.         Link(9001, Link(1, Link(2, Link(3))))
  37.         >>> insert(link, 100, 2)
  38.         >>> link
  39.         Link(9001, Link(1, Link(100, Link(2, Link(3)))))
  40.         >>> insert(link, 4, 5)
  41.         Index out of bounds!
  42.         """
  43.         "*** YOUR CODE HERE ***"
  44.         if index >= len(link):
  45.                 print("Index out of bounds!")
  46.                 return
  47.         i = 0
  48.         while i < index:
  49.                 link = link.rest
  50.                 i += 1
  51.         other = Link(link.first, link.rest)
  52.         link.first = value
  53.         link.rest = other

  54. # Trees

  55. class Tree:
  56.     def __init__(self, entry, branches=()):
  57.         self.entry = entry
  58.         for branch in branches:
  59.             assert isinstance(branch, Tree)
  60.         self.branches = branches

  61.     def __repr__(self):
  62.         if self.branches:
  63.             branches_str = ', ' + repr(self.branches)
  64.         else:
  65.             branches_str = ''
  66.         return 'Tree({0}{1})'.format(self.entry, branches_str)

  67.     def is_leaf(self):
  68.         return not self.branches

  69. def square_tree(t):
  70.         """Mutates a Tree t by squaring all its elements.

  71.         >>> t = Tree(1, [Tree(3, [Tree(5)]), Tree(7)])
  72.         >>> square_tree(t)
  73.         >>> t
  74.         Tree(1, [Tree(9, [Tree(25)]), Tree(49)])
  75.         """
  76.         "*** YOUR CODE HERE ***"
  77.         t.entry *= t.entry
  78.         for branch in t.branches:
  79.                 square_tree(branch)
  80.                
复制代码
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-5 20:42

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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