[CS61A]Homework 3

作业连接http://gaotx.com/cs61a/hw/hw03/

交作业了，代码在此：

HW_SOURCE_FILE = 'hw03.py'

#############
# Questions #
#############

def has_seven(k):
    """Returns True if at least one of the digits of k is a 7, False otherwise.

    >>> has_seven(3)
    False
    >>> has_seven(7)
    True
    >>> has_seven(2734)
    True
    >>> has_seven(2634)
    False
    >>> has_seven(734)
    True
    >>> has_seven(7777)
    True
    >>> from construct_check import check
    >>> check(HW_SOURCE_FILE, 'has_seven',
    ...       ['Assign', 'AugAssign'])
    True
    """
    if k%10 == 7:
        return True
    elif k<10:
        return False
    else:
        return has_seven(k//10)

def summation(n, term):

    """Return the sum of the first n terms in the sequence defined by term.
    Implement using recursion!

    >>> summation(5, lambda x: x * x * x) # 1^3 + 2^3 + 3^3 + 4^3 + 5^3
    225
    >>> summation(9, lambda x: x + 1) # 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10
    54
    >>> summation(5, lambda x: 2**x) # 2^1 + 2^2 + 2^3 + 2^4 + 2^5
    62
    >>> # Do not use while/for loops!
    >>> from construct_check import check
    >>> check(HW_SOURCE_FILE, 'summation',
    ...       ['While', 'For'])
    True
    """
    assert n >= 1
    "*** YOUR CODE HERE ***"
    if n == 1:
        return term(n)
    else:
        return summation(n-1, term) + term(n)

def square(x):
    return x * x

def identity(x):
    return x

triple = lambda x: 3 * x

increment = lambda x: x + 1

add = lambda x, y: x + y

mul = lambda x, y: x * y

def accumulate(combiner, base, n, term):
    """Return the result of combining the first n terms in a sequence and base.
    The terms to be combined are term(1), term(2), ..., term(n).  combiner is a
    two-argument commutative function.

    >>> accumulate(add, 0, 5, identity)  # 0 + 1 + 2 + 3 + 4 + 5
    15
    >>> accumulate(add, 11, 5, identity) # 11 + 1 + 2 + 3 + 4 + 5
    26
    >>> accumulate(add, 11, 0, identity) # 11
    11
    >>> accumulate(add, 11, 3, square)   # 11 + 1^2 + 2^2 + 3^2
    25
    >>> accumulate(mul, 2, 3, square)   # 2 * 1^2 * 2^2 * 3^2
    72
    """
    "*** YOUR CODE HERE ***"

    if n == 0:
        return combiner(base, 0)

    elif n == 1:
        return combiner(base, term(1))

    else:
        return combiner(accumulate(combiner, base, n-1, term), term(n))



def summation_using_accumulate(n, term):
    """Returns the sum of term(1) + ... + term(n). The implementation
    uses accumulate.

    >>> summation_using_accumulate(5, square)
    55
    >>> summation_using_accumulate(5, triple)
    45
    >>> from construct_check import check
    >>> check(HW_SOURCE_FILE, 'summation_using_accumulate',
    ...       ['Recursion', 'For', 'While'])
    True
    """
    "*** YOUR CODE HERE ***"
    return accumulate(add, 0, n, term)

def product_using_accumulate(n, term):
    """An implementation of product using accumulate.

    >>> product_using_accumulate(4, square)
    576
    >>> product_using_accumulate(6, triple)
    524880
    >>> from construct_check import check
    >>> check(HW_SOURCE_FILE, 'product_using_accumulate',
    ...       ['Recursion', 'For', 'While'])
    True
    """
    "*** YOUR CODE HERE ***"
    return accumulate(mul,1, n, term)

def filtered_accumulate(combiner, base, pred, n, term):
    """Return the result of combining the terms in a sequence of N terms
    that satisfy the predicate pred. combiner is a two-argument function.
    If v1, v2, ..., vk are the values in term(1), term(2), ..., term(N)
    that satisfy pred, then the result is
         base combiner v1 combiner v2 ... combiner vk
    (treating combiner as if it were a binary operator, like +). The
    implementation uses accumulate.

    >>> filtered_accumulate(add, 0, lambda x: True, 5, identity)  # 0 + 1 + 2 + 3 + 4 + 5
    15
    >>> filtered_accumulate(add, 11, lambda x: False, 5, identity) # 11
    11
    >>> filtered_accumulate(add, 0, odd, 5, identity)   # 0 + 1 + 3 + 5
    9
    >>> filtered_accumulate(mul, 1, greater_than_5, 5, square)  # 1 * 9 * 16 * 25
    3600
    >>> # Do not use while/for loops or recursion
    >>> from construct_check import check
    >>> check(HW_SOURCE_FILE, 'filtered_accumulate',
    ...       ['While', 'For', 'Recursion'])
    True
    """
    def combine_if(x, y):

        "*** YOUR CODE HERE ***"
        if pred(y) == True:
            return combiner(x, y)
        else:
            return x

    return accumulate(combine_if, base, n, term)

def odd(x):
    return x % 2 == 1

def greater_than_5(x):
    return x > 5

def make_repeater(f, n):
    """Return the function that computes the nth application of f.

    >>> add_three = make_repeater(increment, 3)
    >>> add_three(5)
    8
    >>> make_repeater(triple, 5)(1) # 3 * 3 * 3 * 3 * 3 * 1
    243
    >>> make_repeater(square, 2)(5) # square(square(5))
    625
    >>> make_repeater(square, 4)(5) # square(square(square(square(5))))
    152587890625
    >>> make_repeater(square, 0)(5)
    5
    """
    "*** YOUR CODE HERE ***"
    def h(x):
        k = 0
        while k < n:
            x, k = f(x), k + 1
        return x
    return h     

def compose1(f, g):
    """Return a function h, such that h(x) = f(g(x))."""
    def h(x):
        return f(g(x))
    return h

###################
# Extra Questions #
###################

quine = """
"*** YOUR CODE HERE ***"
"""

def zero(f):
    return lambda x: x

def successor(n):
    return lambda f: lambda x: f(n(f)(x))

def one(f):
    """Church numeral 1: same as successor(zero)"""
    "*** YOUR CODE HERE ***"

def two(f):
    """Church numeral 2: same as successor(successor(zero))"""
    "*** YOUR CODE HERE ***"

three = successor(two)

def church_to_int(n):
    """Convert the Church numeral n to a Python integer.

    >>> church_to_int(zero)
    0
    >>> church_to_int(one)
    1
    >>> church_to_int(two)
    2
    >>> church_to_int(three)
    3
    """
    "*** YOUR CODE HERE ***"

def add_church(m, n):
    """Return the Church numeral for m + n, for Church numerals m and n.

    >>> church_to_int(add_church(two, three))
    5
    """
    "*** YOUR CODE HERE ***"

def mul_church(m, n):
    """Return the Church numeral for m * n, for Church numerals m and n.

    >>> four = successor(three)
    >>> church_to_int(mul_church(two, three))
    6
    >>> church_to_int(mul_church(three, four))
    12
    """
    "*** YOUR CODE HERE ***"

def pow_church(m, n):
    """Return the Church numeral m ** n, for Church numerals m and n.

    >>> church_to_int(pow_church(two, three))
    8
    >>> church_to_int(pow_church(three, two))
    9
    """
    "*** YOUR CODE HERE ***"

不愧是Berkeley，感觉一年级的第一门课难度就相当恐怖阿。。。。。我也学过好几门CS/CE课了，但是依然觉得作业有些难度，pingpong那题做了好久，count_change想不到好方法，就直接省事用DP做了，最后一个challenge是看了答案才理解的。。感觉lambda表达式确实学的一般。。。不过赶进度就不深究了，如果完全按照伯克利学生的标准，我的智商也不够。。
完成截图：

代码：

1. def g(n):
   
2.         """Return the value of G(n), computed recursively.
   
3. 
   
4.         >>> g(1)
   
5.         1
   
6.         >>> g(2)
   
7.         2
   
8.         >>> g(3)
   
9.         3
   
10.         >>> g(4)
    
11.         10
    
12.         >>> g(5)
    
13.         22
    
14.         """
    
15.         "*** YOUR CODE HERE ***"
    
16.         if n <= 3:
    
17.                 return n
    
18.         return g(n-1) + 2 * g(n-2) + 3 * g(n-3)
    
19. 
    
20. def g_iter(n):
    
21.         """Return the value of G(n), computed iteratively.
    
22. 
    
23.         >>> g_iter(1)
    
24.         1
    
25.         >>> g_iter(2)
    
26.         2
    
27.         >>> g_iter(3)
    
28.         3
    
29.         >>> g_iter(4)
    
30.         10
    
31.         >>> g_iter(5)
    
32.         22
    
33.         """
    
34.         "*** YOUR CODE HERE ***"
    
35.         g_list = (n + 1) * [0]
    
36.         for i in range(n + 1):
    
37.                 if i <= 3:
    
38.                         g_list[i] = i
    
39.                 else:
    
40.                         g_list[i] = g_list[i-1] + 2 * g_list[i-2] + 3 * g_list[i-3]
    
41.         return g_list[n]
    
42. 
    
43. 
    
44. def has_seven(k):
    
45.         """Returns True if at least one of the digits of k is a 7, False otherwise.
    
46. 
    
47.         >>> has_seven(3)
    
48.         False
    
49.         >>> has_seven(7)
    
50.         True
    
51.         >>> has_seven(2734)
    
52.         True
    
53.         >>> has_seven(2634)
    
54.         False
    
55.         >>> has_seven(734)
    
56.         True
    
57.         >>> has_seven(7777)
    
58.         True
    
59.         """
    
60.         "*** YOUR CODE HERE ***"
    
61.         if k % 10 == 7:
    
62.                 return True
    
63.         if k < 10:
    
64.                 return False
    
65.         return has_seven(k // 10)
    
66. 
    
67. 
    
68. def pingpong(n):
    
69.         """Return the nth element of the ping-pong sequence.
    
70. 
    
71.         >>> pingpong(7)
    
72.         7
    
73.         >>> pingpong(8)
    
74.         6
    
75.         >>> pingpong(15)
    
76.         1
    
77.         >>> pingpong(21)
    
78.         -1
    
79.         >>> pingpong(22)
    
80.         0
    
81.         >>> pingpong(30)
    
82.         6
    
83.         >>> pingpong(68)
    
84.         2
    
85.         >>> pingpong(69)
    
86.         1
    
87.         >>> pingpong(70)
    
88.         0
    
89.         >>> pingpong(71)
    
90.         1
    
91.         >>> pingpong(72)
    
92.         0
    
93.         >>> pingpong(100)
    
94.         2
    
95.         """
    
96.         "*** YOUR CODE HERE ***"
    
97.         def helper(k, increament, tmp):
    
98.                 if k == n:
    
99.                         return tmp
    
100. #                print("test", n, increament)
     
101.                 if k % 7 == 0 or has_seven(k):
     
102.                         increament = -increament
     
103.                 return helper(k+1, increament, tmp+increament)
     
104. 
     
105.         return helper(1, 1, 1)
     
106. 
     
107. 
     
108. def count_change(amount):
     
109.         """Return the number of ways to make change for amount.
     
110. 
     
111.         >>> count_change(7)
     
112.         6
     
113.         >>> count_change(10)
     
114.         14
     
115.         >>> count_change(20)
     
116.         60
     
117.         >>> count_change(100)
     
118.         9828
     
119.         """
     
120.         "*** YOUR CODE HERE ***"
     
121.         arr = []
     
122.         i = 1
     
123.         while i <= amount:
     
124.                 arr.append(i)
     
125.                 i *= 2
     
126. 
     
127.         res = (amount + 1) * [0]
     
128.         res[0] = 1
     
129. 
     
130.         for i in range(len(arr)):
     
131.                 for j in range(arr[i], amount + 1):
     
132.                         res[j] = res[j] + res[j-arr[i]]                # sum arr[i] and including a[[i]]
     
133. 
     
134.         return res[amount]
     
135.        
     
136. 
     
137. def towers_of_hanoi(n, start, end):
     
138.         """Print the moves required to solve the towers of hanoi game, starting
     
139.         with n disks on the start pole and finishing on the end pole.
     
140. 
     
141.         The game is to assumed to have 3 poles.
     
142. 
     
143.         >>> towers_of_hanoi(1, 1, 3)
     
144.         Move the top disk from rod 1 to rod 3
     
145.         >>> towers_of_hanoi(2, 1, 3)
     
146.         Move the top disk from rod 1 to rod 2
     
147.         Move the top disk from rod 1 to rod 3
     
148.         Move the top disk from rod 2 to rod 3
     
149.         >>> towers_of_hanoi(3, 1, 3)
     
150.         Move the top disk from rod 1 to rod 3
     
151.         Move the top disk from rod 1 to rod 2
     
152.         Move the top disk from rod 3 to rod 2
     
153.         Move the top disk from rod 1 to rod 3
     
154.         Move the top disk from rod 2 to rod 1
     
155.         Move the top disk from rod 2 to rod 3
     
156.         Move the top disk from rod 1 to rod 3
     
157.         """
     
158.         assert 0 < start <= 3 and 0 < end <= 3 and start != end, "Bad start/end"
     
159.         "*** YOUR CODE HERE ***"
     
160.         def helper(n, start, end, empty):
     
161.                 if n == 1:
     
162.                         print("Move the top disk from rod %d to rod %d" % (start, end))
     
163.                         return
     
164.                 helper(n-1, start, empty, end)
     
165.                 helper(1, start, end, empty)
     
166.                 helper(n-1, empty, end, start)
     
167. 
     
168.         return helper(n, start, end, 6 - start - end)
     
169. 
     
170. 
     
171. from operator import sub, mul
     
172. 
     
173. def make_anonymous_factorial():
     
174.         """Return the value of an expression that computes factorial.
     
175. 
     
176.         >>> make_anonymous_factorial()(5)
     
177.         120
     
178.         """
     
179.         return lambda n: (lambda f, v: f(f, v))(lambda f, v: 1 if v == 1 else mul(v, f(f, sub(v, 1))), n)

复制代码

这次作业还是挺有难度的。pingpong那题想了我半天，hanoi写出来不难，把游戏规则想清楚也花了好久哈哈，看了群友写的代码之后发现确实还可以改进！上代码：
#hw03
#Q1
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 ***"
    if n <= 3:
        return n
    if n >= 4:
        return g(n-1) + (2 * g(n-2)) + (3 * g(n-3))
        
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 ***"
    if n <= 3:
        return
    a , b, c = 1, 2, 3
    if n >= 4:
        while n > 3:
            a, b, c = b, c, c + 2*b + 3*a
            n = n - 1
        return c
        
#Q2
def has_seven(k):
    """Returns True if at least one of the digits of k is a 7, False otherwise.

    >>> has_seven(3)
    False
    >>> has_seven(7)
    True
    >>> has_seven(2734)
    True
    >>> has_seven(2634)
    False
    >>> has_seven(734)
    True
    >>> has_seven(7777)
    True
    """
    "*** YOUR CODE HERE ***"
    if k // 10 == 0:
        if k % 10 == 7:
            return True
        if k % 10 != 7:
            return False
    if k % 10 == 7:
        return True
    if k % 10 != 7:
        return has_seven(k//10)
        
#Q3
def pingpong(n):
    """Return the nth element of the ping-pong sequence.

    >>> pingpong(7)
    7
    >>> pingpong(8)
    6
    >>> pingpong(15)
    1
    >>> pingpong(21)
    -1
    >>> pingpong(22)
    0
    >>> pingpong(30)
    6
    >>> pingpong(68)
    2
    >>> pingpong(69)
    1
    >>> pingpong(70)
    0
    >>> pingpong(71)
    1
    >>> pingpong(72)
    0
    >>> pingpong(100)
    2
    """
    def pingpong_next(k, p, up):
        if k == n:
            return p
        if up:
            return pingpong_switch(k+1, p+1, up)
        else:
            return pingpong_switch(k+1, p-1, up)

    def pingpong_switch(k, p, up):
        if k % 7 == 0 or has_seven(k):
            return pingpong_next(k, p, not up)
        else:
            return pingpong_next(k, p, up)

    return pingpong_next(1, 1, True)
   
#Q4
def count_change(amount):
    """Return the number of ways to make change for amount.

    >>> count_change(7)
    6
    >>> count_change(10)
    14
    >>> count_change(20)
    60
    >>> count_change(100)
    9828
    """
    "*** YOUR CODE HERE ***"
    return count_min(1, amount)
   
def count_min(n,m):
    if n == m:
        return 1
    if n > m:
        return 0
    if m == 0:
        return 0
    else:
        with_min = count_min(n, m-n)
        without_min = count_min(2*n, m)
        return with_min + without_min   

#Q5
def towers_of_hanoi(n, start, end):
    """Print the moves required to solve the towers of hanoi game, starting
    with n disks on the start pole and finishing on the end pole.

    The game is to assumed to have 3 poles.

    >>> towers_of_hanoi(1, 1, 3)
    Move the top disk from rod 1 to rod 3
    >>> towers_of_hanoi(2, 1, 3)
    Move the top disk from rod 1 to rod 2
    Move the top disk from rod 1 to rod 3
    Move the top disk from rod 2 to rod 3
    >>> towers_of_hanoi(3, 1, 3)
    Move the top disk from rod 1 to rod 3
    Move the top disk from rod 1 to rod 2
    Move the top disk from rod 3 to rod 2
    Move the top disk from rod 1 to rod 3
    Move the top disk from rod 2 to rod 1
    Move the top disk from rod 2 to rod 3
    Move the top disk from rod 1 to rod 3
    """
    assert 0 < start <= 3 and 0 < end <= 3 and start != end, "Bad start/end"
    "*** YOUR CODE HERE ***"
    if n == 1:
        print "Move the top disk from rod " + str(start) + " to rod " + str(end)
    else:
        index =  start + end
        if index == 3:
            index = 3
        if index == 4:
            index = 2
        if index == 5:
            index = 1
        towers_of_hanoi(n-1, start, index)
        towers_of_hanoi(1, start, end)
        towers_of_hanoi(n-1, index, end)

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
    """
    if n <= 3:
        return n
    else:
        return g(n-1) + 2*g(n-2) +3*g(n-3)
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
    """
    if n <= 3:
        return n
    else:
        first = 1
        second = 2
        third = 3
        for i in range(3, n):
            result = third + 2*second +3*first
            first = second
            second = third
            third = result
        return result


def has_seven(k):
    """Returns True if at least one of the digits of k is a 7, False otherwise.

    >>> has_seven(3)
    False
    >>> has_seven(7)
    True
    >>> has_seven(2734)
    True
    >>> has_seven(2634)
    False
    >>> has_seven(734)
    True
    >>> has_seven(7777)
    True
    """
    if k == 0:
        return False
    if k%10 == 7:
        return True
    else:
        return has_seven(k//10)

def pingpong(n):
    """Return the nth element of the ping-pong sequence.

    >>> pingpong(7)
    7
    >>> pingpong(8)
    6
    >>> pingpong(15)
    1
    >>> pingpong(21)
    -1
    >>> pingpong(22)
    0
    >>> pingpong(30)
    6
    >>> pingpong(68)
    2
    >>> pingpong(69)
    1
    >>> pingpong(70)
    0
    >>> pingpong(71)
    1
    >>> pingpong(72)
    0
    >>> pingpong(100)
    2
    """
   
    if n <= 2:
        return n
    else:
        if (n-1)%7 == 0 or has_seven(n-1):
            return pingpong(n-2)
        else:
            return pingpong(n-1)*2 - pingpong(n-2)
   


def count_change(amount):
    """Return the number of ways to make change for amount.

    >>> count_change(7)
    6
    >>> count_change(10)
    14
    >>> count_change(20)
    60
    >>> count_change(100)
    9828
    """
    return count_using(1, amount)

def count_using(min_coin, amount):
    if amount < 0:
        return 0
    elif amount == 0:
        return 1
    elif min_coin > amount:
        return 0
    else:
        with_min = count_using(min_coin, amount - min_coin)
        without_min = count_using(2*min_coin, amount)
        return with_min + without_min

def towers_of_hanoi(n, start, end):
    """Print the moves required to solve the towers of hanoi game, starting
    with n disks on the start pole and finishing on the end pole.

    The game is to assumed to have 3 poles.

    >>> towers_of_hanoi(1, 1, 3)
    Move the top disk from rod 1 to rod 3
    >>> towers_of_hanoi(2, 1, 3)
    Move the top disk from rod 1 to rod 2
    Move the top disk from rod 1 to rod 3
    Move the top disk from rod 2 to rod 3
    >>> towers_of_hanoi(3, 1, 3)
    Move the top disk from rod 1 to rod 3
    Move the top disk from rod 1 to rod 2
    Move the top disk from rod 3 to rod 2
    Move the top disk from rod 1 to rod 3
    Move the top disk from rod 2 to rod 1
    Move the top disk from rod 2 to rod 3
    Move the top disk from rod 1 to rod 3
    """
    assert 0 < start <= 3 and 0 < end <= 3 and start != end, "Bad start/end"
    if n == 1:
        print('Move the top disk from rod', start, 'to rod', end)
    else:
        towers_of_hanoi(n-1, start, 6-start-end)
        print('Move the top disk from rod', start, 'to rod', end)
        towers_of_hanoi(n-1, 6-start-end, end)

from operator import sub, mul

def make_anonymous_factorial():
    """Return the value of an expression that computes factorial.

    >>> make_anonymous_factorial()(5)
    120
    """
    return lambda x : 1 if x == 1 else x*make_anonymous_factorial()(x-1)

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 ***"
    if n <= 3:
        return n
    else:
        return g(n-1) + 2 * g(n-2) + 3* g(n-3)

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 ***"
    i = 4
    while n < 4:
        return n
    pre_one, pre_two, pre_three = 3, 2, 1
    while n >= 4 and i <= n:
        g = pre_one + 2 * pre_two + 3 * pre_three
        pre_one, pre_two, pre_three = g, pre_one, pre_two
        i += 1
    return g
        pass


def has_seven(k):
    """Returns True if at least one of the digits of k is a 7, False otherwise.

    >>> has_seven(3)
    False
    >>> has_seven(7)
    True
    >>> has_seven(2734)
    True
    >>> has_seven(2634)
    False
    >>> has_seven(734)
    True
    >>> has_seven(7777)
    True
    """
    "*** YOUR CODE HERE ***"
    if k % 10 == 7:
        return True
    elif k % 10 != 7 and k // 10 ==0:
        return False
    else:
        return has_seven(k // 10)



def pingpong(n):
    """Return the nth element of the ping-pong sequence.

    >>> pingpong(7)
    7
    >>> pingpong(8)
    6
    >>> pingpong(15)
    1
    >>> pingpong(21)
    -1
    >>> pingpong(22)
    0
    >>> pingpong(30)
    6
    >>> pingpong(68)
    2
    >>> pingpong(69)
    1
    >>> pingpong(70)
    0
    >>> pingpong(71)
    1
    >>> pingpong(72)
    0
    >>> pingpong(100)
    2
    """
    "*** YOUR CODE HERE ***"
    def pingpong_next(k, p, up):
        if k == n:
            return p
        if up:
            return pingpong_switch(k+1, p+1, up)
        else:
            return pingpong_switch(k+1, p-1, up)

    def pingpong_switch(k, p, up):
        if k % 7 == 0 or has_seven(k):
            return pingpong_next(k, p, not up)
        else:
            return pingpong_next(k, p, up)

    return pingpong_next(1, 1, True)



def count_change(amount):
    """Return the number of ways to make change for amount.

    >>> count_change(7)
    6
    >>> count_change(10)
    14
    >>> count_change(20)
    60
    >>> count_change(100)
    9828
    """
    "*** YOUR CODE HERE ***"
    def count_using(min_coin, amount):
    if amount < 0:
        return 0
    elif amount == 0:
        return 1
    elif min_coin > amount:
        return 0
    else:
        with_min = count_using(min_coin, amount - min_coin)
        without_min = count_using(2*min_coin, amount)
        return with_min + without_min


def towers_of_hanoi(n, start, end):
    """Print the moves required to solve the towers of hanoi game, starting
    with n disks on the start pole and finishing on the end pole.

    The game is to assumed to have 3 poles.

    >>> towers_of_hanoi(1, 1, 3)
    Move the top disk from rod 1 to rod 3
    >>> towers_of_hanoi(2, 1, 3)
    Move the top disk from rod 1 to rod 2
    Move the top disk from rod 1 to rod 3
    Move the top disk from rod 2 to rod 3
    >>> towers_of_hanoi(3, 1, 3)
    Move the top disk from rod 1 to rod 3
    Move the top disk from rod 1 to rod 2
    Move the top disk from rod 3 to rod 2
    Move the top disk from rod 1 to rod 3
    Move the top disk from rod 2 to rod 1
    Move the top disk from rod 2 to rod 3
    Move the top disk from rod 1 to rod 3
    """
    assert 0 < start <= 3 and 0 < end <= 3 and start != end, "Bad start/end"
    "*** YOUR CODE HERE ***"
    if n == 1:
        print('Move the top of disk from rod ', start, 'to rod', end)
    else:
        mid = 6 - start - end
        towers_of_hanoi(n-1, start, mid)
        print('Move the top of disk from rod ', start, 'to rod', end)
        towers_of_hanoi(n-1, mid, end)

感觉作业好难。。。。
找个时间找同学一起讨论一下=。= 先交了

""""
def g(n):
    if n in (1, 2, 3):
        return n
    return g(n-1) + 2*g(n-2) + 3*g(n-3)

def g_iter(n):
    if n == 1 or n == 2 or n == 3:
        return n
    a, b, c = 1, 2, 3
    while n > 3:
        a, b, c = b, c, c + 2*b + 3*a
        n = n - 1
    return c
"""""
""""
def has_seven(k):
    if k % 10 == 7:
        return True
    elif k < 10:
        return False
    else:
        return has_seven(k // 10)

"""""
""""
def pingpong(n):
    def pingpong_next(k, p, up):
        if k == n:
            return p
        if up:
            return pingpong_switch(k+1, p+1, up)
        else:
            return pingpong_switch(k+1, p-1, up)

    def pingpong_switch(k, p, up):
        if k % 7 == 0 or has_seven(k):
            return pingpong_next(k, p, not up)
        else:
            return pingpong_next(k, p, up)

    return pingpong_next(1, 1, True)
    """""
""""
def count_change(amount):
    return count_using(1, amount)

def count_using(min_coin, amount):
    if amount < 0:
        return 0
    elif amount == 0:
        return 1
    elif min_coin > amount:
        return 0
    else:
        with_min = count_using(min_coin, amount - min_coin)
        without_min = count_using(2*min_coin, amount)
        return with_min + without_min
"""""
""""
def towers_of_hanoi(n, start, end):
    assert 0 < start <= 3 and 0 < end <= 3 and start != end, "Bad start/end"
    if n == 1:
        print("Move the top disk from rod", start, "to rod", end)
    else:
        other = 6 - start - end
        towers_of_hanoi(n-1, start, other)
        towers_of_hanoi(1, start, end)
        towers_of_hanoi(n-1, other, end)
        """""

Q1：
def g(n):
        if n<=3:
                return n
        else:
                return g(n-1)+2*g(n-2)+3*g(n-3)

def g_iter(n):
        if n<=3:
                return n
        a,b,c=1,2,3
        while(n>3):
                a,b,c=b,c,c+2*b+3*a
                n-=1
        return c


Q2：
def has_seven(k):
        if k%10==7:
                return True
        elif k<=10:
                return False
        else:
                return has_seven(k//10)
Q3：

def has_seven(k):
        if k%10==7:
                return True
        elif k<=10:
                return False
        else:
                return has_seven(k//10)


def pingpong(n):
        if n<=7:
                return n
        elif (n-1)%7==0 or has_seven(n-1):
                return pingpong(n-2)
        else:
                return 2*pingpong(n-1)- pingpong(n-2)

Q4:

def count_change(amount):
    """Return the number of ways to make change for amount.

    >>> count_change(7)
    6
    >>> count_change(10)
    14
    >>> count_change(20)
    60
    >>> count_change(100)
    9828
    """
    return count_using(1, amount)

def count_using(min_coin,amount):
        if amount < 0:
                return 0
        elif amount == 0:
                return 1
        elif min_coin>amount:
                return 0
        else:
                with_min = count_using(min_coin,amount - min_coin)
                without_min= count_using(2*min_coin, amount)
                return with_min + without_min

Q5:
def towers_of_hanoi(n, start, end):
    """Print the moves required to solve the towers of hanoi game, starting
    with n disks on the start pole and finishing on the end pole.

    The game is to assumed to have 3 poles.

    >>> towers_of_hanoi(1, 1, 3)
    Move the top disk from rod 1 to rod 3
    >>> towers_of_hanoi(2, 1, 3)
    Move the top disk from rod 1 to rod 2
    Move the top disk from rod 1 to rod 3
    Move the top disk from rod 2 to rod 3
    >>> towers_of_hanoi(3, 1, 3)
    Move the top disk from rod 1 to rod 3
    Move the top disk from rod 1 to rod 2
    Move the top disk from rod 3 to rod 2
    Move the top disk from rod 1 to rod 3
    Move the top disk from rod 2 to rod 1
    Move the top disk from rod 2 to rod 3
    Move the top disk from rod 1 to rod 3
    """
    assert 0 < start <= 3 and 0 < end <= 3 and start != end, "Bad start/end"
    if n == 1:
        print('Move the top disk from rod', start, 'to rod', end)
    else:
        towers_of_hanoi(n-1, start, 6-start-end)
        print('Move the top disk from rod', start, 'to rod', end)
        towers_of_hanoi(n-1, 6-start-end, end)


越来越难了。。。。

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 ***"
    if n<=3:
        return n
    else:
        return g(n-1)+2*g(n-2)+3*g(n-3)

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 ***"
    i =1
    g_1,g_2,g_3 = 1,2,3
    while i<n:
        if i<=3:
            g= i
        else:
            g = g_3+2*g_2+3*g_3
            g_3,g_2,g_1 = g, g_3,g_2
        i+=1
    return g


def has_seven(k):
    """Returns True if at least one of the digits of k is a 7, False otherwise.

    >>> has_seven(3)
    False
    >>> has_seven(7)
    True
    >>> has_seven(2734)
    True
    >>> has_seven(2634)
    False
    >>> has_seven(734)
    True
    >>> has_seven(7777)
    True
    """
    "*** YOUR CODE HERE ***"
    if k>0:
        if k%10==7:
            return True
        else:
            return False or has_seven(k//10)
    else:
        return False


def pingpong(n):
    """Return the nth element of the ping-pong sequence.

    >>> pingpong(7)
    7
    >>> pingpong(8)
    6
    >>> pingpong(15)
    1
    >>> pingpong(21)
    -1
    >>> pingpong(22)
    0
    >>> pingpong(30)
    6
    >>> pingpong(68)
    2
    >>> pingpong(69)
    1
    >>> pingpong(70)
    0
    >>> pingpong(71)
    1
    >>> pingpong(72)
    0
    >>> pingpong(100)
    2
    """
    "*** YOUR CODE HERE ***"
    if n==1 or n==2:
        return n
    elif (n-1)%7==0 or has_seven(n-1):
        return pingpong(n-2)
    else:
        return 2*pingpong(n-1)-pingpong(n-2)


def count_change(amount):
    """Return the number of ways to make change for amount.

    >>> count_change(7)
    6
    >>> count_change(10)
    14
    >>> count_change(20)
    60
    >>> count_change(100)
    9828
    """
    "*** YOUR CODE HERE ***"
    maxc =1
    while maxc*2<=amount:
        maxc*=2
    def count_u(amount,max_coin):
        if max_coin==1:
            return 1
        if max_coin>amount:
            return count_change(amount)
        with_max = count_u(amount-max_coin,max_coin)
        without_max = count_u(amount,max_coin/2)
        return with_max+without_max
    return count_u(amount,maxc)

def towers_of_hanoi(n, start, end):
    """Print the moves required to solve the towers of hanoi game, starting
    with n disks on the start pole and finishing on the end pole.

    The game is to assumed to have 3 poles.

    >>> towers_of_hanoi(1, 1, 3)
    Move the top disk from rod 1 to rod 3
    >>> towers_of_hanoi(2, 1, 3)
    Move the top disk from rod 1 to rod 2
    Move the top disk from rod 1 to rod 3
    Move the top disk from rod 2 to rod 3
    >>> towers_of_hanoi(3, 1, 3)
    Move the top disk from rod 1 to rod 3
    Move the top disk from rod 1 to rod 2
    Move the top disk from rod 3 to rod 2
    Move the top disk from rod 1 to rod 3
    Move the top disk from rod 2 to rod 1
    Move the top disk from rod 2 to rod 3
    Move the top disk from rod 1 to rod 3
    """
    assert 0 < start <= 3 and 0 < end <= 3 and start != end, "Bad start/end"
    "*** YOUR CODE HERE ***"
    if n==1:
        print("Move the top disk from rod",start,"to rod",end)
    else:
        other = 6-start-end
        towers_of_hanoi(n-1,start,other)
        towers_of_hanoi(1,start,end)
        towers_of_hanoi(n-1,other,end)

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
    """
    if n <= 3 :
        return n
    else :
        return g(n-1) + 2* g(n-2) + 3 * g(n-3)
        
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
    """
    if n <= 3:
        return n
    else:
        i = 2
        pre, curr, next = 1, 2, 3
        while i < n :
            pre, curr, next = curr, next, next + 2*curr + 3*pre
            i += 1
        return curr        

def has_seven(k):
    """Returns True if at least one of the digits of k is a 7, False otherwise.

    >>> has_seven(3)
    False
    >>> has_seven(7)
    True
    >>> has_seven(2734)
    True
    >>> has_seven(2634)
    False
    >>> has_seven(734)
    True
    >>> has_seven(7777)
    True
    """
    if k==7 :
        return True
    elif k % 10 == 7 :
        return True
    elif k > 10:
        return has_seven(k // 10)
    return False

def pingpong(n):
    """Return the nth element of the ping-pong sequence.

    >>> pingpong(7)
    7
    >>> pingpong(8)
    6
    >>> pingpong(15)
    1
    >>> pingpong(21)
    -1
    >>> pingpong(22)
    0
    >>> pingpong(30)
    6
    >>> pingpong(68)
    2
    >>> pingpong(69)
    1
    >>> pingpong(70)
    0
    >>> pingpong(71)
    1
    >>> pingpong(72)
    0
    >>> pingpong(100)
    2
    """
    def up(k,i):
        k, i = k + 1, i + 1
        if i % 7== 0 or has_seven(i):
            return down(k,i)
        elif i != n:
            return up(k, i)
        else:
            return k
   
    def down(k,i):
        k, i = k - 1, i + 1
        if i % 7== 0 or has_seven(i):
            return up(k,i)
        elif i != n:
            return down(k,i)
        else:
            return k

    return up(1,1)
        

pingpong那个不会 就看了答案理解了一下
其他的代码：
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 ***"
    if n <= 3:
        return n
    else:
        return g(n-1) + 2 * g(n-2) + 3 * g(n-3)

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 ***"
    if n == 1 or n == 2 or n == 3:
        return n
    while n > 3:
        a, b, c = b, c,  c + 2 * b + 3 * c
        n -= 1
    return c


def has_seven(k):
    """Returns True if at least one of the digits of k is a 7, False otherwise.

    >>> has_seven(3)
    False
    >>> has_seven(7)
    True
    >>> has_seven(2734)
    True
    >>> has_seven(2634)
    False
    >>> has_seven(734)
    True
    >>> has_seven(7777)
    True
    """
    "*** YOUR CODE HERE ***"
    if k % 10 == 7:
        return True
    elif k < 10:
        return False
    else:
        return has_seven(k // 10)


def pingpong(n):
    """Return the nth element of the ping-pong sequence.

    >>> pingpong(7)
    7
    >>> pingpong(8)
    6
    >>> pingpong(15)
    1
    >>> pingpong(21)
    -1
    >>> pingpong(22)
    0
    >>> pingpong(30)
    6
    >>> pingpong(68)
    2
    >>> pingpong(69)
    1
    >>> pingpong(70)
    0
    >>> pingpong(71)
    1
    >>> pingpong(72)
    0
    >>> pingpong(100)
    2
    """
    "*** YOUR CODE HERE ***"
    def pingpong_next(k, p, up):
        if k == n:
            return p
        if up:
            return pingpong_switch(k+1, p+1, up)
        else:
            return pingpong_switch(k+1, p-1, up)
    def pingpong_switch(k, p, up):
        if k % 7 == 0 or has_seven(k):
            return pingpong_next(k, p, not up)
        else:
            return pingpong_next(k, p, up)

    return pingpong_next(1,1,True)



def count_change(amount):
    """Return the number of ways to make change for amount.

    >>> count_change(7)
    6
    >>> count_change(10)
    14
    >>> count_change(20)
    60
    >>> count_change(100)
    9828
    """
    "*** YOUR CODE HERE ***"
    def return_money(min,amount):
        if amount < 0:
            return 0
        elif amount == 0:
            return 1
        elif min > amount:
            return 0
        else:
            with_min = return_money(min, amount - min)
            without_min = return_money(2*min, amount)
        return without_min + with_min
    return return_money(1,amount)



def towers_of_hanoi(n, start, end):
    """Print the moves required to solve the towers of hanoi game, starting
    with n disks on the start pole and finishing on the end pole.

    The game is to assumed to have 3 poles.

    >>> towers_of_hanoi(1, 1, 3)
    Move the top disk from rod 1 to rod 3
    >>> towers_of_hanoi(2, 1, 3)
    Move the top disk from rod 1 to rod 2
    Move the top disk from rod 1 to rod 3
    Move the top disk from rod 2 to rod 3
    >>> towers_of_hanoi(3, 1, 3)
    Move the top disk from rod 1 to rod 3
    Move the top disk from rod 1 to rod 2
    Move the top disk from rod 3 to rod 2
    Move the top disk from rod 1 to rod 3
    Move the top disk from rod 2 to rod 1
    Move the top disk from rod 2 to rod 3
    Move the top disk from rod 1 to rod 3
    """
    assert 0 < start <= 3 and 0 < end <= 3 and start != end, "Bad start/end"
    "*** YOUR CODE HERE ***"
    if n == 1:
        print("Move the top of the disk from rod", start, "to rod", end)
    else:
        third = 6 - start - end
        towers_of_hanoi(n-1, start, third)
        towers_of_hanoi(1, start, end)
        towers_of_hanoi(n-1, third, end)

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'

FFFelix 发表于 2015-5-18 12:57
pingpong那个不会 就看了答案理解了一下
其他的代码：
def g(n):

赶进度challenge problem就没有做

才会写三个怎么办。。。感觉后面两个都得看答案
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 ***"
    if n <= 3:
        return n
    else:
        return g(n - 1) + 2 * g(n - 2) + 3 * g(n - 3)

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 ***"
    if n <= 3:
        return n
    a, b, c = 1, 2, 3
    while n > 3:
        a, b, c = b, c, c + 2 * b + 3 * a
        n -= 1
    return c


def has_seven(k):
    """Returns True if at least one of the digits of k is a 7, False otherwise.

    >>> has_seven(3)
    False
    >>> has_seven(7)
    True
    >>> has_seven(2734)
    True
    >>> has_seven(2634)
    False
    >>> has_seven(734)
    True
    >>> has_seven(7777)
    True
    """
    "*** YOUR CODE HERE ***"
    if k < 10:
        if k == 7:
            return True
        else:
            return False
    elif k % 10 == 7:
        return True
    else:
        return has_seven(k // 10)


def pingpong(n):
    """Return the nth element of the ping-pong sequence.

    >>> pingpong(7)
    7
    >>> pingpong(8)
    6
    >>> pingpong(15)
    1
    >>> pingpong(21)
    -1
    >>> pingpong(22)
    0
    >>> pingpong(30)
    6
    >>> pingpong(68)
    2
    >>> pingpong(69)
    1
    >>> pingpong(70)
    0
    >>> pingpong(71)
    1
    >>> pingpong(72)
    0
    >>> pingpong(100)
    2
    """
    "*** YOUR CODE HERE ***"
    def pingpong_next(k, p, up):
        if k == n:
            return p
        if up:
            return pingpong_switch(k + 1, p + 1, up)
        else:
            return pingpong_switch(k + 1, p - 1, up)

    def pingpong_switch(k, p, up):
        if k % 7 == 0 or has_seven(k):
            return pingpong_next(k, p, not up)
        else:
            return pingpong_next(k, p, up)

    return pingpong_next(1, 1, True)



def count_change(amount):
    """Return the number of ways to make change for amount.

    >>> count_change(7)
    6
    >>> count_change(10)
    14
    >>> count_change(20)
    60
    >>> count_change(100)
    9828
    """
    "*** YOUR CODE HERE ***"
    return count_using(1, amount)

def count_using(min_coin, amount):
    if amount < 0:
        return 0
    elif amount == 0:
        return 1
    elif min_coin > amount:
        return 0
    else:
        with_min = count_using(min_coin, amount -  min_coin)
        without_min = count_using(2 * min_coin, amount)
        return with_min + without_min


def towers_of_hanoi(n, start, end):
    """Print the moves required to solve the towers of hanoi game, starting
    with n disks on the start pole and finishing on the end pole.

    The game is to assumed to have 3 poles.

    >>> towers_of_hanoi(1, 1, 3)
    Move the top disk from rod 1 to rod 3
    >>> towers_of_hanoi(2, 1, 3)
    Move the top disk from rod 1 to rod 2
    Move the top disk from rod 1 to rod 3
    Move the top disk from rod 2 to rod 3
    >>> towers_of_hanoi(3, 1, 3)
    Move the top disk from rod 1 to rod 3
    Move the top disk from rod 1 to rod 2
    Move the top disk from rod 3 to rod 2
    Move the top disk from rod 1 to rod 3
    Move the top disk from rod 2 to rod 1
    Move the top disk from rod 2 to rod 3
    Move the top disk from rod 1 to rod 3
    """
    assert 0 < start <= 3 and 0 < end <= 3 and start != end, "Bad start/end"
    "*** YOUR CODE HERE ***"
    if n == 1:
        print("Move the top disk from rod", start, "to rod", end)
    else:
        other = 6 - start - end
        towers_of_hanoi(n-1, start, other)
        towers_of_hanoi(1, start, end)
        towers_of_hanoi(n-1, other, end)