"""61A Homework 7 Name: Login: TA: Section: """ # Q1. class Square(object): def __init__(self, side): self.side = side class Rect(object): def __init__(self, width, height): self.width = width self.height = height def type_tag(s): return type_tag.tags[type(s)] type_tag.tags = {Square: 's', Rect: 'r'} def apply(operator_name, shape): """Apply operator to shape. >>> apply('area', Square(10)) 100 >>> apply('perimeter', Square(5)) 20 >>> apply('area', Rect(5, 10)) 50 >>> apply('perimeter', Rect(2, 4)) 12 """ "*** YOUR CODE HERE ***" # Q2. def g(n): """Return the value of G(n), computed recursively. >>> g(1) 1 >>> g(2) 2 >>> g(3) 3 >>> g(4) 10 >>> g(5) 22 """ "*** YOUR CODE HERE ***" def g_iter(n): """Return the value of G(n), computed iteratively. >>> g_iter(1) 1 >>> g_iter(2) 2 >>> g_iter(3) 3 >>> g_iter(4) 10 >>> g_iter(5) 22 """ "*** YOUR CODE HERE ***" # Q3. def part(n): """Return the number of partitions of positive integer n. >>> part(5) 7 >>> part(10) 42 >>> part(15) 176 >>> part(20) 627 """ "*** YOUR CODE HERE ***" # Q4. from operator import sub, mul def make_anonymous_factorial(): """Return the value of an expression that computes factorial. >>> make_anonymous_factorial()(5) 120 """ return YOUR_EXPRESSION_HERE # Q5. def has_cycle(s): """Return whether Rlist s contains a cycle. >>> s = Rlist(1, Rlist(2, Rlist(3))) >>> s.rest.rest.rest = s >>> has_cycle(s) True >>> t = Rlist(1, Rlist(2, Rlist(3))) >>> has_cycle(t) False """ "*** YOUR CODE HERE ***" def has_cycle_constant(s): """Return whether Rlist s contains a cycle. >>> s = Rlist(1, Rlist(2, Rlist(3))) >>> s.rest.rest.rest = s >>> has_cycle_constant(s) True >>> t = Rlist(1, Rlist(2, Rlist(3))) >>> has_cycle_constant(t) False """ "*** YOUR CODE HERE ***" class Rlist(object): """A recursive list consisting of a first element and the rest.""" class EmptyList(object): def __len__(self): return 0 empty = EmptyList() def __init__(self, first, rest=empty): self.first = first self.rest = rest def __repr__(self): args = repr(self.first) if self.rest is not Rlist.empty: args += ', {0}'.format(repr(self.rest)) return 'Rlist({0})'.format(args) def __len__(self): return 1 + len(self.rest) def __getitem__(self, i): if i == 0: return self.first return self.rest[i-1]