一亩三分地论坛

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

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

[CS61A]HW06

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

[其他]CS61A #3 - 04@UCBerkely

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

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

x
HW06 Link: http://gaotx.com/cs61a/hw/hw06/My solution: http://gaotx.com.blogs/2015/05/28/cs61a-hw06/




评分

1

查看全部评分

FFFelix 发表于 2015-6-1 18:41:51 | 显示全部楼层
终于等到啦~ 不过那个循环的题目还是参考了答案

class Link:
    """A linked list.

    >>> s = Link(3, Link(4, Link(5)))
    >>> len(s)
    3
    >>> s[2]
    5
    >>> s
    Link(3, Link(4, Link(5)))
    """
    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:
            rest_str = ', ' + repr(self.rest)
        else:
            rest_str = ''
        return 'Link({0}{1})'.format(self.first, rest_str)

def deep_map(f, s):
    """Return a Link with the same structure as s but with fn mapped over
    its elements and any elements of linked lists contained anywhere within it.

    >>> s = Link(1, Link(Link(2, Link(3)), Link(4)))
    >>> deep_map(lambda x: x * x, s)
    Link(1, Link(Link(4, Link(9)), Link(16)))
    >>> s # unchanged
    Link(1, Link(Link(2, Link(3)), Link(4)))
    >>> deep_map(lambda x: 2 * x, Link(s, Link(Link(Link(5)))))
    Link(Link(2, Link(Link(4, Link(6)), Link(8))), Link(Link(Link(10))))
    """
    "*** YOUR CODE HERE ***"
    if s == Link.empty:
        return s
    elif not isinstance(s, Link):
        return f(s)
    return Link(deep_map(f,s.first),deep_map(f,s.rest))

def reverse(s):
    """Return a linked list with the elements of s in reverse order.

    >>> s = Link(3, Link(5, Link(4, Link(6))))
    >>> reverse(s)
    Link(6, Link(4, Link(5, Link(3))))
    >>> s
    Link(3, Link(5, Link(4, Link(6))))
    """
    "*** YOUR CODE HERE ***"
    def reverse_to(s, t):
        if s == Link.empty:
            return t
        else:
            return reverse_to(s.rest, Link(s.first, t))
    return reverse_to(s, Link.empty)

def has_cycle(s):
    """Return whether Link s contains a cycle.

    >>> s = Link(1, Link(2, Link(3)))
    >>> s.rest.rest.rest = s
    >>> has_cycle(s)
    True
    >>> t = Link(1, Link(2, Link(3)))
    >>> has_cycle(t)
    False
    """
    "*** YOUR CODE HERE ***"
    temp = set()
    while s != Link.empty:
        if s in temp:
            return True
        temp.add(s)
        s = s.rest
    return False

def has_cycle_constant(s):
    """Return whether Link s contains a cycle.

    >>> s = Link(1, Link(2, Link(3)))
    >>> s.rest.rest.rest = s
    >>> has_cycle_constant(s)
    True
    >>> t = Link(1, Link(2, Link(3)))
    >>> has_cycle_constant(t)
    False
    """
    # Challenge: replace this line with your implementation
    return has_cycle(s)

class Mobile:
    """A binary mobile has branches; each branch has a weight or a mobile.

    >>> m = Mobile(Branch(1, Weight(2)), Branch(2, Weight(1)))
    >>> m.weight
    3
    >>> m.is_balanced()
    True
    >>> m.left.contents = Mobile(Branch(1, Weight(1)), Branch(2, Weight(1)))
    >>> m.weight
    3
    >>> m.left.contents.is_balanced()
    False
    >>> m.is_balanced() # All submobiles must be balanced for m to be balanced
    False
    >>> m.left.contents.right.contents.weight = 0.5
    >>> m.left.contents.is_balanced()
    True
    >>> m.is_balanced()
    False
    >>> m.right.length = 1.5
    >>> m.is_balanced()
    True
    """
    def __init__(self, left, right):
        for v in (left, right):
            if type(v) != Branch:
                raise TypeError(str(v) + ' is not a Branch')
        self.left = left
        self.right = right

    @property
    def weight(self):
        """The total weight of the mobile."""
        "*** YOUR CODE HERE ***"
        return self.left.contents.weight + self.right.contents.weight

    def is_balanced(self):
        """True if and only if the mobile is balanced."""
        "*** YOUR CODE HERE ***"
        torque_equal = self.left.torque == self.right.torque
        lc, rc = self.left.contents, self.right.contents
        return torque_equal and lc.is_balanced() and rc.is_balanced()

class Branch:
    """A branch of a binary mobile."""
    def __init__(self, length, contents):
        if type(contents) not in (Weight, Mobile):
            raise TypeError(str(contents) + ' is not a Weight or Mobile')
        self.length = length
        self.contents = contents

    @property
    def torque(self):
        """The torque on the branch"""
        return self.length * self.contents.weight

class Weight:
    """A weight at the end of a branch."""
    def __init__(self, weight):
        self.weight = weight

    def is_balanced(self):
        return True




评分

1

查看全部评分

回复 支持 反对

使用道具 举报

karte_polo 发表于 2015-6-3 23:34:34 | 显示全部楼层
class Link:
    """A linked list.

    >>> s = Link(3, Link(4, Link(5)))
    >>> len(s)
    3
    >>> s[2]
    5
    >>> s
    Link(3, Link(4, Link(5)))
    """
    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:
            rest_str = ', ' + repr(self.rest)
        else:
            rest_str = ''
        return 'Link({0}{1})'.format(self.first, rest_str)

def deep_map(f, s):
    """Return a Link with the same structure as s but with fn mapped over
    its elements and any elements of linked lists contained anywhere within it.

    >>> s = Link(1, Link(Link(2, Link(3)), Link(4)))
    >>> deep_map(lambda x: x * x, s)
    Link(1, Link(Link(4, Link(9)), Link(16)))
    >>> s # unchanged
    Link(1, Link(Link(2, Link(3)), Link(4)))
    >>> deep_map(lambda x: 2 * x, Link(s, Link(Link(Link(5)))))
    Link(Link(2, Link(Link(4, Link(6)), Link(8))), Link(Link(Link(10))))
    """
    "*** YOUR CODE HERE ***"
    def LinkE_Handler(i):
        if isinstance(i,Link):
            return Link(deep_map(f,i),)
        else:
            return Link(f(i),)
    if s.rest is Link.empty:
        return LinkE_Handler(s.first)
    else:
        return Link(LinkE_Handler(s.first),deep_map(f,s.rest))


def reverse(s):
    """Return a linked list with the elements of s in reverse order.

    >>> s = Link(3, Link(5, Link(4, Link(6))))
    >>> reverse(s)
    Link(6, Link(4, Link(5, Link(3))))
    >>> s
    Link(3, Link(5, Link(4, Link(6))))
    """
    "*** YOUR CODE HERE ***"
    def reverse_to(s,t):
        if s is Link.empty:
            return t
        else:
            return reverse_to(s.rest,Link(s.first,t))
    return reverse_to(s,Link.empty)
            


def has_cycle(s):
    """Return whether Link s contains a cycle.

    >>> s = Link(1, Link(2, Link(3)))
    >>> s.rest.rest.rest = s
    >>> has_cycle(s)
    True
    >>> t = Link(1, Link(2, Link(3)))
    >>> has_cycle(t)
    False
    """
    "*** YOUR CODE HERE ***"
    def cycled(t,s):
        if t is Link.empty:
            return False
        elif t==s:
            return True
        return cycled(t.rest,s)
    return cycled(s.rest,s)

def has_cycle_constant(s):
    """Return whether Link s contains a cycle.

    >>> s = Link(1, Link(2, Link(3)))
    >>> s.rest.rest.rest = s
    >>> has_cycle_constant(s)
    True
    >>> t = Link(1, Link(2, Link(3)))
    >>> has_cycle_constant(t)
    False
    """
    # Challenge: replace this line with your implementation
    return has_cycle(s)

class Mobile:
    """A binary mobile has branches; each branch has a weight or a mobile.

    >>> m = Mobile(Branch(1, Weight(2)), Branch(2, Weight(1)))
    >>> m.weight
    3
    >>> m.is_balanced()
    True
    >>> m.left.contents = Mobile(Branch(1, Weight(1)), Branch(2, Weight(1)))
    >>> m.weight
    3
    >>> m.left.contents.is_balanced()
    False
    >>> m.is_balanced() # All submobiles must be balanced for m to be balanced
    False
    >>> m.left.contents.right.contents.weight = 0.5
    >>> m.left.contents.is_balanced()
    True
    >>> m.is_balanced()
    False
    >>> m.right.length = 1.5
    >>> m.is_balanced()
    True
    """
    def __init__(self, left, right):
        for v in (left, right):
            if type(v) != Branch:
                raise TypeError(str(v) + ' is not a Branch')
        self.left = left
        self.right = right

    @property
    def weight(self):
        """The total weight of the mobile."""
        "*** YOUR CODE HERE ***"
        return self.left.contents.weight+self.right.contents.weight

    def is_balanced(self):
        """True if and only if the mobile is balanced."""
        "*** YOUR CODE HERE ***"
        torque_equal = self.left.torque == self.right.torque
        l, r = self.left.contents, self.right.contents
        return torque_equal and l.is_balanced() and r.is_balanced()

        

class Branch:
    """A branch of a binary mobile."""
    def __init__(self, length, contents):
        if type(contents) not in (Weight, Mobile):
            raise TypeError(str(contents) + ' is not a Weight or Mobile')
        self.length = length
        self.contents = contents

    @property
    def torque(self):
        """The torque on the branch"""
        return self.length * self.contents.weight

class Weight:
    """A weight at the end of a branch."""
    def __init__(self, weight):
        self.weight = weight

    def is_balanced(self):
        return True

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

西风吹草 发表于 2015-6-4 00:35:34 | 显示全部楼层
Question 1:
def deep_map(f, s):
        if s is Link.empty:
                return s
        elif not isinstance(s, Link):
                return f(s)
        else:
                return Link(deep_map(f, s.first), deep_map(f, s.rest))

Question 2:
def reverse(s):
        t, i = Link(s[0]), 1
        while i < len(s):
                t = Link(s[i], t)
                i += 1
        return t

Question 3:
def has_cycle(s):
        while s != Link.empty:
                if s in lists:
                        return True
                else:
                        lists.add(s)
                        s = s.rest
        return False

Question 4:
class Mobile:
        def __init__(self, left, right):
                for v in (left, right):
                        if type(v) != Branch:
                                raise TypeError(str(v) + ' is not a Branch')
                self.left = left
                self.right = right
        @property
        def weight(self):
                return self.left.contents.weight + self.right.contents.weight
        def is_balanced(self):
                return self.left.torque == self.right.torque and self.left.contents.is_balanced() and self.right.contents.is_balanced()

class Branch:
        def __init__(self, length, contents):
                if type(contents) not in (Weight, Mobile):
                        raise TypeError(str(contents) + ' is not a Weight or Mobile')
                self.length = length
                self.contents = contents
        @property
        def torque(self):
                return self.length * self.contents.weight

class Weight:
        def __init__(self, weight):
                self.weight = weight
        def is_balanced(self):
                return True

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

wuxiaomin98 发表于 2015-6-6 05:20:05 | 显示全部楼层
感觉好难
class Link:
    """A linked list.

    >>> s = Link(3, Link(4, Link(5)))
    >>> len(s)
    3
    >>> s[2]
    5
    >>> s
    Link(3, Link(4, Link(5)))
    """
    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:
            rest_str = ', ' + repr(self.rest)
        else:
            rest_str = ''
        return 'Link({0}{1})'.format(self.first, rest_str)

def deep_map(f, s):
    """Return a Link with the same structure as s but with fn mapped over
    its elements and any elements of linked lists contained anywhere within it.

    >>> s = Link(1, Link(Link(2, Link(3)), Link(4)))
    >>> deep_map(lambda x: x * x, s)
    Link(1, Link(Link(4, Link(9)), Link(16)))
    >>> s # unchanged
    Link(1, Link(Link(2, Link(3)), Link(4)))
    >>> deep_map(lambda x: 2 * x, Link(s, Link(Link(Link(5)))))
    Link(Link(2, Link(Link(4, Link(6)), Link(8))), Link(Link(Link(10))))
    """
    "*** YOUR CODE HERE ***"
    if s is Link.empty:
        return s
    elif not isinstance(s, Link):
        return f(s)
    return Link(deep_map(f, s.first), deep_map(f, s.rest))

def reverse(s):
    """Return a linked list with the elements of s in reverse order.

    >>> s = Link(3, Link(5, Link(4, Link(6))))
    >>> reverse(s)
    Link(6, Link(4, Link(5, Link(3))))
    >>> s
    Link(3, Link(5, Link(4, Link(6))))
    """
    "*** YOUR CODE HERE ***"
    def reverse_to(s):
        if s is Link.empty:
            return t
        else:
            return reverse_to(s.rest, Link(s.first, t))
    return reverse_to(s, Link.empty)

def has_cycle(s):
    """Return whether Link s contains a cycle.

    >>> s = Link(1, Link(2, Link(3)))
    >>> s.rest.rest.rest = s
    >>> has_cycle(s)
    True
    >>> t = Link(1, Link(2, Link(3)))
    >>> has_cycle(t)
    False
    """
    "*** YOUR CODE HERE ***"
    lists = set()
    while s != Link.empty:
        if s in lists:
            return True
        lists.add(s)
        s = s.rest
    return False

def has_cycle_constant(s):
    """Return whether Link s contains a cycle.

    >>> s = Link(1, Link(2, Link(3)))
    >>> s.rest.rest.rest = s
    >>> has_cycle_constant(s)
    True
    >>> t = Link(1, Link(2, Link(3)))
    >>> has_cycle_constant(t)
    False
    """
    # Challenge: replace this line with your implementation
    if s == Link.empty:
        return False
    else:
        slow, fast = s, s.rest
        while fast != Link.empty:
          if fast.rest == Link.empty:
              return False
          elif fast == slow or fast.rest == slow:
              return True
          else:
              slow, fast = slow.rest, fast.rest.rest
        return False
回复 支持 反对

使用道具 举报

reasonapp 发表于 2015-6-28 18:13:58 | 显示全部楼层
这次作业非常难。。。。搞了一下午还参考了答案。原来这就是算法啊。。代码:
#hw06
#Q1
class Link:
    """A linked list.

    >>> s = Link(3, Link(4, Link(5)))
    >>> len(s)
    3
    >>> s[2]
    5
    >>> s
    Link(3, Link(4, Link(5)))
    """
    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:
            rest_str = ', ' + repr(self.rest)
        else:
            rest_str = ''
        return 'Link({0}{1})'.format(self.first, rest_str)

def deep_map(f, s):
    """Return a Link with the same structure as s but with fn mapped over
    its elements and any elements of linked lists contained anywhere within it.

    >>> s = Link(1, Link(Link(2, Link(3)), Link(4)))
    >>> deep_map(lambda x: x * x, s)
    Link(1, Link(Link(4, Link(9)), Link(16)))
    >>> s # unchanged
    Link(1, Link(Link(2, Link(3)), Link(4)))
    >>> deep_map(lambda x: 2 * x, Link(s, Link(Link(Link(5)))))
    Link(Link(2, Link(Link(4, Link(6)), Link(8))), Link(Link(Link(10))))
    """
    "*** YOUR CODE HERE ***"
    if s is Link.empty:
        return s
    elif not isinstance(s, Link):
        return f(s)
    return Link(deep_map(f, s.first), deep_map(f, s.rest))
   
#Q2
def reverse(s):
    """Return a linked list with the elements of s in reverse order.

    >>> s = Link(3, Link(5, Link(4, Link(6))))
    >>> reverse(s)
    Link(6, Link(4, Link(5, Link(3))))
    >>> s
    Link(3, Link(5, Link(4, Link(6))))
    """
    "*** YOUR CODE HERE ***"
    def reverse_to(s, t):
        if s is Link.empty:
            return t
        else:
            return reverse_to(s.rest, Link(s.first, t))
    return reverse_to(s, Link.empty)

#Q3
def has_cycle(s):
    """Return whether Link s contains a cycle.

    >>> s = Link(1, Link(2, Link(3)))
    >>> s.rest.rest.rest = s
    >>> has_cycle(s)
    True
    >>> t = Link(1, Link(2, Link(3)))
    >>> has_cycle(t)
    False
    """
    "*** YOUR CODE HERE ***"
    lists = set()
    while s != Link.empty:
        if s in lists:
            return True
        lists.add(s)
        s = s.rest
    return False      

def has_cycle_constant(s):
    """Return whether Link s contains a cycle.

    >>> s = Link(1, Link(2, Link(3)))
    >>> s.rest.rest.rest = s
    >>> has_cycle_constant(s)
    True
    >>> t = Link(1, Link(2, Link(3)))
    >>> has_cycle_constant(t)
    False
    """
    # Challenge: replace this line with your implementation
    if s == Link.empty:
        return False
    else:
        slow, fast = s, s.rest
        while fast != Link.empty:
            if fast.rest == Link.empty:
                return False
            elif fast == slow or fast.rest == slow:
                return True
            else:
                slow, fast = slow.rest, fast.rest.rest
        return False            
            
#Q4
class Mobile:
    """A binary mobile has branches; each branch has a weight or a mobile.

    >>> m = Mobile(Branch(1, Weight(2)), Branch(2, Weight(1)))
    >>> m.weight
    3
    >>> m.is_balanced()
    True
    >>> m.left.contents = Mobile(Branch(1, Weight(1)), Branch(2, Weight(1)))
    >>> m.weight
    3
    >>> m.left.contents.is_balanced()
    False
    >>> m.is_balanced() # All submobiles must be balanced for m to be balanced
    False
    >>> m.left.contents.right.contents.weight = 0.5
    >>> m.left.contents.is_balanced()
    True
    >>> m.is_balanced()
    False
    >>> m.right.length = 1.5
    >>> m.is_balanced()
    True
    """
    def __init__(self, left, right):
        for v in (left, right):
            if type(v) != Branch:
                raise TypeError(str(v) + ' is not a Branch')
        self.left = left
        self.right = right

    @property
    def weight(self):
        """The total weight of the mobile."""
        "*** YOUR CODE HERE ***"
        return self.left.contents.weight + self.right.contents.weight

    def is_balanced(self):
        """True if and only if the mobile is balanced."""
        "*** YOUR CODE HERE ***"
        torque_equal = self.left.torque == self.right.torque
        lc, rc = self.left.contents, self.right.contents
        return torque_equal and lc.is_balanced() and rc.is_balanced()
        
class Branch:
    """A branch of a binary mobile."""
    def __init__(self, length, contents):
        if type(contents) not in (Weight, Mobile):
            raise TypeError(str(contents) + ' is not a Weight or Mobile')
        self.length = length
        self.contents = contents

    @property
    def torque(self):
        """The torque on the branch"""
        return self.length * self.contents.weight

class Weight:
    """A weight at the end of a branch."""
    def __init__(self, weight):
        self.weight = weight

    def is_balanced(self):
        return True



回复 支持 反对

使用道具 举报

liyimeng 发表于 2016-2-23 11:47:18 | 显示全部楼层
交一下作业:
hw06.png

extra懒得写了。。估计解法就是用双指针来解决吧,看能不能追击上。。
上传别的部分的代码:
  1. class Link:
  2.         """A linked list.

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

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

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

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

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

  29. def deep_map(f, s):
  30.         """Return a Link with the same structure as s but with fn mapped over
  31.         its elements and any elements of linked lists contained anywhere within it.

  32.         >>> s = Link(1, Link(Link(2, Link(3)), Link(4)))
  33.         >>> deep_map(lambda x: x * x, s)
  34.         Link(1, Link(Link(4, Link(9)), Link(16)))
  35.         >>> s # unchanged
  36.         Link(1, Link(Link(2, Link(3)), Link(4)))
  37.         >>> deep_map(lambda x: 2 * x, Link(s, Link(Link(Link(5)))))
  38.         Link(Link(2, Link(Link(4, Link(6)), Link(8))), Link(Link(Link(10))))
  39.         """
  40.         "*** YOUR CODE HERE ***"
  41.         if s is Link.empty:
  42.                 return s
  43.         elif isinstance(s.first, Link):
  44.                 return Link(deep_map(f, s.first), deep_map(f, s.rest))
  45.         else:
  46.                 return Link(f(s.first), deep_map(f, s.rest))

  47. def reverse(s):
  48.         """Return a linked list with the elements of s in reverse order.

  49.         >>> s = Link(3, Link(5, Link(4, Link(6))))
  50.         >>> reverse(s)
  51.         Link(6, Link(4, Link(5, Link(3))))
  52.         >>> s
  53.         Link(3, Link(5, Link(4, Link(6))))
  54.         """
  55.         "*** YOUR CODE HERE ***"
  56.         reverse_lst = Link.empty
  57.         while s is not Link.empty:
  58.                 reverse_lst = Link(s.first, reverse_lst)
  59.                 s = s.rest
  60.         return reverse_lst
  61.        

  62. def has_cycle(s):
  63.         """Return whether Link s contains a cycle.

  64.         >>> s = Link(1, Link(2, Link(3)))
  65.         >>> s.rest.rest.rest = s
  66.         >>> has_cycle(s)
  67.         True
  68.         >>> t = Link(1, Link(2, Link(3)))
  69.         >>> has_cycle(t)
  70.         False
  71.         """
  72.         hashset = set()
  73.         while s is not Link.empty:
  74.                 if s in hashset:
  75.                         return True
  76.                 else:
  77.                         hashset.add(s)
  78.                 s = s.rest
  79.         return False

  80. def has_cycle_constant(s):
  81.         """Return whether Link s contains a cycle.

  82.         >>> s = Link(1, Link(2, Link(3)))
  83.         >>> s.rest.rest.rest = s
  84.         >>> has_cycle_constant(s)
  85.         True
  86.         >>> t = Link(1, Link(2, Link(3)))
  87.         >>> has_cycle_constant(t)
  88.         False
  89.         """
  90.         # Challenge: replace this line with your implementation
  91.         return has_cycle(s)

  92. class Mobile:
  93.         """A binary mobile has branches; each branch has a weight or a mobile.

  94.         >>> m = Mobile(Branch(1, Weight(2)), Branch(2, Weight(1)))
  95.         >>> m.weight
  96.         3
  97.         >>> m.is_balanced()
  98.         True
  99.         >>> m.left.contents = Mobile(Branch(1, Weight(1)), Branch(2, Weight(1)))
  100.         >>> m.weight
  101.         3
  102.         >>> m.left.contents.is_balanced()
  103.         False
  104.         >>> m.is_balanced() # All submobiles must be balanced for m to be balanced
  105.         False
  106.         >>> m.left.contents.right.contents.weight = 0.5
  107.         >>> m.left.contents.is_balanced()
  108.         True
  109.         >>> m.is_balanced()
  110.         False
  111.         >>> m.right.length = 1.5
  112.         >>> m.is_balanced()
  113.         True
  114.         """
  115.         def __init__(self, left, right):
  116.                 for v in (left, right):
  117.                         if type(v) != Branch:
  118.                                 raise TypeError(str(v) + ' is not a Branch')
  119.                 self.left = left
  120.                 self.right = right

  121.         @property
  122.         def weight(self):
  123.                 """The total weight of the mobile."""
  124.                 "*** YOUR CODE HERE ***"
  125.                 return self.left.contents.weight + self.right.contents.weight

  126.         def is_balanced(self):
  127.                 """True if and only if the mobile is balanced."""
  128.                 "*** YOUR CODE HERE ***"
  129.                 return self.left.contents.is_balanced() and self.right.contents.is_balanced() and self.left.torque == self.right.torque

  130. class Branch:
  131.         """A branch of a binary mobile."""
  132.         def __init__(self, length, contents):
  133.                 if type(contents) not in (Weight, Mobile):
  134.                         raise TypeError(str(contents) + ' is not a Weight or Mobile')
  135.                 self.length = length
  136.                 self.contents = contents

  137.         @property
  138.         def torque(self):
  139.                 """The torque on the branch"""
  140.                 return self.length * self.contents.weight

  141. class Weight:
  142.         """A weight at the end of a branch."""
  143.         def __init__(self, weight):
  144.                 self.weight = weight

  145.         def is_balanced(self):
  146.                 return True


复制代码
回复 支持 反对

使用道具 举报

Liaeve 发表于 2016-5-9 20:33:57 | 显示全部楼层
class Link:
    """A linked list.

    >>> s = Link(3, Link(4, Link(5)))
    >>> len(s)
    3
    >>> s[2]
    5
    >>> s
    Link(3, Link(4, Link(5)))
    """
    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:
            rest_str = ', ' + repr(self.rest)
        else:
            rest_str = ''
        return 'Link({0}{1})'.format(self.first, rest_str)

def deep_map(f, s):
    """Return a Link with the same structure as s but with fn mapped over
    its elements and any elements of linked lists contained anywhere within it.

    >>> s = Link(1, Link(Link(2, Link(3)), Link(4)))
    >>> deep_map(lambda x: x * x, s)
    Link(1, Link(Link(4, Link(9)), Link(16)))
    >>> s # unchanged
    Link(1, Link(Link(2, Link(3)), Link(4)))
    >>> deep_map(lambda x: 2 * x, Link(s, Link(Link(Link(5)))))
    Link(Link(2, Link(Link(4, Link(6)), Link(8))), Link(Link(Link(10))))
    """
    "*** YOUR CODE HERE ***"
    if s is Link.empty:
        return s
    elif not isinstance(s, Link):
        return f(s)
    return Link(deep_map(f, s.first), deep_map(f, s.rest))

def reverse(s):
    """Return a linked list with the elements of s in reverse order.

    >>> s = Link(3, Link(5, Link(4, Link(6))))
    >>> reverse(s)
    Link(6, Link(4, Link(5, Link(3))))
    >>> s
    Link(3, Link(5, Link(4, Link(6))))
    """
    "*** YOUR CODE HERE ***"
    i = 1
    t = Link(s[0])
    while i < len(s):
        t = Link(s[i], t)
        i += 1
    return t

def has_cycle(s):
    """Return whether Link s contains a cycle.

    >>> s = Link(1, Link(2, Link(3)))
    >>> s.rest.rest.rest = s
    >>> has_cycle(s)
    True
    >>> t = Link(1, Link(2, Link(3)))
    >>> has_cycle(t)
    False
    """
    "*** YOUR CODE HERE ***"
    def cycle(s, t):
        if t is Link.empty:
            return False
        elif t == s:
            return True
        else:
            return cycle(s, t.rest)
    return cycle(s, s.rest)

def has_cycle_constant(s):
    """Return whether Link s contains a cycle.

    >>> s = Link(1, Link(2, Link(3)))
    >>> s.rest.rest.rest = s
    >>> has_cycle_constant(s)
    True
    >>> t = Link(1, Link(2, Link(3)))
    >>> has_cycle_constant(t)
    False
    """
    # Challenge: replace this line with your implementation
    return has_cycle(s)

class Mobile:
    """A binary mobile has branches; each branch has a weight or a mobile.

    >>> m = Mobile(Branch(1, Weight(2)), Branch(2, Weight(1)))
    >>> m.weight
    3
    >>> m.is_balanced()
    True
    >>> m.left.contents = Mobile(Branch(1, Weight(1)), Branch(2, Weight(1)))
    >>> m.weight
    3
    >>> m.left.contents.is_balanced()
    False
    >>> m.is_balanced() # All submobiles must be balanced for m to be balanced
    False
    >>> m.left.contents.right.contents.weight = 0.5
    >>> m.left.contents.is_balanced()
    True
    >>> m.is_balanced()
    False
    >>> m.right.length = 1.5
    >>> m.is_balanced()
    True
    """
    def __init__(self, left, right):
        for v in (left, right):
            if type(v) != Branch:
                raise TypeError(str(v) + ' is not a Branch')
        self.left = left
        self.right = right

    @property
    def weight(self):
        """The total weight of the mobile."""
        "*** YOUR CODE HERE ***"
        return self.left.contents.weight + self.right.contents.weight

    def is_balanced(self):
        """True if and only if the mobile is balanced."""
        "*** YOUR CODE HERE ***"
        equal_torque = self.left.torque == self.right.torque
        return equal_torque and self.left.contents.is_balanced() and self.right.contents.is_balanced()

class Branch:
    """A branch of a binary mobile."""
    def __init__(self, length, contents):
        if type(contents) not in (Weight, Mobile):
            raise TypeError(str(contents) + ' is not a Weight or Mobile')
        self.length = length
        self.contents = contents

    @property
    def torque(self):
        """The torque on the branch"""
        return self.length * self.contents.weight

class Weight:
    """A weight at the end of a branch."""
    def __init__(self, weight):
        self.weight = weight

    def is_balanced(self):
        return True


回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-7 16:47

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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