📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
12
返回列表 发新帖
楼主: sky420
跳转到指定楼层
上一主题 下一主题
收起左侧

[CS61A]Lab03: Recrusion

🔗
wuxiaomin98 2015-5-23 07:37:52 | 只看该作者
全局:
# Q2
def make_buzzer(n):
    """ Returns a function that prints numbers in a specified
    range except those divisible by n.

    >>> i_hate_fives = make_buzzer(5)
    >>> i_hate_fives(10)
    Buzz!
    1
    2
    3
    4
    Buzz!
    6
    7
    8
    9
    """
    "*** YOUR CODE HERE ***"
    def f(range):
        i = 0
        while i < range:
            if n % i == 0:
                print("Buzz!")
            else:
                print(i)
            i += 1
    return f



    return f

# Q4
def f1():
    """
    >>> f1()
    3
    """
    "*** YOUR CODE HERE ***"
    return 3

def f2():
    """
    >>> f2()()
    3
    """
    "*** YOUR CODE HERE ***"
    return lambda: 3

def f3():
    """
    >>> f3()(3)
    3
    """
    "*** YOUR CODE HERE ***"
    return lambda x: x

def f4():
    """
    >>> f4()()(3)()
    3
    """
    "*** YOUR CODE HERE ***"
    return lambda: lambda x: lambda: x

# Q6
def sum(n):
    """Computes the sum of all integers between 1 and n, inclusive.
    Assume n is positive.

    >>> sum(1)
    1
    >>> sum(5)  # 1 + 2 + 3 + 4 + 5
    15
    """
    "*** YOUR CODE HERE ***"
    if n == 1:
        return 1
    else:
        return n + sum(n - 1)

# Q7

def sum_every_other_number(n):
    """Return the sum of every other natural number
    up to n, inclusive.

    >>> sum_every_other_number(8)
    20
    >>> sum_every_other_number(9)
    25
    """
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return n + sum_every_other_number(n - 2)


def fibonacci(n):
    """Return the nth fibonacci number.
   
    >>> fibonacci(11)
    89
    """
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fibonacci(n - 1) + fibonacci(n - 2)


# Q8
def hailstone(n):
    """Print out the hailstone sequence starting at n, and return the
    number of elements in the sequence.

    >>> a = hailstone(10)
    10
    5
    16
    8
    4
    2
    1
    >>> a
    7
    """
    "*** YOUR CODE HERE ***"
    print(n)
    if n == 1:
        return 1
    elif n % 2 == 1:
        return 1 + hailstone(n // 2)
    else:
        return 1 + hailstone(3 * n + 1)
回复

使用道具 举报

🔗
reasonapp 2015-6-12 21:58:58 | 只看该作者
全局:
递归还是不难的,不过Q4的lambda想了好半天
上代码~

#lab03 Q2
def make_buzzer(n):
    """ Returns a function that prints numbers in a specified
    range except those divisible by n.

    >>> i_hate_fives = make_buzzer(5)
    >>> i_hate_fives(10)
    Buzz!
    1
    2
    3
    4
    Buzz!
    6
    7
    8
    9
    """
    "*** YOUR CODE HERE ***"
    def h(x):
        i = 0
        while(i < x):
            if(i % n) == 0:
                print('Buzz!')
            else:
                print i
            i += 1
    return h
   
#Q4
def f1():
    """
    >>> f1()
    3
    """
    "*** YOUR CODE HERE ***"
    return 3

def f2():
    """
    >>> f2()()
    3
    """
    "*** YOUR CODE HERE ***"
    return lambda: 3

def f3():
    """
    >>> f3()(3)
    3
    """
    "*** YOUR CODE HERE ***"
    return lambda x: x

def f4():
    """
    >>> f4()()(3)()
    3
    """
    "*** YOUR CODE HERE ***"
    return lambda: lambda x: lambda: x
   
#Q6
def sum(n):
    """Computes the sum of all integers between 1 and n, inclusive.
    Assume n is positive.

    >>> sum(1)
    1
    >>> sum(5)  # 1 + 2 + 3 + 4 + 5
    15
    """
    "*** YOUR CODE HERE ***"
    if n == 1:
        return 1
    return n + sum(n-1)
   
#Q7
def sum_every_other_number(n):
    """Return the sum of every other natural number
    up to n, inclusive.

    >>> sum_every_other_number(8)
    20
    >>> sum_every_other_number(9)
    25
    """
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return n + sum_every_other_number(n - 2)
        
def fibonacci(n):
    """Return the nth fibonacci number.

    >>> fibonacci(11)
    89
    """
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fibonacci(n - 1) + fibonacci(n - 2)
        
#Q8
def hailstone(n):
    """Print out the hailstone sequence starting at n, and return the
    number of elements in the sequence.

    >>> a = hailstone(10)
    10
    5
    16
    8
    4
    2
    1
    >>> a
    7
    """
    "*** YOUR CODE HERE ***"   
    print n
    if n == 1:
    #     print n
        return 1
    elif n % 2 == 0:
    #     print n
        return 1 + hailstone(n/2)
    elif n % 2 != 0:
    #    print n
        return 1 + hailstone(3 * n + 1)
回复

使用道具 举报

🔗
rockleecsu 2016-1-20 13:18:45 | 只看该作者
全局:
交作业!!!


代码:
  1. # Q2
  2. def make_buzzer(n):
  3.     """ Returns a function that prints numbers in a specified
  4.     range except those divisible by n.

  5.     >>> i_hate_fives = make_buzzer(5)
  6.     >>> i_hate_fives(10)
  7.     Buzz!
  8.     1
  9.     2
  10.     3
  11.     4
  12.     Buzz!
  13.     6
  14.     7
  15.     8
  16.     9
  17.     """
  18.     "*** YOUR CODE HERE ***"
  19.     def ran(limit):
  20.             for i in range(limit):
  21.                     if i % n == 0:
  22.                             print("Buzz!")
  23.                     else:
  24.                             print(i)
  25.     return ran


  26. # Q4
  27. def f1():
  28.     """
  29.     >>> f1()
  30.     3
  31.     """
  32.     "*** YOUR CODE HERE ***"
  33.     return 3


  34. def f2():
  35.     """
  36.     >>> f2()()
  37.     3
  38.     """
  39.     "*** YOUR CODE HERE ***"
  40.     return lambda: 3


  41. def f3():
  42.     """
  43.     >>> f3()(3)
  44.     3
  45.     """
  46.     "*** YOUR CODE HERE ***"
  47.     return lambda x: x


  48. def f4():
  49.     """
  50.     >>> f4()()(3)()
  51.     3
  52.     """
  53.     "*** YOUR CODE HERE ***"
  54.     return lambda: lambda x: lambda: x


  55. # Q6
  56. def sum(n):
  57.     """Computes the sum of all integers between 1 and n, inclusive.
  58.     Assume n is positive.

  59.     >>> sum(1)
  60.     1
  61.     >>> sum(5)  # 1 + 2 + 3 + 4 + 5
  62.     15
  63.     """
  64.     "*** YOUR CODE HERE ***"
  65.     if n <= 1:
  66.             return n
  67.     return sum(n - 1) + n

  68. # Q7

  69. def sum_every_other_number(n):
  70.     """Return the sum of every other natural number
  71.     up to n, inclusive.

  72.     >>> sum_every_other_number(8)
  73.     20
  74.     >>> sum_every_other_number(9)
  75.     25
  76.     """
  77.     if n < 2:
  78.         return n
  79.     else:
  80.         return n + sum_every_other_number(n - 2)


  81. def fibonacci(n):
  82.     """Return the nth fibonacci number.
  83.    
  84.     >>> fibonacci(11)
  85.     89
  86.     """
  87.     if n == 0:
  88.         return 0
  89.     elif n == 1:
  90.         return 1
  91.     else:
  92.         return fibonacci(n - 1) + fibonacci(n - 2)


  93. # Q8
  94. def hailstone(n):
  95.     """Print out the hailstone sequence starting at n, and return the
  96.     number of elements in the sequence.

  97.     >>> a = hailstone(10)
  98.     10
  99.     5
  100.     16
  101.     8
  102.     4
  103.     2
  104.     1
  105.     >>> a
  106.     7
  107.     """
  108.     "*** YOUR CODE HERE ***"
  109.     print(n)
  110.     if n == 1:
  111.             return 1
  112.     elif n % 2 == 0:
  113.             return 1 + hailstone(n // 2)
  114.     else:
  115.             return 1 + hailstone(n * 3 + 1)
复制代码
  1. # Q9
  2. def cycle(f1, f2, f3):
  3.     """ Returns a function that is itself a higher order function
  4.     >>> def add1(x):
  5.     ...     return x + 1
  6.     >>> def times2(x):
  7.     ...     return x * 2
  8.     >>> def add3(x):
  9.     ...     return x + 3
  10.     >>> my_cycle = cycle(add1, times2, add3)
  11.     >>> identity = my_cycle(0)
  12.     >>> identity(5)
  13.     5
  14.     >>> add_one_then_double = my_cycle(2)
  15.     >>> add_one_then_double(1)
  16.     4
  17.     >>> do_all_functions = my_cycle(3)
  18.     >>> do_all_functions(2)
  19.     9
  20.     >>> do_more_than_a_cycle = my_cycle(4)
  21.     >>> do_more_than_a_cycle(2)
  22.     10
  23.     >>> do_two_cycles = my_cycle(6)
  24.     >>> do_two_cycles(1)
  25.     19
  26.     """
  27.     "*** YOUR CODE HERE ***"
  28.     def iteration(n):
  29.         def ret(x):
  30.             i = 0
  31.             while i < n:
  32.                 if i % 3 == 0:
  33.                     x = f1(x)
  34.                 elif i % 3 == 1:
  35.                     x = f2(x)
  36.                 else:
  37.                     x = f3(x)
  38.                 i += 1
  39.             return x
  40.         return ret
  41.     return iteration

  42. # Q10
  43. def lambda_curry2(func):
  44.     """
  45.     Returns a Curried version of a two argument function func.
  46.     >>> from operator import add
  47.     >>> x = lambda_curry2(add)
  48.     >>> y = x(3)
  49.     >>> y(5)
  50.     8
  51.     """
  52.     "*** YOUR CODE HERE ***"
  53.     return lambda x: lambda y: func(x, y)

  54. # Q12
  55. def paths(m, n):
  56.     """Return the number of paths from one corner of an
  57.     M by N grid to the opposite corner.

  58.     >>> paths(2, 2)
  59.     2
  60.     >>> paths(5, 7)
  61.     210
  62.     >>> paths(117, 1)
  63.     1
  64.     >>> paths(1, 157)
  65.     1
  66.     """
  67.     "*** YOUR CODE HERE ***"
  68.     if m == 1 or n == 1:
  69.         return 1
  70.     return paths(m - 1, n) + paths(m, n - 1)

  71. # Q13
  72. def gcd(a, b):
  73.     """Returns the greatest common divisor of a and b.
  74.     Should be implemented using recursion.

  75.     >>> gcd(34, 19)
  76.     1
  77.     >>> gcd(39, 91)
  78.     13
  79.     >>> gcd(20, 30)
  80.     10
  81.     >>> gcd(40, 40)
  82.     40
  83.     """
  84.     "*** YOUR CODE HERE ***"
  85.     if a < b:
  86.         a, b = b, a
  87.     if a % b == 0:
  88.         return b
  89.     else:
  90.         return gcd(b, a % b)
复制代码
回复

使用道具 举报

🔗
Liaeve 2016-2-12 14:50:41 | 只看该作者
全局:
lambda的用法始终不理解,Q4里面f1和f2的区别,f3和f4的区别,还有它们的怎么来的,搞不清楚
回复

使用道具 举报

🔗
Liaeve 2016-2-12 14:50:58 | 只看该作者
全局:
# Q2
def make_buzzer(n):
    """ Returns a function that prints numbers in a specified
    range except those divisible by n.

    >>> i_hate_fives = make_buzzer(5)
    >>> i_hate_fives(10)
    Buzz!
    1
    2
    3
    4
    Buzz!
    6
    7
    8
    9
    """
    "*** YOUR CODE HERE ***"
    def buzz(m):
        for i in range(0, m):
            if i % n == 0:
                print('Buzz!')
            else:
                print(i)
    return buzz

# Q4
def f1():
    """
    >>> f1()
    3
    """
    "*** YOUR CODE HERE ***"
    return 3

def f2():
    """
    >>> f2()()
    3
    """
    "*** YOUR CODE HERE ***"
    return lambda: 3

def f3():
    """
    >>> f3()(3)
    3
    """
    "*** YOUR CODE HERE ***"
    return lambda x: x

def f4():
    """
    >>> f4()()(3)()
    3
    """
    "*** YOUR CODE HERE ***"
    return lambda: lambda x: lambda: x

# Q6
def sum(n):
    """Computes the sum of all integers between 1 and n, inclusive.
    Assume n is positive.

    >>> sum(1)
    1
    >>> sum(5)  # 1 + 2 + 3 + 4 + 5
    15
    """
    "*** YOUR CODE HERE ***"
    if n == 0:
        total = 0
    else:
        total = sum(n-1) + n
    return total

# Q7

def sum_every_other_number(n):
    """Return the sum of every other natural number
    up to n, inclusive.

    >>> sum_every_other_number(8)
    20
    >>> sum_every_other_number(9)
    25
    """
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return n + sum_every_other_number(n - 2)


def fibonacci(n):
    """Return the nth fibonacci number.
   
    >>> fibonacci(11)
    89
    """
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fibonacci(n - 1) + fibonacci(n - 2)


# Q8
def hailstone(n):
    """Print out the hailstone sequence starting at n, and return the
    number of elements in the sequence.

    >>> a = hailstone(10)
    10
    5
    16
    8
    4
    2
    1
    >>> a
    7
    """
    "*** YOUR CODE HERE ***"
    print (n)
    if n == 1:
        return 1
    elif n % 2 == 0:
        return hailstone(n // 2) + 1
    else:
        return hailstone(n * 3 + 1) + 1

# Q9
def cycle(f1, f2, f3):
    """ Returns a function that is itself a higher order function
    >>> def add1(x):
    ...     return x + 1
    >>> def times2(x):
    ...     return x * 2
    >>> def add3(x):
    ...     return x + 3
    >>> my_cycle = cycle(add1, times2, add3)
    >>> identity = my_cycle(0)
    >>> identity(5)
    5
    >>> add_one_then_double = my_cycle(2)
    >>> add_one_then_double(1)
    4
    >>> do_all_functions = my_cycle(3)
    >>> do_all_functions(2)
    9
    >>> do_more_than_a_cycle = my_cycle(4)
    >>> do_more_than_a_cycle(2)
    10
    >>> do_two_cycles = my_cycle(6)
    >>> do_two_cycles(1)
    19
    """
    "*** YOUR CODE HERE ***"
    def fn(n):
        def ret(x):
            for i in range(0, n):
                if i % 3 == 0:
                    x = f1(x)
                elif i % 3 == 1:
                    x = f2(x)
                else:
                    x = f3(x)
            return x
        return ret
    return fn

# Q10
def lambda_curry2(func):
    """
    Returns a Curried version of a two argument function func.
    >>> from operator import add
    >>> x = lambda_curry2(add)
    >>> y = x(3)
    >>> y(5)
    8
    """
    "*** YOUR CODE HERE ***"
    return lambda arg1: lambda arg2: func(arg1, arg2)

# Q12
def paths(m, n):
    """Return the number of paths from one corner of an
    M by N grid to the opposite corner.

    >>> paths(2, 2)
    2
    >>> paths(5, 7)
    210
    >>> paths(117, 1)
    1
    >>> paths(1, 157)
    1
    """
    "*** YOUR CODE HERE ***"
    if m == 1 or n == 1:
        return 1
    else:
        return paths(m, n-1) + paths(m-1, n)

# Q13
def gcd(a, b):
    """Returns the greatest common divisor of a and b.
    Should be implemented using recursion.

    >>> gcd(34, 19)
    1
    >>> gcd(39, 91)
    13
    >>> gcd(20, 30)
    10
    >>> gcd(40, 40)
    40
    """
    "*** YOUR CODE HERE ***"
    p = max(a, b)
    q = min(a, b)
    if p % q == 0:
        return  q
    else:
        return gcd(q, p % q)
回复

使用道具 举报

🔗
wkh279 2016-11-19 11:21:43 | 只看该作者
全局:
lab03.py
  1. # Q2
  2. def make_buzzer(n):
  3.     """ Returns a function that prints numbers in a specified
  4.     range except those divisible by n.

  5.     >>> i_hate_fives = make_buzzer(5)
  6.     >>> i_hate_fives(10)
  7.     Buzz!
  8.     1
  9.     2
  10.     3
  11.     4
  12.     Buzz!
  13.     6
  14.     7
  15.     8
  16.     9
  17.     """
  18.     def buzz(m):
  19.         i = 0
  20.         while i < m:
  21.             if i % n == 0:
  22.                 print('Buzz!')
  23.             else:
  24.                 print(i)
  25.             i += 1
  26.     return buzz

  27. # Q4
  28. def f1():
  29.     """
  30.     >>> f1()
  31.     3
  32.     """
  33.     return 3

  34. def f2():
  35.     """
  36.     >>> f2()()
  37.     3
  38.     """
  39.     return lambda:3

  40. def f3():
  41.     """
  42.     >>> f3()(3)
  43.     3
  44.     """
  45.     return lambda x:x

  46. def f4():
  47.     """
  48.     >>> f4()()(3)()
  49.     3
  50.     """
  51.     return lambda: lambda x: lambda:x
  52. # Q6
  53. def sum(n):
  54.     """Computes the sum of all integers between 1 and n, inclusive.
  55.     Assume n is positive.

  56.     >>> sum(1)
  57.     1
  58.     >>> sum(5)  # 1 + 2 + 3 + 4 + 5
  59.     15
  60.     """
  61.     if n==1:
  62.         return 1
  63.     else:
  64.         return n+sum(n-1)

  65. # Q7

  66. def sum_every_other_number(n):
  67.     """Return the sum of every other natural number
  68.     up to n, inclusive.

  69.     >>> sum_every_other_number(8)
  70.     20
  71.     >>> sum_every_other_number(9)
  72.     25
  73.     """
  74.     if n == 0:
  75.         return 0
  76.     elif n ==1:
  77.         return 1
  78.     else:
  79.         return n + sum_every_other_number(n - 2)


  80. def fibonacci(n):
  81.     """Return the nth fibonacci number.
  82.    
  83.     >>> fibonacci(11)
  84.     89
  85.     """
  86.     if n == 0:
  87.         return 0
  88.     elif n == 1:
  89.         return 1
  90.     else:
  91.         return fibonacci(n - 1) + fibonacci(n - 2)


  92. # Q8
  93. def hailstone(n):
  94.     """Print out the hailstone sequence starting at n, and return the
  95.     number of elements in the sequence.

  96.     >>> a = hailstone(10)
  97.     10
  98.     5
  99.     16
  100.     8
  101.     4
  102.     2
  103.     1
  104.     >>> a
  105.     7
  106.     """
  107.     print(n)
  108.     if n==1:
  109.         return 1
  110.     elif n%2 == 0:
  111.         return 1+hailstone(n//2)
  112.     else:
  113.         return hailstone(3*n+1)+1
复制代码


lab03_extra.py
  1. # Q9
  2. def cycle(f1, f2, f3):
  3.     """ Returns a function that is itself a higher order function
  4.     >>> def add1(x):
  5.     ...     return x + 1
  6.     >>> def times2(x):
  7.     ...     return x * 2
  8.     >>> def add3(x):
  9.     ...     return x + 3
  10.     >>> my_cycle = cycle(add1, times2, add3)
  11.     >>> identity = my_cycle(0)
  12.     >>> identity(5)
  13.     5
  14.     >>> add_one_then_double = my_cycle(2)
  15.     >>> add_one_then_double(1)
  16.     4
  17.     >>> do_all_functions = my_cycle(3)
  18.     >>> do_all_functions(2)
  19.     9
  20.     >>> do_more_than_a_cycle = my_cycle(4)
  21.     >>> do_more_than_a_cycle(2)
  22.     10
  23.     >>> do_two_cycles = my_cycle(6)
  24.     >>> do_two_cycles(1)
  25.     19
  26.     """
  27.     def f(n):
  28.         if n==0:
  29.             return lambda x:x
  30.         if n %3==0:
  31.             return lambda x:f3(f2(f1(f(n-3)(x))))
  32.         elif n %3==1:
  33.             return lambda x:f1(f(n-1)(x))
  34.         else:
  35.             return lambda x:f2(f1(f(n-2)(x)))
  36.     return f

  37. # Q10
  38. def lambda_curry2(func):
  39.     """
  40.     Returns a Curried version of a two argument function func.
  41.     >>> from operator import add
  42.     >>> x = lambda_curry2(add)
  43.     >>> y = x(3)
  44.     >>> y(5)
  45.     8
  46.     """
  47.     return lambda x: lambda y: func(x,y)

  48. # Q12
  49. def paths(m, n):
  50.     """Return the number of paths from one corner of an
  51.     M by N grid to the opposite corner.

  52.     >>> paths(2, 2)
  53.     2
  54.     >>> paths(5, 7)
  55.     210
  56.     >>> paths(117, 1)
  57.     1
  58.     >>> paths(1, 157)
  59.     1
  60.     """
  61.     if m==1 or n==1:
  62.         return 1
  63.     else:
  64.         return paths(m-1,n)+paths(m,n-1)

  65. # Q13
  66. def gcd(a, b):
  67.     """Returns the greatest common divisor of a and b.
  68.     Should be implemented using recursion.

  69.     >>> gcd(34, 19)
  70.     1
  71.     >>> gcd(39, 91)
  72.     13
  73.     >>> gcd(20, 30)
  74.     10
  75.     >>> gcd(40, 40)
  76.     40
  77.     """
  78.     x,y=min(a,b),max(a,b)
  79.     if y%x==0:
  80.         return x
  81.     else:
  82.         return gcd(x,y%x)
复制代码
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

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