lab 整理

刚开始上手确实很懵逼，渐渐搞懂了。

lab00

只需要直接返回 2024 即可。

def twenty_twenty_four():
    """Come up with the most creative expression that evaluates to 2024
    using only numbers and the +, *, and - operators.

    >>> twenty_twenty_four()
    2024
    """
    return 2024

lab01

WWPD

=====================================================================
Assignment: Lab 1
OK, version v1.18.1
=====================================================================

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Unlocking tests

At each "? ", type what you would expect the output to be.
Type exit() to quit

---------------------------------------------------------------------
return-and-print > Suite 1 > Case 1
(cases remaining: 1)

What would Python display? If you get stuck, try it out in the Python
interpreter!

>>> def welcome():
...     print('Go')
...     return 'hello'
>>> def cal():
...     print('Bears')
...     return 'world'
>>> welcome()
(line 1)? Go
(line 2)? 'hello'
-- OK! --

>>> print(welcome(), cal())
(line 1)? Go
(line 2)? Bears
(line 3)? hello world
-- OK! --

---------------------------------------------------------------------
OK! All cases for return-and-print unlocked.

---------------------------------------------------------------------
debugging-quiz > Suite 1 > Case 1
(cases remaining: 7)

Q: In the following traceback, what is the most recent function call?
Traceback (most recent call last):
    File "temp.py", line 10, in <module>
      f("hi")
    File "temp.py", line 2, in f
      return g(x + x, x)
    File "temp.py", line 5, in g
      return h(x + y * 5)
    File "temp.py", line 8, in h
      return x + 0
  TypeError: must be str, not int
Choose the number of the correct choice:
0) g(x + x, x)
1) f("hi")
2) h(x + y * 5)
? 2
-- OK! --

---------------------------------------------------------------------
debugging-quiz > Suite 1 > Case 2
(cases remaining: 6)

Q: In the following traceback, what is the cause of this error?
Traceback (most recent call last):
    File "temp.py", line 10, in <module>
      f("hi")
    File "temp.py", line 2, in f
      return g(x + x, x)
    File "temp.py", line 5, in g
      return h(x + y * 5)
    File "temp.py", line 8, in h
      return x + 0
  TypeError: must be str, not int
Choose the number of the correct choice:
0) the code attempted to add a string to an integer
1) there was a missing return statement
2) the code looped infinitely
? 0
-- OK! --

---------------------------------------------------------------------
debugging-quiz > Suite 1 > Case 3
(cases remaining: 5)

Q: How do you write a doctest asserting that square(2) == 4?
Choose the number of the correct choice:
0) def square(x):
       '''
       input: 2
       output: 4
       '''
       return x * x
1) def square(x):
       '''
       doctest: (2, 4)
       '''
       return x * x
2) def square(x):
       '''
       square(2)
       4
       '''
       return x * x
3) def square(x):
       '''
       >>> square(2)
       4
       '''
       return x * x
? 3
-- OK! --

---------------------------------------------------------------------
debugging-quiz > Suite 1 > Case 4
(cases remaining: 4)

Q: When should you use print statements?
Choose the number of the correct choice:
0) To investigate the values of variables at certain points in your code
1) For permanant debugging so you can have long term confidence in your code
2) To ensure that certain conditions are true at certain points in your code
? 0
-- OK! --

---------------------------------------------------------------------
debugging-quiz > Suite 1 > Case 5
(cases remaining: 3)

Q: How do you prevent the ok autograder from interpreting print statements as output?
Choose the number of the correct choice:
0) You don't need to do anything, ok only looks at returned values, not printed values
1) Print with 'DEBUG:' at the front of the outputted line
2) Print with # at the front of the outputted line
? 1
-- OK! --

---------------------------------------------------------------------
debugging-quiz > Suite 1 > Case 6
(cases remaining: 2)

Q: What is the best way to open an interactive terminal to investigate a failing test for question sum_digits in assignment lab01?
Choose the number of the correct choice:
0) python3 ok -q sum_digits --trace
1) python3 ok -q sum_digits
2) python3 ok -q sum_digits -i
3) python3 -i lab01.py
? 2
-- OK! --

---------------------------------------------------------------------
debugging-quiz > Suite 1 > Case 7
(cases remaining: 1)

Q: Which of the following is NOT true?
Choose the number of the correct choice:
0) Debugging is not a substitute for testing
1) It is generally good practice to release code with assertion statements left in
2) It is generally bad practice to release code with debugging print statements left in
3) Code that returns a wrong answer instead of crashing is generally better as it at least works fine
4) Testing is very important to ensure robust code
? 3
-- OK! --

---------------------------------------------------------------------
OK! All cases for debugging-quiz unlocked.

Backup... 100% completee
Backup past deadline by 34 days, 3 hours, 58 minutes, and 22 seconds
Backup successful for user: yangrenbing7@gmail.com
URL: https://okpy.org/cal/cs61a/fa24/lab01/backups/21KrOW

OK is up to date
=====================================================================
Assignment: Lab 1
OK, version v1.18.1
=====================================================================

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Running tests

---------------------------------------------------------------------
Test summary
    10 test cases passed! No cases failed.

Submit... 0.0% complete
Could not submit: Late Submission of cal/cs61a/fa24/lab01

OK is up to date

答案解释

函数调用输出

>>> def welcome():
...     print('Go')
...     return 'hello'
>>> def cal():
...     print('Bears')
...     return 'world'
>>> welcome()

预期输出：
- (line 1)? Go：调用 welcome() 函数时，它打印“Go”，所以第一行输出“Go”。
- (line 2)? 'hello'：welcome() 函数返回字符串 'hello'，但在这里没有直接打印出来。

打印函数输出

>>> print(welcome(), cal())

预期输出：
- (line 1)? Go：第一次调用 welcome() 打印“Go”。
- (line 2)? Bears：第二次调用 cal() 打印“Bears”。
- (line 3)? hello world：print 函数将两个函数的返回值组合在一起，分别是 'hello' 和 'world'。最终输出是“hello world”。

追溯最近的函数调用

这个问题询问追溯中最近的函数调用是什么。
- 正确答案是 2) h(x + y * 5)，因为这是在出现错误之前最后被调用的函数。

错误的原因

追溯中显示了由于使用不兼容的类型而导致的 TypeError。
- 正确答案是 0) the code attempted to add a string to an integer（代码尝试将字符串与整数相加）。这是因为调用 f 函数时传入了字符串参数，最终导致不兼容操作。

平方函数的文档测试

要断言 square(2) == 4，正确的文档测试格式是：

'''
>>> square(2)
4
'''

正确答案是 3，因为它正确地展示了如何使用文档测试。

何时使用打印语句

打印语句通常用于检查代码执行过程中的变量值。
- 正确答案是 0) To investigate the values of variables at certain points in your code（用于调查代码中特定时刻变量的值）。

防止自动评分器解读打印语句

为了防止自动评分器将打印语句解释为输出，你可以在打印语句前加上 'DEBUG:'。
- 正确答案是 1) Print with 'DEBUG:' at the front of the outputted line（在输出行前加上 'DEBUG:'）。

打开交互终端以调查失败的测试

要以交互方式调查失败的测试，应该使用可以打开交互提示符的命令。
- 正确答案是 2) python3 ok -q sum_digits -i，它允许进行交互式调试。

不正确的陈述

选项中不正确的陈述是：
- 3) Code that returns a wrong answer instead of crashing is generally better as it at least works fine（返回错误答案而不是崩溃的代码通常更好，因为它至少可以正常工作）。这是误导性的，因为错误的输出可能会导致比崩溃更大的问题。

Practice

def digit(n, k):
    """Return the digit that is k from the right of n for positive integers n and k.

    >>> digit(3579, 2)
    5
    >>> digit(3579, 0)
    9
    >>> digit(3579, 10)
    0
    """
    return (n // pow(10, k)) % 10


def middle(a, b, c):
    """Return the number among a, b, and c that is not the smallest or largest.
    Assume a, b, and c are all different numbers.

    >>> middle(3, 5, 4)
    4
    >>> middle(30, 5, 4)
    5
    >>> middle(3, 5, 40)
    5
    >>> middle(3, 5, 40)
    5
    >>> middle(30, 5, 40)
    30
    """
    return min(max(a, b), max(b, c), max(a, c))


def falling(n, k):
    """Compute the falling factorial of n to depth k.

    >>> falling(6, 3)  # 6 * 5 * 4
    120
    >>> falling(4, 3)  # 4 * 3 * 2
    24
    >>> falling(4, 1)  # 4
    4
    >>> falling(4, 0)
    1
    """
    if k == 0:
        return 1
    else:
        return n * falling(n - 1, k - 1)


def divisible_by_k(n, k):
    """
    >>> a = divisible_by_k(10, 2)  # 2, 4, 6, 8, and 10 are divisible by 2
    2
    4
    6
    8
    10
    >>> a
    5
    >>> b = divisible_by_k(3, 1)  # 1, 2, and 3 are divisible by 1
    1
    2
    3
    >>> b
    3
    >>> c = divisible_by_k(6, 7)  # There are no integers up to 6 divisible by 7
    >>> c
    0
    """
    cnt = 0
    for i in range(1, n + 1):
        if i % k == 0:
            cnt += 1
            print(i)
    return cnt


def sum_digits(y):
    """Sum all the digits of y.

    >>> sum_digits(10) # 1 + 0 = 1
    1
    >>> sum_digits(4224) # 4 + 2 + 2 + 4 = 12
    12
    >>> sum_digits(1234567890)
    45
    >>> a = sum_digits(123) # make sure that you are using return rather than print
    >>> a
    6
    """
    sum = 0
    while y:
        sum += y % 10
        y //= 10
    return sum


def double_eights(n):
    """Return true if n has two eights in a row.
    >>> double_eights(8)
    False
    >>> double_eights(88)
    True
    >>> double_eights(2882)
    True
    >>> double_eights(880088)
    True
    >>> double_eights(12345)
    False
    >>> double_eights(80808080)
    False
    """
    cnt = 0
    while n:
        if n % 10 == 8:
            cnt += 1
            if cnt == 2:
                return True
        else:
            cnt = 0
        n //= 10
    return False

总结

简单总结一下：

pow(x,y)：表示\(x^y\)。
middle这个比较有意思，直接返回表达式。在 python 中max函数可以不止两个参数。

lab02

WWPD

Windows PowerShell
版权所有（C） Microsoft Corporation。保留所有权利。

安装最新的 PowerShell，了解新功能和改进！https://aka.ms/PSWindows

PS C:\Users\APP\Desktop\整合\自学\CS61A\lab\lab02> python ok -u
=====================================================================
Assignment: Lab 2
OK, version v1.18.1
=====================================================================

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Unlocking tests

At each "? ", type what you would expect the output to be.
Type exit() to quit

---------------------------------------------------------------------
Lambda the Free > Suite 1 > Case 1
(cases remaining: 5)

Q: Which of the following statements describes a difference between a def statement and a lambda expression?
Choose the number of the correct choice:
0) A lambda expression cannot have more than two parameters.
1) A lambda expression cannot return another function.
2) A lambda expression does not automatically bind the function that it returns to a name.
3) A def statement can only have one line in its body.
? 2
-- OK! --

---------------------------------------------------------------------
Lambda the Free > Suite 1 > Case 2
(cases remaining: 4)

Q: How many formal parameters does the following lambda expression have?
lambda a, b: c + d
Choose the number of the correct choice:
0) two
1) one
2) Not enough information
3) three
? 0
-- OK! --

---------------------------------------------------------------------
Lambda the Free > Suite 1 > Case 3
(cases remaining: 3)

Q: When is the return expression of a lambda expression executed?
Choose the number of the correct choice:
0) When you pass the lambda expression into another function.
1) When the function returned by the lambda expression is called.
2) When you assign the lambda expression to a name.
3) When the lambda expression is evaluated.
? 1
-- OK! --

---------------------------------------------------------------------
Lambda the Free > Suite 2 > Case 1
(cases remaining: 2)

What would Python display? If you get stuck, try it out in the Python
interpreter!

>>> # If Python displays <function...>, type Function, if it errors type Error, if it displays nothing type Nothing
>>> lambda x: x  # A lambda expression with one parameter x
? Function
-- OK! --

>>> a = lambda x: x  # Assigning a lambda function to the name a
>>> a(5)
? 5
-- OK! --

>>> (lambda: 3)()  # Using a lambda expression as an operator in a call exp.
? 3
-- OK! --

>>> b = lambda x, y: lambda: x + y # Lambdas can return other lambdas!
>>> c = b(8, 4)
>>> c
? Function
-- OK! --

>>> c()
? 12
-- OK! --

>>> d = lambda f: f(4)  # They can have functions as arguments as well
>>> def square(x):
...     return x * x
>>> d(square)
? 16
-- OK! --

---------------------------------------------------------------------
Lambda the Free > Suite 2 > Case 2
(cases remaining: 1)

What would Python display? If you get stuck, try it out in the Python
interpreter!

>>> # Try drawing an environment diagram if you get stuck!
>>> higher_order_lambda = lambda f: lambda x: f(x)
>>> g = lambda x: x * x
>>> higher_order_lambda(2)(g) # Which argument belongs to which function call?
? Error
-- OK! --

>>> higher_order_lambda(g)(2)
? 4
-- OK! --

>>> call_thrice = lambda f: lambda x: f(f(f(x)))
>>> call_thrice(lambda y: y + 1)(0)
? 3
-- OK! --

>>> print_lambda = lambda z: print(z) # When is the return expression of a lambda expression executed?
>>> print_lambda
? Function
-- OK! --

>>> one_thousand = print_lambda(1000)
? 1000
-- OK! --

>>> one_thousand # What did the call to print_lambda return? If it displays nothing, write Nothing
? Nothing
-- OK! --

---------------------------------------------------------------------
OK! All cases for Lambda the Free unlocked.

---------------------------------------------------------------------
The Truth Will Prevail > Suite 1 > Case 1
(cases remaining: 4)

What would Python display? If you get stuck, try it out in the Python
interpreter!

>>> True and 13
? 13
-- OK! --

>>> False or 0
? 0
-- OK! --

>>> not 10
? False
-- OK! --

>>> not None
? True
-- OK! --

---------------------------------------------------------------------
The Truth Will Prevail > Suite 2 > Case 1
(cases remaining: 3)

What would Python display? If you get stuck, try it out in the Python
interpreter!

>>> True and 1 / 0  # If this errors, just type Error.
? Error
-- OK! --

>>> True or 1 / 0  # If this errors, just type Error.
? True
-- OK! --

>>> -1 and 1 > 0 # If this errors, just type Error.
? True
-- OK! --

>>> -1 or 5
? -1
-- OK! --

>>> (1 + 1) and 1  # If this errors, just type Error. If this is blank, just type Nothing.
? 1
-- OK! --

---------------------------------------------------------------------
The Truth Will Prevail > Suite 2 > Case 2
(cases remaining: 2)

What would Python display? If you get stuck, try it out in the Python
interpreter!

>>> print(3) or ""
(line 1)? 3
(line 2)? ""
-- OK! --

---------------------------------------------------------------------
The Truth Will Prevail > Suite 3 > Case 1
(cases remaining: 1)

What would Python display? If you get stuck, try it out in the Python
interpreter!

>>> def f(x):
...     if x == 0:
...         return "zero"
...     elif x > 0:
...         return "positive"
...     else:
...         return ""
>>> 0 or f(1)
? "positive"
-- OK! --

>>> f(0) or f(-1)
? "zero"
-- OK! --

>>> f(0) and f(-1)
? ""
-- OK! --

---------------------------------------------------------------------
OK! All cases for The Truth Will Prevail unlocked.

---------------------------------------------------------------------
Higher Order Functions > Suite 1 > Case 1
(cases remaining: 1)

What would Python display? If you get stuck, try it out in the Python
interpreter!

>>> # If Python displays <function...>, type Function, if it errors type Error, if it displays nothing type Nothing
>>> def cake():
...    print('beets')
...    def pie():
...        print('sweets')
...        return 'cake'
...    return pie
>>> chocolate = cake()
? beets
-- OK! --

>>> chocolate
? Function
-- OK! --

>>> chocolate()
(line 1)? sweets
(line 2)? 'cake'
-- OK! --

>>> more_chocolate, more_cake = chocolate(), cake
? sweets
-- OK! --

>>> more_chocolate
? 'cake'
-- OK! --

>>> # Reminder: cake, more_cake, and chocolate were defined/assigned in the code above!
>>> # It might be helpful to refer to their definitions on the assignment website so you don't have to scroll as much!
>>> def snake(x, y):
...    if cake == more_cake:
...        return chocolate
...    else:
...        return x + y
>>> snake(10, 20)
? Function
-- OK! --

>>> snake(10, 20)()
(line 1)? sweets
(line 2)? 'cake'
-- OK! --

>>> cake = 'cake'
>>> snake(10, 20)
? 30
-- OK! --

---------------------------------------------------------------------
OK! All cases for Higher Order Functions unlocked.

Backup... 100% complete
Backup past deadline by 27 days, 4 hours, 40 minutes, and 27 seconds
OK is up to date

答案解释

Lambda the Free

函数定义和 Lambda 表达式的区别

问题：哪个语句描述了 def 语句和 Lambda 表达式之间的区别？
答案：2) A lambda expression does not automatically bind the function that it returns to a name.（Lambda 表达式不会自动将其返回的函数绑定到名称）。
- 解释：def 语句定义的函数可以直接通过名称调用，而 Lambda 表达式需要被赋值给一个变量才能被调用。

Lambda 表达式的参数数量

问题：给定的 Lambda 表达式 lambda a, b: c + d 有多少个正式参数？
答案：0) two（两个）。
- 解释：这个 Lambda 表达式有两个参数 a 和 b。

Lambda 表达式的返回表达式执行时间

问题：Lambda 表达式的返回表达式何时执行？
答案：1) When the function returned by the lambda expression is called.（当返回的 Lambda 表达式被调用时）。
- 解释：Lambda 表达式本身不会立即执行，只有在其返回的函数被调用时，返回表达式才会被执行。

Lambda 表达式的输出

>>> lambda x: x

答案：Function。
- 解释：这是一个 Lambda 表达式，定义了一个带有一个参数的函数，但未被调用。

赋值 Lambda 表达式

>>> a = lambda x: x
>>> a(5)

答案：5。
- 解释：调用 Lambda 函数 a 并传递参数 5，返回 5。

无参数 Lambda 表达式

>>> (lambda: 3)()

答案：3。
- 解释：这是一个无参数的 Lambda 表达式，直接调用返回 3。

返回其他 Lambda 的 Lambda

>>> b = lambda x, y: lambda: x + y
>>> c = b(8, 4)

答案：Function。
- 解释：b 返回一个新的 Lambda 函数，该函数可以被调用以返回 x + y 的结果。

调用返回的 Lambda

>>> c()

答案：12。
- 解释：调用 c 返回 8 + 4，即 12。

接收函数作为参数的 Lambda

>>> d = lambda f: f(4)
>>> def square(x):
...     return x * x
>>> d(square)

答案：16。
- 解释：d 函数接收 square 函数作为参数，调用 square(4) 返回 16。

The Truth Will Prevail

逻辑运算的输出

>>> True and 13

答案：13。
- 解释：逻辑与运算符 and 的结果是 13，因为在 True 的情况下，and 返回后面的值。

逻辑或运算的输出

>>> False or 0

答案：0。
- 解释：逻辑或运算符 or 返回 0，因为前面的值是 False。

非运算的输出

>>> not 10

答案：False。
- 解释：任何非零值在布尔上下文中都被视为 True，因此 not 10 返回 False。

非运算的 None 值

>>> not None

答案：True。
- 解释：None 在布尔上下文中被视为 False，因此 not None 返回 True。

含错误的逻辑运算

>>> True and 1 / 0

答案：Error。
- 解释：在 and 运算中，由于第二个表达式会导致除以零错误，因此会返回错误。

逻辑或运算中的错误

>>> True or 1 / 0

答案：True。
- 解释：由于 or 运算符短路特性，1 / 0 不会被执行，因此返回 True。

逻辑与的比较

>>> -1 and 1 > 0

答案：True。
- 解释：-1 是 True，且 1 > 0 也是 True，所以结果为 True。

逻辑或运算

>>> -1 or 5

答案：-1。
- 解释：由于 -1 是 True，因此返回 -1。

Higher Order Functions

函数定义

>>> def cake():
...    print('beets')
...    def pie():
...        print('sweets')
...        return 'cake'
...    return pie
>>> chocolate = cake()

答案：beets。
- 解释：调用 cake() 时打印 beets，并返回内部函数 pie。

检查返回的函数

>>> chocolate

答案：Function。
- 解释：chocolate 现在是一个函数（pie）。

调用返回的函数

>>> chocolate()

答案：sweets 和 'cake'。
- 解释：调用 chocolate 函数会打印 sweets，并返回 'cake'。

多重赋值

>>> more_chocolate, more_cake = chocolate(), cake

答案：sweets。
- 解释：调用 chocolate() 会打印 sweets。

返回的值

>>> more_chocolate

答案：'cake'。
- 解释：more_chocolate 接收 chocolate() 的返回值 'cake'。

条件语句的返回

>>> def snake(x, y):
...    if cake == more_cake:
...        return chocolate
...    else:
...        return x + y
>>> snake(10, 20)

答案：Function。
- 解释：cake 和 more_cake 是相同的，因此返回 chocolate 函数。

调用函数返回

>>> snake(10, 20)()

答案：sweets 和 'cake'。
- 解释：调用 snake 返回 chocolate 函数，然后调用它打印 sweets，返回 'cake'。

改变 cake 的值

>>> cake = 'cake'
>>> snake(10, 20)

答案：30。
- 解释：这次 cake 和 more_cake 不再相同，因此返回 10 + 20，即 30。

Practice

有趣，了解了一下闭包的概念。

from math import gcd

def composite_identity(f, g):
    """
    Return a function with one parameter x that returns True if f(g(x)) is
    equal to g(f(x)). You can assume the result of g(x) is a valid input for f
    and vice versa.

    >>> add_one = lambda x: x + 1        # adds one to x
    >>> square = lambda x: x**2          # squares x [returns x^2]
    >>> b1 = composite_identity(square, add_one)
    >>> b1(0)                            # (0 + 1) ** 2 == 0 ** 2 + 1
    True
    >>> b1(4)                            # (4 + 1) ** 2 != 4 ** 2 + 1
    False
    """
    return lambda x: f(g(x)) == g(f(x))


def sum_digits(y):
    """Return the sum of the digits of non-negative integer y."""
    total = 0
    while y > 0:
        total, y = total + y % 10, y // 10
    return total

def is_prime(n):
    """Return whether positive integer n is prime."""
    if n == 1:
        return False
    k = 2
    while k < n:
        if n % k == 0:
            return False
        k += 1
    return True

def count_cond(condition):
    """Returns a function with one parameter N that counts all the numbers from
    1 to N that satisfy the two-argument predicate function Condition, where
    the first argument for Condition is N and the second argument is the
    number from 1 to N.

    >>> count_fives = count_cond(lambda n, i: sum_digits(n * i) == 5)
    >>> count_fives(10)   # 50 (10 * 5)
    1
    >>> count_fives(50)   # 50 (50 * 1), 500 (50 * 10), 1400 (50 * 28), 2300 (50 * 46)
    4

    >>> is_i_prime = lambda n, i: is_prime(i) # need to pass 2-argument function into count_cond
    >>> count_primes = count_cond(is_i_prime)
    >>> count_primes(2)    # 2
    1
    >>> count_primes(3)    # 2, 3
    2
    >>> count_primes(4)    # 2, 3
    2
    >>> count_primes(5)    # 2, 3, 5
    3
    >>> count_primes(20)   # 2, 3, 5, 7, 11, 13, 17, 19
    8
    """
    "*** YOUR CODE HERE ***"
    def counter(n):
        i = 1
        count = 0
        while i <= n:
            if(condition(n, i)):
                count += 1
            i += 1
        return count
    return counter

def multiple(a, b):
    """Return the smallest number n that is a multiple of both a and b.

    >>> multiple(3, 4)
    12
    >>> multiple(14, 21)
    42
    """
    "*** YOUR CODE HERE ***"
    return a * b // gcd(a, b)


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
    """
    def g(n):
        def h(x):
            if n == 0:
                return x
            else:
                return cycle(f2, f3, f1)(n - 1)(f1(x))
        return h
    return g

总结

解释一下最后的cycle：
这段代码实现了一个 高阶函数，它可以按照指定的次数，依次调用三个函数 f1、f2 和 f3，形成一个“函数循环”。具体来说，它通过递归来实现这个循环，每次调用时，将函数的顺序轮换，并逐步减少剩余的执行次数。我们来逐步分析这个递归结构：

函数结构
1. cycle(f1, f2, f3):
  - cycle 是最外层函数，它接受三个单参数函数 f1, f2, 和 f3 作为输入。
  - 它返回一个函数 g(n)，其中 n 表示将依次执行 f1, f2, f3 几次的组合操作。
2. g(n):
  - g 是一个函数，接受一个参数 n。n 表示在输入上要进行几次函数的组合调用。
  - 它返回一个函数 h(x)，其中 x 是对哪个数执行函数的组合。
3. h(x):
  - h 是最终的函数，它接受参数 x，并在此参数上按照 f1, f2, f3 的顺序执行操作。
  - 递归通过 n 来决定执行多少次。
递归逻辑分析

让我们特别关注递归的部分：
def h(x):
if n == 0:
return x
else:
return cycle(f2, f3, f1)(n - 1)(f1(x))
这个函数 h(x) 是用来在输入 x 上应用函数组合的。
- if n == 0:
  当 n == 0 时，表示没有函数要执行了，因此 h(x) 直接返回 x，即输入什么输出什么。这是递归的基线条件，防止无限递归。
- 递归的 else 部分：
  return cycle(f2, f3, f1)(n - 1)(f1(x))
  这行代码非常关键。让我们逐步理解：
  - f1(x)：首先调用 f1，对 x 执行函数 f1 的操作。这个结果将作为递归调用的输入。
  - cycle(f2, f3, f1)：然后调用 cycle 函数，传入 f2, f3, f1，也就是说，下一轮的函数顺序变成了 f2, f3, f1，实现了函数的“轮换”。
  - (n - 1)：将剩余执行次数 n 减 1，递归调用时，会在 n-1 次的基础上继续。
  - 最后，通过递归调用 h(x)，对 x（已经经过 f1 处理的值）继续调用下一轮的函数组合。
例子解析

让我们通过一个例子来理解：

my_cycle = cycle(add1, times2, add3)

创建了一个循环函数 my_cycle，其中 add1, times2, add3 按顺序执行。

my_cycle(3)(2) 的计算过程：
1. n = 3，调用 add1(2)，结果是 3。
2. 递归调用 cycle(times2, add3, add1)(2)(3)：
  - n = 2，调用 times2(3)，结果是 6。
3. 递归调用 cycle(add3, add1, times2)(1)(6)：
  - n = 1，调用 add3(6)，结果是 9。
4. 递归调用 cycle(add1, times2, add3)(0)(9)：
  - n = 0，直接返回 9。
最终，结果为 9，这表明三个函数 add1 -> times2 -> add3 被依次应用在 2 上，得到的最终结果是 9。

总结

递归部分的关键点在于：
1. 按照函数顺序 f1 -> f2 -> f3 应用它们，但顺序会在递归调用中每次向前轮换。
2. 递归基线是 n == 0，防止无限递归，并确保函数最终返回结果。
闭包的解释
counter 能够捕获变量 n 的原因在于闭包的概念。Python 支持闭包，允许内部函数（如 counter）捕获并使用外部函数作用域中的变量（如 n）。

闭包的解释

在 Python 中，当一个函数定义在另一个函数的内部时，内部函数会记住它所处的外部函数中的变量，即使外部函数已经返回，内部函数仍然可以访问这些变量。

在你的代码中：
def count_cond(condition):
def counter(n):
i = 1
count = 0
while i <= n:
if condition(n, i):
count += 1
i += 1
return count
return counter
- count_cond 函数返回 counter 函数。
- 当 count_cond 被调用时，比如 count_fives = count_cond(lambda n, i: sum_digits(n * i) == 5)，Python 创建并返回了 counter 函数。
- 尽管 count_cond 函数结束并返回了 counter，但 counter 仍然能够访问它在调用时的 n 参数，这是因为 counter 形成了一个闭包。
为什么 counter 能捕获 n

当你调用 count_fives(10) 时，counter(10) 被调用：
- n = 10 被传递给 counter 函数，n 成为 counter 的局部变量。
- 在 counter 中，每次调用 condition(n, i)，n 这个局部变量会传递给 condition。
由于 n 是 counter 函数的参数，Python 将它视为 counter 的局部变量，因此它可以被随时捕获和使用。也就是说，counter 捕获并使用了传递给它的 n，这就是为什么 n 在内部函数中是可见并可用的。

闭包示例

一个简单的闭包示例：
def outer_function(x):
def inner_function(y):
return x + y
return inner_function

closure = outer_function(5)
print(closure(10)) # 输出 15
在这个例子中，outer_function 返回了 inner_function，并且 inner_function 捕获了 x，即使 outer_function 已经结束。closure(10) 调用时，inner_function 仍然能够访问并使用 x = 5。类似地，在你的代码中，counter 捕获并使用了传入的 n。

lab03

WWPD

Windows PowerShell
版权所有（C） Microsoft Corporation。保留所有权利。

安装最新的 PowerShell，了解新功能和改进！https://aka.ms/PSWindows

PS C:\Users\APP\Desktop\整合\自学\CS61A\lab\lab03> python ok -u
=====================================================================

Assignment: Lab 3

OK, version v1.18.1
=====================================================================Unlocking tests

At each "? ", type what you would expect the output to be.
Type exit() to quit

---------------------------------------------------------------------
Lists > Suite 1 > Case 1
(cases remaining: 1)

What would Python display? If you get stuck, try it out in the Python
interpreter!

>>> s = [7//3, 5, [4, 0, 1], 2]
>>> s[0]
? 2
-- OK! --

>>> s[2]
? [4, 0, 1]
-- OK! --

>>> s[-1]
? 2
-- OK! --

>>> len(s)
? 4
-- OK! --

>>> 4 in s
? False
-- OK! --

>>> 4 in s[2]
? True
-- OK! --

>>> s[2] + [3 + 2]
? [4, 0, 1, 5]
-- OK! --

>>> 5 in s[2]
? False
-- OK! --

>>> s[2] * 2
? [4, 0, 1, 4, 0, 1]
-- OK! --

>>> list(range(3, 6))
? [3, 4, 5]
-- OK! --

>>> range(3, 6)
? range(3, 6)
-- OK! --

>>> r = range(3, 6)
>>> [r[0], r[2]]
? [3, 5]
-- OK! --

>>> range(4)[-1]
? 3
-- OK! --

---------------------------------------------------------------------
OK! All cases for Lists unlocked.

---------------------------------------------------------------------
Comprehensions > Suite 1 > Case 1
(cases remaining: 1)

What would Python display? If you get stuck, try it out in the Python
interpreter!

>>> [2 * x for x in range(4)]
? [0, 2, 4, 6]
-- OK! --

>>> [y for y in [6, 1, 6, 1] if y > 2]
? [6, 6]
-- OK! --

>>> [[1] + s for s in [[4], [5, 6]]]
? [[1, 4], [1, 5, 6]]
-- OK! --

>>> [z + 1 for z in range(10) if z % 3 == 0]
? [1, 4, 7, 10]
-- OK! --

---------------------------------------------------------------------
OK! All cases for Comprehensions unlocked.

Backup... 100% complete
Backup past deadline by 13 days, 6 hours, 8 minutes, and 56 seconds
OK is up to date

答案解释

Lists

s = [7//3, 5, [4, 0, 1], 2]
- s[0] 结果为 2
  - 解释：7 // 3 是整数除法，结果为 2。
- s[2] 结果为 [4, 0, 1]
  - 解释：这是列表 s 中的第三个元素，即嵌套列表。
- s[-1] 结果为 2
  - 解释：负索引 -1 表示列表的最后一个元素。
- len(s) 结果为 4
  - 解释：列表 s 中有四个元素，分别是 2、5、[4, 0, 1] 和 2。
- 4 in s 结果为 False
  - 解释：4 不在列表 s 的四个元素中。
- 4 in s[2] 结果为 True
  - 解释：4 在 s[2] 中的嵌套列表 [4, 0, 1] 中。
- s[2] + [3 + 2] 结果为 [4, 0, 1, 5]
  - 解释：s[2] 是 [4, 0, 1]，而 3 + 2 的结果是 5，合并后形成新的列表。
- 5 in s[2] 结果为 False
  - 解释：5 不在 s[2] 的嵌套列表 [4, 0, 1] 中。
- s[2] * 2 结果为 [4, 0, 1, 4, 0, 1]
  - 解释：将嵌套列表重复两次，形成新列表。
- list(range(3, 6)) 结果为 [3, 4, 5]
  - 解释：range(3, 6) 生成从 3 到 5 的数字，转换为列表。
- range(3, 6) 结果为 range(3, 6)
  - 解释：range 对象的显示形式。
- r = range(3, 6)，[r[0], r[2]] 结果为 [3, 5]
  - 解释：r[0] 是 3，r[2] 是 5。
- range(4)[-1] 结果为 3
  - 解释：负索引 -1 获取范围中的最后一个元素。

Comprehensions

[2 * x for x in range(4)]
- 结果为 [0, 2, 4, 6]
  - 解释：range(4) 生成 0, 1, 2, 3，每个值乘以 2 后形成新列表。
[y for y in [6, 1, 6, 1] if y > 2]
- 结果为 [6, 6]
  - 解释：仅保留大于 2 的值。
[[1] + s for s in [[4], [5, 6]]]
- 结果为 [[1, 4], [1, 5, 6]]
  - 解释：将 1 添加到每个嵌套列表的开头。
[z + 1 for z in range(10) if z % 3 == 0]
- 结果为 [1, 4, 7, 10]
  - 解释：仅保留 0, 3, 6, 9（0 和 3 在 +1 后形成 1 和 4），再加上 10（9 在 +1 后形成 10）。

Practice

LAB_SOURCE_FILE = __file__


def print_if(s, f):
    """Print each element of s for which f returns a true value.

    >>> print_if([3, 4, 5, 6], lambda x: x > 4)
    5
    6
    >>> result = print_if([3, 4, 5, 6], lambda x: x % 2 == 0)
    4
    6
    >>> print(result)  # print_if should return None
    None
    """
    for x in s:
        if f(x):
            print(x)
    return


from math import fabs
def close(s, k):
    """Return how many elements of s that are within k of their index.

    >>> t = [6, 2, 4, 3, 5]
    >>> close(t, 0)  # Only 3 is equal to its index
    1
    >>> close(t, 1)  # 2, 3, and 5 are within 1 of their index
    3
    >>> close(t, 2)  # 2, 3, 4, and 5 are all within 2 of their index
    4
    >>> close(list(range(10)), 0)
    10
    """
    count = 0
    for i in range(len(s)):  # Use a range to loop over indices
        "*** YOUR CODE HERE ***"
        if fabs(i - s[i]) <= k:
            count += 1
    return count


def close_list(s, k):
    """Return a list of the elements of s that are within k of their index.

    >>> t = [6, 2, 4, 3, 5]
    >>> close_list(t, 0)  # Only 3 is equal to its index
    [3]
    >>> close_list(t, 1)  # 2, 3, and 5 are within 1 of their index
    [2, 3, 5]
    >>> close_list(t, 2)  # 2, 3, 4, and 5 are all within 2 of their index
    [2, 4, 3, 5]
    """
    return [ s[i] for i in range(len(s)) if fabs(i - s[i]) <= k]


from math import sqrt

def squares(s):
    """Returns a new list containing square roots of the elements of the
    original list that are perfect squares.

    >>> seq = [8, 49, 8, 9, 2, 1, 100, 102]
    >>> squares(seq)
    [7, 3, 1, 10]
    >>> seq = [500, 30]
    >>> squares(seq)
    []
    """
    return [ round(sqrt(n)) for n in s if round(sqrt(n)) * round(sqrt(n)) == n]     # 注意精度问题 should use round() to avoid float


def double_eights(n):
    """Returns whether or not n has two digits in row that
    are the number 8.

    >>> double_eights(1288)
    True
    >>> double_eights(880)
    True
    >>> double_eights(538835)
    True
    >>> double_eights(284682)
    False
    >>> double_eights(588138)
    True
    >>> double_eights(78)
    False
    >>> # ban iteration
    >>> from construct_check import check
    >>> check(LAB_SOURCE_FILE, 'double_eights', ['While', 'For'])
    True
    """
    "*** YOUR CODE HERE ***"
    if n < 10:
        return False
    if n % 10 == 8 and n // 10 % 10 == 8:
        return True
    return double_eights(n // 10)


def make_onion(f, g):
    """Return a function can_reach(x, y, limit) that returns
    whether some call expression containing only f, g, and x with
    up to limit calls will give the result y.

    >>> up = lambda x: x + 1
    >>> double = lambda y: y * 2
    >>> can_reach = make_onion(up, double)
    >>> can_reach(5, 25, 4)      # 25 = up(double(double(up(5))))
    True
    >>> can_reach(5, 25, 3)      # Not possible
    False
    >>> can_reach(1, 1, 0)      # 1 = 1
    True
    >>> add_ing = lambda x: x + "ing"
    >>> add_end = lambda y: y + "end"
    >>> can_reach_string = make_onion(add_ing, add_end)
    >>> can_reach_string("cry", "crying", 1)      # "crying" = add_ing("cry")
    True
    >>> can_reach_string("un", "unending", 3)     # "unending" = add_ing(add_end("un"))
    True
    >>> can_reach_string("peach", "folding", 4)   # Not possible
    False
    """
    def can_reach(x, y, limit):
        if limit < 0:
            return False
        elif x == y:
            return True
        else:
            return can_reach(f(x), y, limit - 1) or can_reach(g(x), y, limit - 1)
    return can_reach

总结

可以学到这个用法：返回一个列表推导式，当fabs(i - s[i]) <= k，返回s[i]。

def close_list(s, k):
    """Return a list of the elements of s that are within k of their index.

    >>> t = [6, 2, 4, 3, 5]
    >>> close_list(t, 0)  # Only 3 is equal to its index
    [3]
    >>> close_list(t, 1)  # 2, 3, and 5 are within 1 of their index
    [2, 3, 5]
    >>> close_list(t, 2)  # 2, 3, 4, and 5 are all within 2 of their index
    [2, 4, 3, 5]
    """
    return [ s[i] for i in range(len(s)) if fabs(i - s[i]) <= k]

这个需要注意一下精度问题：round()函数采用"四舍六入，五取偶"的规则，也称为"银行家舍入法"。具体来说：

当需要舍入的位数小于 5 时（如 1, 2, 3, 4），直接舍去。
当需要舍入的位数大于 5 时（如 6, 7, 8, 9），直接进一。

当需要舍入的位数为 5 时，取决于被舍去位之前的数字：

如果舍去位前的数字是偶数，则舍去（向下舍入）。

如果舍去位前的数字是奇数，则进一（向上舍入）。

print(round(2.5))  # 输出 2，舍入为偶数
print(round(3.5))  # 输出 4，舍入为偶数
print(round(1.235, 2))  # 输出 1.24，四舍六入五取偶
print(round(1.245, 2))  # 输出 1.24，五取偶

def squares(s):
    """Returns a new list containing square roots of the elements of the
    original list that are perfect squares.

    >>> seq = [8, 49, 8, 9, 2, 1, 100, 102]
    >>> squares(seq)
    [7, 3, 1, 10]
    >>> seq = [500, 30]
    >>> squares(seq)
    []
    """
    return [ round(sqrt(n)) for n in s if round(sqrt(n)) * round(sqrt(n)) == n]
    # 注意精度问题 should use round() to avoid float

注意到需要两位是 8，不难想到从n的最低位进行处理：先判断最低位是不是 8，再看高一位是不是也是 8，如果是，返回True。

如果n只有 1 位，肯定不符合题意，返回False。

def double_eights(n):
    """Returns whether or not n has two digits in row that
    are the number 8.

    >>> double_eights(1288)
    True
    >>> double_eights(880)
    True
    >>> double_eights(538835)
    True
    >>> double_eights(284682)
    False
    >>> double_eights(588138)
    True
    >>> double_eights(78)
    False
    >>> # ban iteration
    >>> from construct_check import check
    >>> check(LAB_SOURCE_FILE, 'double_eights', ['While', 'For'])
    True
    """
    "*** YOUR CODE HERE ***"
    if n < 10:
        return False
    if n % 10 == 8 and n // 10 % 10 == 8:
        return True
    return double_eights(n // 10)

这道题目的要求是返回函数can_reach：我们需要进行can_reach函数的编写：要求的是通过小于limit次的f和g函数的操作，实现x==y，这里采用递归方法。
- 临界情况：超过limit次，can_reach函数返回False。
- 成功情况：x==y，返回True。
- 一般情况：更新x，继续进行can_reach函数操作：有两种情况：
  - 可能是调用f，也可能是调用g，采取其中一种方法即可，所以两种结果进行or运算。

def make_onion(f, g):
    """Return a function can_reach(x, y, limit) that returns
    whether some call expression containing only f, g, and x with
    up to limit calls will give the result y.

    >>> up = lambda x: x + 1
    >>> double = lambda y: y * 2
    >>> can_reach = make_onion(up, double)
    >>> can_reach(5, 25, 4)      # 25 = up(double(double(up(5))))
    True
    >>> can_reach(5, 25, 3)      # Not possible
    False
    >>> can_reach(1, 1, 0)      # 1 = 1
    True
    >>> add_ing = lambda x: x + "ing"
    >>> add_end = lambda y: y + "end"
    >>> can_reach_string = make_onion(add_ing, add_end)
    >>> can_reach_string("cry", "crying", 1)      # "crying" = add_ing("cry")
    True
    >>> can_reach_string("un", "unending", 3)     # "unending" = add_ing(add_end("un"))
    True
    >>> can_reach_string("peach", "folding", 4)   # Not possible
    False
    """
    def can_reach(x, y, limit):
        if limit < 0:
            return False
        elif x == y:
            return True
        else:
            return can_reach(f(x), y, limit - 1) or can_reach(g(x), y, limit - 1)
    return can_reach

lab04

WWPD

=====================================================================
Assignment: Lab 4
OK, version v1.18.1
=====================================================================

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Unlocking tests

At each "? ", type what you would expect the output to be.
Type exit() to quit

---------------------------------------------------------------------
Dictionaries > Suite 1 > Case 1
(cases remaining: 1)

What would Python display? If you get stuck, try it out in the Python
interpreter!

>>> pokemon = {'pikachu': 25, 'dragonair': 148, 'mew': 151}
>>> pokemon['pikachu']
? 25
-- OK! --

>>> len(pokemon)
? 3
-- OK! --

>>> 'mewtwo' in pokemon
? False
-- OK! --

>>> 'pikachu' in pokemon
? True
-- OK! --

>>> 25 in pokemon
? False
-- OK! --

>>> 148 in pokemon.values()
? True
-- OK! --

>>> 151 in pokemon.keys()
? False
-- OK! --

>>> 'mew' in pokemon.keys()
? True
-- OK! --

---------------------------------------------------------------------
OK! All cases for Dictionaries unlocked.

Backup... 100% complete

答案解释

以下是每道题的中文解释：

pokemon['pikachu']
- 答案：25
- 解释： 这是在字典 pokemon 中通过键 'pikachu' 来访问对应的值。键 'pikachu' 的值是 25，所以返回 25。
len(pokemon)
- 答案：3
- 解释： len() 函数返回字典 pokemon 中键-值对的数量。这里有三个键-值对：'pikachu'、'dragonair' 和 'mew'，所以长度为 3。
'mewtwo' in pokemon
- 答案：False
- 解释： in 操作符用于检查 'mewtwo' 是否是字典 pokemon 中的一个键。由于 'mewtwo' 不是键，因此结果为 False。
'pikachu' in pokemon
- 答案：True
- 解释： in 操作符用于检查 'pikachu' 是否是字典 pokemon 中的一个键。因为 'pikachu' 是一个键，所以结果为 True。
25 in pokemon
- 答案：False
- 解释： in 操作符在字典中用于检查某个键是否存在，而不是值。25 是一个值，但不是键，因此结果为 False。
148 in pokemon.values()
- 答案：True
- 解释： pokemon.values() 返回字典中所有值的视图。由于 148 是其中一个值（对应键 'dragonair'），结果为 True。
151 in pokemon.keys()
- 答案：False
- 解释： pokemon.keys() 返回字典中所有键的视图。151 是一个值而非键，因此结果为 False。
'mew' in pokemon.keys()
- 答案：True
- 解释： pokemon.keys() 返回所有键的视图。'mew' 是字典中的一个键，因此结果为 True。

Practice

def divide(quotients, divisors):
    """Return a dictonary in which each quotient q is a key for the list of
    divisors that it divides evenly.

    >>> divide([3, 4, 5], [8, 9, 10, 11, 12])
    {3: [9, 12], 4: [8, 12], 5: [10]}
    >>> divide(range(1, 5), range(20, 25))
    {1: [20, 21, 22, 23, 24], 2: [20, 22, 24], 3: [21, 24], 4: [20, 24]}
    """
    return {q: [d for d in divisors if d % q == 0] for q in quotients}


def buy(fruits_to_buy, prices, total_amount):
    """Print ways to buy some of each fruit so that the sum of prices is amount.

    >>> prices = {'oranges': 4, 'apples': 3, 'bananas': 2, 'kiwis': 9}
    >>> buy(['apples', 'oranges', 'bananas'], prices, 12)  # We can only buy apple, orange, and banana, but not kiwi
    [2 apples][1 orange][1 banana]
    >>> buy(['apples', 'oranges', 'bananas'], prices, 16)
    [2 apples][1 orange][3 bananas]
    [2 apples][2 oranges][1 banana]
    >>> buy(['apples', 'kiwis'], prices, 36)
    [3 apples][3 kiwis]
    [6 apples][2 kiwis]
    [9 apples][1 kiwi]
    """
    def add(fruits, amount, cart):
        if fruits == [] and amount == 0:
            print(cart)
        elif fruits and amount > 0:
            fruit = fruits[0]
            price = prices[fruit]
            for k in range(1, amount // price + 1):
                # Hint: The display function will help you add fruit to the cart.
                add(fruits[1:], amount - price * k, cart + display(fruit, k))
    add(fruits_to_buy, total_amount, '')


def display(fruit, count):
    """Display a count of a fruit in square brackets.

    >>> display('apples', 3)
    '[3 apples]'
    >>> display('apples', 1)
    '[1 apple]'
    >>> print(display('apples', 3) + display('kiwis', 3))
    [3 apples][3 kiwis]
    """
    assert count >= 1 and fruit[-1] == 's'
    if count == 1:
        fruit = fruit[:-1]  # get rid of the plural s
    return '[' + str(count) + ' ' + fruit + ']'




from math import sqrt
def distance(city_a, city_b):
    """
    >>> city_a = make_city('city_a', 0, 1)
    >>> city_b = make_city('city_b', 0, 2)
    >>> distance(city_a, city_b)
    1.0
    >>> city_c = make_city('city_c', 6.5, 12)
    >>> city_d = make_city('city_d', 2.5, 15)
    >>> distance(city_c, city_d)
    5.0
    """
    "*** YOUR CODE HERE ***"
    x1 = get_lat(city_a)
    y1 = get_lon(city_a)
    x2 = get_lat(city_b)
    y2 = get_lon(city_b)
    return sqrt((x1 - x2)**2 + (y1 - y2)**2)

def closer_city(lat, lon, city_a, city_b):
    """
    Returns the name of either city_a or city_b, whichever is closest to
    coordinate (lat, lon). If the two cities are the same distance away
    from the coordinate, consider city_b to be the closer city.

    >>> berkeley = make_city('Berkeley', 37.87, 112.26)
    >>> stanford = make_city('Stanford', 34.05, 118.25)
    >>> closer_city(38.33, 121.44, berkeley, stanford)
    'Stanford'
    >>> bucharest = make_city('Bucharest', 44.43, 26.10)
    >>> vienna = make_city('Vienna', 48.20, 16.37)
    >>> closer_city(41.29, 174.78, bucharest, vienna)
    'Bucharest'
    """
    "*** YOUR CODE HERE ***"
    city = make_city('center', lat, lon)
    dis1 = distance(city, city_a)
    dis2 = distance(city, city_b)
    if dis1 < dis2:
        return get_name(city_a)
    else:
        return get_name(city_b)

def check_city_abstraction():
    """
    There's nothing for you to do for this function, it's just here for the extra doctest
    >>> change_abstraction(True)
    >>> city_a = make_city('city_a', 0, 1)
    >>> city_b = make_city('city_b', 0, 2)
    >>> distance(city_a, city_b)
    1.0
    >>> city_c = make_city('city_c', 6.5, 12)
    >>> city_d = make_city('city_d', 2.5, 15)
    >>> distance(city_c, city_d)
    5.0
    >>> berkeley = make_city('Berkeley', 37.87, 112.26)
    >>> stanford = make_city('Stanford', 34.05, 118.25)
    >>> closer_city(38.33, 121.44, berkeley, stanford)
    'Stanford'
    >>> bucharest = make_city('Bucharest', 44.43, 26.10)
    >>> vienna = make_city('Vienna', 48.20, 16.37)
    >>> closer_city(41.29, 174.78, bucharest, vienna)
    'Bucharest'
    >>> change_abstraction(False)
    """

# Treat all the following code as being behind an abstraction layer,
# you shouldn't need to look at it.
def make_city(name, lat, lon):
    """
    >>> city = make_city('Berkeley', 0, 1)
    >>> get_name(city)
    'Berkeley'
    >>> get_lat(city)
    0
    >>> get_lon(city)
    1
    """
    if change_abstraction.changed:
        return {"name" : name, "lat" : lat, "lon" : lon}
    else:
        return [name, lat, lon]

def get_name(city):
    """
    >>> city = make_city('Berkeley', 0, 1)
    >>> get_name(city)
    'Berkeley'
    """
    if change_abstraction.changed:
        return city["name"]
    else:
        return city[0]

def get_lat(city):
    """
    >>> city = make_city('Berkeley', 0, 1)
    >>> get_lat(city)
    0
    """
    if change_abstraction.changed:
        return city["lat"]
    else:
        return city[1]

def get_lon(city):
    """
    >>> city = make_city('Berkeley', 0, 1)
    >>> get_lon(city)
    1
    """
    if change_abstraction.changed:
        return city["lon"]
    else:
        return city[2]

###############


def change_abstraction(change):
    """
    For testing purposes.
    >>> change_abstraction(True)
    >>> change_abstraction.changed
    True
    """
    change_abstraction.changed = change

change_abstraction.changed = False

总结

还是对列表推导式的一个妙用，另外这里还引入了字典推导式，属于两者的混用。

def divide(quotients, divisors):
    """Return a dictonary in which each quotient q is a key for the list of
    divisors that it divides evenly.

    >>> divide([3, 4, 5], [8, 9, 10, 11, 12])
    {3: [9, 12], 4: [8, 12], 5: [10]}
    >>> divide(range(1, 5), range(20, 25))
    {1: [20, 21, 22, 23, 24], 2: [20, 22, 24], 3: [21, 24], 4: [20, 24]}
    """
    return {q: [d for d in divisors if d % q == 0] for q in quotients}

Python 支持字典推导式，其语法类似于列表推导式，但用于生成字典。字典推导式可以让我们通过简洁的方式构造字典。语法格式如下：
{key_expr: value_expr for item in iterable if condition}
其中：

key_expr 表示键的表达式。

value_expr 表示值的表达式。

iterable 是可迭代对象。

condition 是可选的条件，用于筛选符合条件的元素。

示例
生成简单字典
squares = {x: x**2 for x in range(1, 6)}
print(squares)  # 输出: {1: 1, 2: 4, 3: 9, 4: 16, 5: 25}
带条件的字典推导式
evens = {x: x**2 for x in range(1, 6) if x % 2 == 0}
print(evens)  # 输出: {2: 4, 4: 16}
从列表生成字典
fruits = ['apple', 'banana', 'cherry']
fruit_lengths = {fruit: len(fruit) for fruit in fruits}
print(fruit_lengths)  # 输出: {'apple': 5, 'banana': 6, 'cherry': 6}
交换键和值
original = {'a': 1, 'b': 2, 'c': 3}
inverted = {v: k for k, v in original.items()}
print(inverted)  # 输出: {1: 'a', 2: 'b', 3: 'c'}
字典推导式是 Python 中非常强大的特性，可以让代码更加简洁和可读。

先补充题目的要求：

Implement the buy function that takes three parameters: 实现带有三个参数的buy函数：
1. fruits_to_buy: A list of strings representing the fruits you need to buy. At least one of each fruit must be bought. fruits_to_buy ：代表您需要购买的水果的字符串列表。每种水果至少要买一个。
2. prices: A dictionary where the keys are fruit names (strings) and the values are positive integers representing the cost of each fruit. prices ：一个字典，其中键是水果名称（字符串），值是表示每种水果成本的正整数。
3. total_amount: An integer representing the total money available for purchasing the fruits. Take a look at the docstring for more details on the input structure. total_amount ：一个整数，表示可用于购买水果的总金额。有关输入结构的更多详细信息，请查看文档字符串。
The function should print all possible ways to buy the required fruits so that the combined cost equals total_amount. You can only select fruits mentioned in fruits_to_buy list. 该函数应该打印购买所需水果的所有可能方式，以便总成本等于total_amount 。您只能选择fruits_to_buy列表中提到的水果。

Note: You can use the display function to format the output. Call display(fruit, count) for each fruit and its corresponding quantity to generate a string showing the type and amount of fruit bought. 注意：您可以使用display功能来格式化输出。对每个水果及其对应的数量调用display(fruit, count) ，生成一个字符串，显示购买的水果的类型和数量。

Hint: How can you ensure that every combination includes at least one of each fruit listed in fruits_to_buy? 提示：如何确保每个组合至少包含fruits_to_buy中列出的每种水果中的一种？

解释：

cart这里是要输出的表达式，需要留意。

临界情况就是：水果种类用完和钱用完的情况，输出cart

一般情况：计算当前水果fruit[0]的所有可能情况（花费的金额小于amout），然后计算接下来水果的购买情况。

需要留意的是更新cart，使用cart + display(fruit, k)进行格式化。

def buy(fruits_to_buy, prices, total_amount):
    """Print ways to buy some of each fruit so that the sum of prices is amount.

    >>> prices = {'oranges': 4, 'apples': 3, 'bananas': 2, 'kiwis': 9}
    >>> buy(['apples', 'oranges', 'bananas'], prices, 12)  # We can only buy apple, orange, and banana, but not kiwi
    [2 apples][1 orange][1 banana]
    >>> buy(['apples', 'oranges', 'bananas'], prices, 16)
    [2 apples][1 orange][3 bananas]
    [2 apples][2 oranges][1 banana]
    >>> buy(['apples', 'kiwis'], prices, 36)
    [3 apples][3 kiwis]
    [6 apples][2 kiwis]
    [9 apples][1 kiwi]
    """
    #def add(fruits, amount, cart):
    #    if fruits == [] and amount == 0:
    #        print(cart)
    #    elif fruits and amount > 0:
    #        fruit = fruits[0]
    #        price = ____
    #        for k in ____:
    #            # Hint: The display function will help you add fruit to the cart.
    #            add(____, ____, ____)
    #add(fruits_to_buy, total_amount, '')

    # answer below
    def add(fruits, amount, cart):
        if fruits == [] and amount == 0:
            print(cart)
        elif fruits and amount > 0:
            fruit = fruits[0]
            price = prices[fruit]
            for k in range(1, amount // price + 1):
                # Hint: The display function will help you add fruit to the cart.
                add(fruits[1:], amount - price * k, cart + display(fruit, k))
    add(fruits_to_buy, total_amount, '')

lab05

WWPD1

=====================================================================
Assignment: Lab 5
OK, version v1.18.1
=====================================================================

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Unlocking tests

At each "? ", type what you would expect the output to be.
Type exit() to quit

---------------------------------------------------------------------
List Mutation > Suite 1 > Case 1
(cases remaining: 1)

What would Python display? If you get stuck, try it out in the Python
interpreter!

>>> # If nothing would be output by Python, type Nothing
>>> # If the code would error, type Error
>>> s = [6, 7, 8]
>>> print(s.append(6))
? None
-- OK! --

>>> s
? [6, 7, 8, 6]
-- OK! --

>>> s.insert(0, 9)
>>> s
? [9, 6, 7, 8, 6]
-- OK! --

>>> x = s.pop(1)
>>> s
? [9, 7, 8, 6]
-- OK! --

>>> s.remove(x)
>>> s
? [9, 7, 8]
-- OK! --

>>> a, b = s, s[:]
>>> a is s
? True
-- OK! --

>>> b == s
? True
-- OK! --

>>> b is s
? False
-- OK! --

>>> a.pop()
? 8
-- OK! --

>>> a + b
? [9, 7, 9, 7, 8]
-- OK! --

>>> s = [3]
>>> s.extend([4, 5])
>>> s
? [3, 4, 5]
-- OK! --

>>> a
? [9, 7]
-- OK! --

>>> s.extend([s.append(9), s.append(10)])
>>> s
? [3, 4, 5, 9, 10, None, None]
-- OK! --

---------------------------------------------------------------------
OK! All cases for List Mutation unlocked.

Backup... 100% complete

答案解释 1

以下是每道题的解释：

print(s.append(6))
- 答案：None
- 解释： append 方法将 6 添加到列表 s 的末尾，但它本身不返回任何值（返回 None），因此 print 输出 None。
s
- 答案：[6, 7, 8, 6]
- 解释： 刚才 append(6) 将 6 添加到了 s 的末尾，所以 s 现在是 [6, 7, 8, 6]。
s.insert(0, 9) 和 s
- 答案：[9, 6, 7, 8, 6]
- 解释： insert(0, 9) 在索引 0 位置插入 9，使 s 变为 [9, 6, 7, 8, 6]。
x = s.pop(1) 和 s
- 答案：[9, 7, 8, 6]
- 解释： pop(1) 删除并返回索引 1 位置的元素 6，使得 s 更新为 [9, 7, 8, 6]，且 x 为 6。
s.remove(x) 和 s
- 答案：[9, 7, 8]
- 解释： remove(x) 从列表中移除第一个值为 x 的元素，即 6，所以 s 变为 [9, 7, 8]。
a, b = s, s[:] 和 a is s
- 答案：True
- 解释： a 和 s 指向同一个对象，因此 a is s 为 True。
b == s
- 答案：True
- 解释： b 是 s 的一个副本，因此 b 的值与 s 相等，所以 b == s 为 True。
b is s
- 答案：False
- 解释： b 是 s 的一个浅拷贝，不是同一个对象，因此 b is s 为 False。
a.pop()
- 答案：8
- 解释： pop() 移除并返回列表的最后一个元素 8，所以结果是 8。
a + b
- 答案：[9, 7, 9, 7, 8]
- 解释： a 现在是 [9, 7]，而 b 是 [9, 7, 8]。a + b 是两个列表的连接，结果为 [9, 7, 9, 7, 8]。
s = [3] 和 s.extend([4, 5]) 和 s
- 答案：[3, 4, 5]
- 解释： extend 方法将 [4, 5] 添加到 s 的末尾，所以 s 变为 [3, 4, 5]。
a
- 答案：[9, 7]
- 解释： a 没有被修改过，所以仍然是 [9, 7]。
s.extend([s.append(9), s.append(10)]) 和 s
- 答案：[3, 4, 5, 9, 10, None, None]
- 解释： s.append(9) 和 s.append(10) 各自会将 9 和 10 添加到列表 s 中，但 append 方法返回 None，所以 s.extend([None, None]) 也会添加两个 None。最终，s 为 [3, 4, 5, 9, 10, None, None]。

WWPD2

=====================================================================
Assignment: Lab 5
OK, version v1.18.1
=====================================================================

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Unlocking tests

At each "? ", type what you would expect the output to be.
Type exit() to quit

---------------------------------------------------------------------
Iterators > Suite 1 > Case 1
(cases remaining: 3)

What would Python display? If you get stuck, try it out in the Python
interpreter!

>>> # Enter StopIteration if StopIteration exception occurs, Error for other errors
>>> # Enter Iterator if the output is an iterator object.
>>> s = [1, 2, 3, 4]
>>> t = iter(s)
>>> next(s)
? Error
-- OK! --

>>> next(t)
? 1
-- OK! --

>>> next(t)
? 2
-- OK! --

>>> next(iter(s))
? 1
-- OK! --

>>> next(iter(s))
? 1
-- OK! --

>>> next(t)
? 3
-- OK! --

>>> next(t)
? 4
-- OK! --

---------------------------------------------------------------------
Iterators > Suite 1 > Case 2
(cases remaining: 2)

What would Python display? If you get stuck, try it out in the Python
interpreter!

>>> r = range(6)
>>> r_iter = iter(r)
>>> next(r_iter)
? 0
-- OK! --

>>> [x + 1 for x in r]
? [1, 2, 3, 4, 5, 6]
-- OK! --

>>> [x + 1 for x in r_iter]
? [2, 3, 4, 5, 6]
-- OK! --

>>> next(r_iter)
? StopIteration
-- OK! --

---------------------------------------------------------------------
Iterators > Suite 1 > Case 3
(cases remaining: 1)

What would Python display? If you get stuck, try it out in the Python
interpreter!

>>> map_iter = map(lambda x : x + 10, range(5))
>>> next(map_iter)
? 10
-- OK! --

>>> next(map_iter)
? 11
-- OK! --

>>> list(map_iter)
? [12, 13, 14]
-- OK! --

>>> for e in filter(lambda x : x % 4 == 0, range(1000, 1008)):
...     print(e)
(line 1)? 1000
(line 2)? 1004
-- OK! --

>>> [x + y for x, y in zip([1, 2, 3], [4, 5, 6])]
? [5, 7, 9]
-- OK! --

---------------------------------------------------------------------
OK! All cases for Iterators unlocked.

Backup... 100% complete

答案解释 2

以下是每道题的中文解释：

Case 1

next(s)
- 答案：Error
- 解释： next() 需要一个迭代器对象，但 s 是一个列表，不是迭代器，所以会引发 TypeError。
next(t)
- 答案：1
- 解释： t 是 s 的迭代器，调用 next(t) 返回 s 中的第一个元素 1。
next(t)
- 答案：2
- 解释： 再次调用 next(t) 返回 s 中的第二个元素 2。
next(iter(s))
- 答案：1
- 解释： iter(s) 创建 s 的新迭代器，调用 next() 返回第一个元素 1。
next(iter(s))
- 答案：1
- 解释： 同上，再次创建 s 的新迭代器，next() 返回第一个元素 1。
next(t)
- 答案：3
- 解释： t 已经迭代到 s 中的第三个元素 3，因此 next(t) 返回 3。
next(t)
- 答案：4
- 解释： t 现在返回 s 中的第四个元素 4。

Case 2

next(r_iter)
- 答案：0
- 解释： r_iter 是 range(6) 的迭代器，next(r_iter) 返回第一个元素 0。
[x + 1 for x in r]
- 答案：[1, 2, 3, 4, 5, 6]
- 解释： 列表推导式会对 r 的每个元素加 1，结果是 [1, 2, 3, 4, 5, 6]。
[x + 1 for x in r_iter]
- 答案：[2, 3, 4, 5, 6]
- 解释： 因为 r_iter 已经被迭代过一次，当前指向 1 后的元素，故结果为 [2, 3, 4, 5, 6]。
next(r_iter)
- 答案：StopIteration
- 解释： r_iter 已经被完全迭代，调用 next() 时会引发 StopIteration。

Case 3

next(map_iter)
- 答案：10
- 解释： map_iter 应用 lambda x: x + 10 到 range(5)，第一个元素是 10。
next(map_iter)
- 答案：11
- 解释： map_iter 的下一个元素是 1 + 10 = 11。
list(map_iter)
- 答案：[12, 13, 14]
- 解释： map_iter 已经迭代到 2 开始的元素，剩余元素 12、13 和 14 转换为列表。
for e in filter(lambda x: x % 4 == 0, range(1000, 1008))
- 答案：1000, 1004
- 解释： filter 返回 range(1000, 1008) 中能被 4 整除的数，所以打印 1000 和 1004。
[x + y for x, y in zip([1, 2, 3], [4, 5, 6])]
- 答案：[5, 7, 9]
- 解释： zip 配对两个列表元素，逐对相加，得到 [5, 7, 9]。

这些题目测试了迭代器和生成器在 Python 中的使用，以及如何应用 next() 函数和 map、filter 等函数的操作。

Practice

HW_SOURCE_FILE=__file__


def insert_items(s, before, after):
    """Insert after into s after each occurrence of before and then return s.

    >>> test_s = [1, 5, 8, 5, 2, 3]
    >>> new_s = insert_items(test_s, 5, 7)
    >>> new_s
    [1, 5, 7, 8, 5, 7, 2, 3]
    >>> test_s
    [1, 5, 7, 8, 5, 7, 2, 3]
    >>> new_s is test_s
    True
    >>> double_s = [1, 2, 1, 2, 3, 3]
    >>> double_s = insert_items(double_s, 3, 4)
    >>> double_s
    [1, 2, 1, 2, 3, 4, 3, 4]
    >>> large_s = [1, 4, 8]
    >>> large_s2 = insert_items(large_s, 4, 4)
    >>> large_s2
    [1, 4, 4, 8]
    >>> large_s3 = insert_items(large_s2, 4, 6)
    >>> large_s3
    [1, 4, 6, 4, 6, 8]
    >>> large_s3 is large_s
    True
    """
    "*** YOUR CODE HERE ***"
    index = 0
    while index < len(s):
        if s[index] == before:
            s.insert(index + 1, after)
            index += 1
        index += 1
    return s


def group_by(s, fn):
    """Return a dictionary of lists that together contain the elements of s.
    The key for each list is the value that fn returns when called on any of the
    values of that list.

    >>> group_by([12, 23, 14, 45], lambda p: p // 10)
    {1: [12, 14], 2: [23], 4: [45]}
    >>> group_by(range(-3, 4), lambda x: x * x)
    {9: [-3, 3], 4: [-2, 2], 1: [-1, 1], 0: [0]}
    """
    grouped = {}
    for value in s:
        key = fn(value)
        if key in grouped:
            grouped[key].append(value)
        else:
            grouped[key] = [value]
    return grouped


def count_occurrences(t, n, x):
    """Return the number of times that x is equal to one of the
    first n elements of iterator t.

    >>> s = iter([10, 9, 10, 9, 9, 10, 8, 8, 8, 7])
    >>> count_occurrences(s, 10, 9)
    3
    >>> t = iter([10, 9, 10, 9, 9, 10, 8, 8, 8, 7])
    >>> count_occurrences(t, 3, 10)
    2
    >>> u = iter([3, 2, 2, 2, 1, 2, 1, 4, 4, 5, 5, 5])
    >>> count_occurrences(u, 1, 3)  # Only iterate over 3
    1
    >>> count_occurrences(u, 3, 2)  # Only iterate over 2, 2, 2
    3
    >>> list(u)                     # Ensure that the iterator has advanced the right amount
    [1, 2, 1, 4, 4, 5, 5, 5]
    >>> v = iter([4, 1, 6, 6, 7, 7, 6, 6, 2, 2, 2, 5])
    >>> count_occurrences(v, 6, 6)
    2
    """
    "*** YOUR CODE HERE ***"
    index = 0
    cnt = 0
    while index < n:
        if next(t) == x:
            cnt += 1
        index += 1
    return cnt


def repeated(t, k):
    """Return the first value in iterator t that appears k times in a row,
    calling next on t as few times as possible.

    >>> s = iter([10, 9, 10, 9, 9, 10, 8, 8, 8, 7])
    >>> repeated(s, 2)
    9
    >>> t = iter([10, 9, 10, 9, 9, 10, 8, 8, 8, 7])
    >>> repeated(t, 3)
    8
    >>> u = iter([3, 2, 2, 2, 1, 2, 1, 4, 4, 5, 5, 5])
    >>> repeated(u, 3)
    2
    >>> repeated(u, 3)
    5
    >>> v = iter([4, 1, 6, 6, 7, 7, 8, 8, 2, 2, 2, 5])
    >>> repeated(v, 3)
    2
    """
    assert k > 1
    "*** YOUR CODE HERE ***"
    cnt = 0
    last_val = None
    while True:
        val = next(t)
        if val == last_val:
            cnt += 1
        else:
            last_val = val
            cnt = 1
        if cnt == k:
            return last_val


def sprout_leaves(t, leaves):
    """Sprout new leaves containing the labels in leaves at each leaf of
    the original tree t and return the resulting tree.

    >>> t1 = tree(1, [tree(2), tree(3)])
    >>> print_tree(t1)
    1
      2
      3
    >>> new1 = sprout_leaves(t1, [4, 5])
    >>> print_tree(new1)
    1
      2
        4
        5
      3
        4
        5

    >>> t2 = tree(1, [tree(2, [tree(3)])])
    >>> print_tree(t2)
    1
      2
        3
    >>> new2 = sprout_leaves(t2, [6, 1, 2])
    >>> print_tree(new2)
    1
      2
        3
          6
          1
          2
    """
    "*** YOUR CODE HERE ***"
    if is_leaf(t):
        return tree(label(t), [tree(x) for x in leaves])
    return tree(label(t), [sprout_leaves(x, leaves) for x in branches(t)])

def partial_reverse(s, start):
    """Reverse part of a list in-place, starting with start up to the end of
    the list.

    >>> a = [1, 2, 3, 4, 5, 6, 7]
    >>> partial_reverse(a, 2)
    >>> a
    [1, 2, 7, 6, 5, 4, 3]
    >>> partial_reverse(a, 5)
    >>> a
    [1, 2, 7, 6, 5, 3, 4]
    """
    "*** YOUR CODE HERE ***"
    i = start
    j = len(s) - 1
    while i <= j:
        s[i], s[j] = s[j], s[i]
        i += 1
        j -= 1


# Tree Data Abstraction

def tree(label, branches=[]):
    """Construct a tree with the given label value and a list of branches."""
    for branch in branches:
        assert is_tree(branch), 'branches must be trees'
    return [label] + list(branches)

def label(tree):
    """Return the label value of a tree."""
    return tree[0]

def branches(tree):
    """Return the list of branches of the given tree."""
    return tree[1:]

def is_tree(tree):
    """Returns True if the given tree is a tree, and False otherwise."""
    if type(tree) != list or len(tree) < 1:
        return False
    for branch in branches(tree):
        if not is_tree(branch):
            return False
    return True

def is_leaf(tree):
    """Returns True if the given tree's list of branches is empty, and False
    otherwise.
    """
    return not branches(tree)

def print_tree(t, indent=0):
    """Print a representation of this tree in which each node is
    indented by two spaces times its depth from the root.

    >>> print_tree(tree(1))
    1
    >>> print_tree(tree(1, [tree(2)]))
    1
      2
    >>> numbers = tree(1, [tree(2), tree(3, [tree(4), tree(5)]), tree(6, [tree(7)])])
    >>> print_tree(numbers)
    1
      2
      3
        4
        5
      6
        7
    """
    print('  ' * indent + str(label(t)))
    for b in branches(t):
        print_tree(b, indent + 1)

def copy_tree(t):
    """Returns a copy of t. Only for testing purposes.

    >>> t = tree(5)
    >>> copy = copy_tree(t)
    >>> t = tree(6)
    >>> print_tree(copy)
    5
    """
    return tree(label(t), [copy_tree(b) for b in branches(t)])

总结

这道题需要留意使用s.insert(index, value)，表示在index位置插入value值，需要留意的是由于插入后发生了修改，所以需要多进行一次index += 1。

def insert_items(s, before, after):
    """Insert after into s after each occurrence of before and then return s.

    >>> test_s = [1, 5, 8, 5, 2, 3]
    >>> new_s = insert_items(test_s, 5, 7)
    >>> new_s
    [1, 5, 7, 8, 5, 7, 2, 3]
    >>> test_s
    [1, 5, 7, 8, 5, 7, 2, 3]
    >>> new_s is test_s
    True
    >>> double_s = [1, 2, 1, 2, 3, 3]
    >>> double_s = insert_items(double_s, 3, 4)
    >>> double_s
    [1, 2, 1, 2, 3, 4, 3, 4]
    >>> large_s = [1, 4, 8]
    >>> large_s2 = insert_items(large_s, 4, 4)
    >>> large_s2
    [1, 4, 4, 8]
    >>> large_s3 = insert_items(large_s2, 4, 6)
    >>> large_s3
    [1, 4, 6, 4, 6, 8]
    >>> large_s3 is large_s
    True
    """
    "*** YOUR CODE HERE ***"
    index = 0
    while index < len(s):
        if s[index] == before:
            s.insert(index + 1, after)
            index += 1
        index += 1
    return s

有个小细节：注意这里是在字典中创建列表，所以当key不在列表中时，需要手动创建一个列表。

如果key已经在列表中：直接添加到列表末尾即可。

def group_by(s, fn):
    """Return a dictionary of lists that together contain the elements of s.
    The key for each list is the value that fn returns when called on any of the
    values of that list.

    >>> group_by([12, 23, 14, 45], lambda p: p // 10)
    {1: [12, 14], 2: [23], 4: [45]}
    >>> group_by(range(-3, 4), lambda x: x * x)
    {9: [-3, 3], 4: [-2, 2], 1: [-1, 1], 0: [0]}
    """
    grouped = {}
    for value in s:
        key = fn(value)
        if key in grouped:
            grouped[key].append(value)
        else:
            grouped[key] = [value]
    return grouped

这道题需要看一下前后提示：

Implement repeated, which takes in an iterator t and an integer k greater than 1. It returns the first value in t that appears k times in a row. You may assume that there is an element of t repeated at least k times in a row. 实现repeated ，它接受一个迭代器t和一个大于 1 的整数k 。它返回t中连续出现k次的第一个值。您可以假设t中有一个元素连续重复至少k次。

Important: Call next on t only the minimum number of times required. If you are receiving a StopIteration exception, your repeated function is calling next too many times. 重要提示：仅调用next on t所需的最少次数。如果您收到StopIteration异常，则说明您的repeated函数调用next次数过多。

因为已经保证是有解的了：所以可以这样实现：

记录一个last_val，如果当前val和last_val相同，更新记录cnt，否则进行重置，直到cnt==k为止。

不需要担心收到StopIteration异常。

def repeated(t, k):
    """Return the first value in iterator t that appears k times in a row,
    calling next on t as few times as possible.

    >>> s = iter([10, 9, 10, 9, 9, 10, 8, 8, 8, 7])
    >>> repeated(s, 2)
    9
    >>> t = iter([10, 9, 10, 9, 9, 10, 8, 8, 8, 7])
    >>> repeated(t, 3)
    8
    >>> u = iter([3, 2, 2, 2, 1, 2, 1, 4, 4, 5, 5, 5])
    >>> repeated(u, 3)
    2
    >>> repeated(u, 3)
    5
    >>> v = iter([4, 1, 6, 6, 7, 7, 8, 8, 2, 2, 2, 5])
    >>> repeated(v, 3)
    2
    """
    assert k > 1
    "*** YOUR CODE HERE ***"
    cnt = 0
    last_val = None
    while True:
        val = next(t)
        if val == last_val:
            cnt += 1
        else:
            last_val = val
            cnt = 1
        if cnt == k:
            return last_val

注意这里的tree本质上还是一个列表，我们围绕列表进行分析：

临界情况：根据题意在叶子进行添加树，当当前节点是叶子时，可以使用列表推导式对其进行扩展（使用tree的构造方法）。

一般情况：我们对当前节点的每个分支进行递归处理即可，可以使用列表推导式完成

def sprout_leaves(t, leaves):
    """Sprout new leaves containing the labels in leaves at each leaf of
    the original tree t and return the resulting tree.

    >>> t1 = tree(1, [tree(2), tree(3)])
    >>> print_tree(t1)
    1
      2
      3
    >>> new1 = sprout_leaves(t1, [4, 5])
    >>> print_tree(new1)
    1
      2
        4
        5
      3
        4
        5

    >>> t2 = tree(1, [tree(2, [tree(3)])])
    >>> print_tree(t2)
    1
      2
        3
    >>> new2 = sprout_leaves(t2, [6, 1, 2])
    >>> print_tree(new2)
    1
      2
        3
          6
          1
          2
    """
    "*** YOUR CODE HERE ***"
    if is_leaf(t):
        return tree(label(t), [tree(x) for x in leaves])
    return tree(label(t), [sprout_leaves(x, leaves) for x in branches(t)])

使用交换即可，通过双指针实现：

def partial_reverse(s, start):
    """Reverse part of a list in-place, starting with start up to the end of
    the list.

    >>> a = [1, 2, 3, 4, 5, 6, 7]
    >>> partial_reverse(a, 2)
    >>> a
    [1, 2, 7, 6, 5, 4, 3]
    >>> partial_reverse(a, 5)
    >>> a
    [1, 2, 7, 6, 5, 3, 4]
    """
    "*** YOUR CODE HERE ***"
    i = start
    j = len(s) - 1
    while i <= j:
        s[i], s[j] = s[j], s[i]
        i += 1
        j -= 1

lab06

无WWPD。

Practice

class Transaction:
    def __init__(self, id, before, after):
        self.id = id
        self.before = before
        self.after = after

    def changed(self):
        """Return whether the transaction resulted in a changed balance."""
        "*** YOUR CODE HERE ***"
        if self.before != self.after:
            return True
        else:
            return False

    def report(self):
        """Return a string describing the transaction.

        >>> Transaction(3, 20, 10).report()
        '3: decreased 20->10'
        >>> Transaction(4, 20, 50).report()
        '4: increased 20->50'
        >>> Transaction(5, 50, 50).report()
        '5: no change'
        """
        msg = 'no change'
        if self.changed():
            "*** YOUR CODE HERE ***"
            if self.before > self.after:
                msg = 'decreased ' + str(self.before) + '->' + str(self.after)
            else:
                msg = 'increased ' + str(self.before) + '->' + str(self.after)
        return str(self.id) + ': ' + msg

class BankAccount:
    """A bank account that tracks its transaction history.

    >>> a = BankAccount('Eric')
    >>> a.deposit(100)    # Transaction 0 for a
    100
    >>> b = BankAccount('Erica')
    >>> a.withdraw(30)    # Transaction 1 for a
    70
    >>> a.deposit(10)     # Transaction 2 for a
    80
    >>> b.deposit(50)     # Transaction 0 for b
    50
    >>> b.withdraw(10)    # Transaction 1 for b
    40
    >>> a.withdraw(100)   # Transaction 3 for a
    'Insufficient funds'
    >>> len(a.transactions)
    4
    >>> len([t for t in a.transactions if t.changed()])
    3
    >>> for t in a.transactions:
    ...     print(t.report())
    0: increased 0->100
    1: decreased 100->70
    2: increased 70->80
    3: no change
    >>> b.withdraw(100)   # Transaction 2 for b
    'Insufficient funds'
    >>> b.withdraw(30)    # Transaction 3 for b
    10
    >>> for t in b.transactions:
    ...     print(t.report())
    0: increased 0->50
    1: decreased 50->40
    2: no change
    3: decreased 40->10
    """
    #*** YOU NEED TO MAKE CHANGES IN SEVERAL PLACES IN THIS CLASS ***
    def next_id(self):
        self.count += 1
        return self.count

    def __init__(self, account_holder):
        self.balance = 0
        self.holder = account_holder
        self.transactions = []
        self.count = -1

    def deposit(self, amount):
        """Increase the account balance by amount, add the deposit
        to the transaction history, and return the new balance.
        """
        self.transactions.append(Transaction(self.next_id(), self.balance, self.balance + amount))
        self.balance = self.balance + amount
        return self.balance

    def withdraw(self, amount):
        """Decrease the account balance by amount, add the withdraw
        to the transaction history, and return the new balance.
        """
        if amount > self.balance:
            self.transactions.append(Transaction(self.next_id(), self.balance, self.balance))
            return 'Insufficient funds'
        self.transactions.append(Transaction(self.next_id(), self.balance, self.balance - amount))
        self.balance = self.balance - amount
        return self.balance

    # another solution
    # def next_id(self):
    #     # There are many ways to implement this counter, such as using an instance
    #     # attribute to track the next ID.
    #     return len(self.transactions)

    # def __init__(self, account_holder):
    #     self.balance = 0
    #     self.holder = account_holder
    #     self.transactions = []
    # def deposit(self, amount):
    #     """Increase the account balance by amount, add the deposit
    #     to the transaction history, and return the new balance.
    #     """
    #     self.transactions.append(Transaction(self.next_id(), self.balance, self.balance + amount))
    #     self.balance = self.balance + amount
    #     return self.balance

    # def withdraw(self, amount):
    #     """Decrease the account balance by amount, add the withdraw
    #     to the transaction history, and return the new balance.
    #     """
    #     if amount > self.balance:
    #         self.transactions.append(Transaction(self.next_id(), self.balance, self.balance))
    #         return 'Insufficient funds'
    #     self.transactions.append(Transaction(self.next_id(), self.balance, self.balance - amount))
    #     self.balance = self.balance - amount
    #     return self.balance


class Email:
    """An email has the following instance attributes:

        msg (str): the contents of the message
        sender (Client): the client that sent the email
        recipient_name (str): the name of the recipient (another client)
    """
    def __init__(self, msg, sender, recipient_name):
        self.msg = msg
        self.sender = sender
        self.recipient_name = recipient_name

class Server:
    """Each Server has one instance attribute called clients that is a
    dictionary from client names to client objects.
    """
    def __init__(self):
        self.clients = {}

    def send(self, email):
        """Append the email to the inbox of the client it is addressed to.
            email is an instance of the Email class.
        """
        self.clients[email.recipient_name].inbox.append(email)

    def register_client(self, client):
        """Add a client to the clients mapping (which is a
        dictionary from client names to client instances).
            client is an instance of the Client class.
        """
        self.clients[client.name] = client

class Client:
    """A client has a server, a name (str), and an inbox (list).

    >>> s = Server()
    >>> a = Client(s, 'Alice')
    >>> b = Client(s, 'Bob')
    >>> a.compose('Hello, World!', 'Bob')
    >>> b.inbox[0].msg
    'Hello, World!'
    >>> a.compose('CS 61A Rocks!', 'Bob')
    >>> len(b.inbox)
    2
    >>> b.inbox[1].msg
    'CS 61A Rocks!'
    >>> b.inbox[1].sender.name
    'Alice'
    """
    def __init__(self, server, name):
        self.inbox = []
        self.server = server
        self.name = name
        server.register_client(self)

    def compose(self, message, recipient_name):
        """Send an email with the given message to the recipient."""
        email = Email(message, self, recipient_name)
        self.server.send(email)


class Mint:
    """A mint creates coins by stamping on years.

    The update method sets the mint's stamp to Mint.present_year.

    >>> mint = Mint()
    >>> mint.year
    2024
    >>> dime = mint.create(Dime)
    >>> dime.year
    2024
    >>> Mint.present_year = 2104  # Time passes
    >>> nickel = mint.create(Nickel)
    >>> nickel.year     # The mint has not updated its stamp yet
    2024
    >>> nickel.worth()  # 5 cents + (80 - 50 years)
    35
    >>> mint.update()   # The mint's year is updated to 2104
    >>> Mint.present_year = 2179     # More time passes
    >>> mint.create(Dime).worth()    # 10 cents + (75 - 50 years)
    35
    >>> Mint().create(Dime).worth()  # A new mint has the current year
    10
    >>> dime.worth()     # 10 cents + (155 - 50 years)
    115
    >>> Dime.cents = 20  # Upgrade all dimes!
    >>> dime.worth()     # 20 cents + (155 - 50 years)
    125
    """
    present_year = 2024

    def __init__(self):
        self.update()

    def create(self, coin):
        "*** YOUR CODE HERE ***"
        return coin(self.year)


    def update(self):
        "*** YOUR CODE HERE ***"
        self.year = self.present_year

class Coin:
    cents = None # will be provided by subclasses, but not by Coin itself

    def __init__(self, year):
        self.year = year

    def worth(self):
        "*** YOUR CODE HERE ***"
        delta = Mint.present_year - self.year
        return self.cents + max(0, delta - 50)

class Nickel(Coin):
    cents = 5

class Dime(Coin):
    cents = 10

总结

Transaction不难，关键在于BankAccount的修改：可以留意的是需要进行交易记录的保存，所以我们添加一个self.transactions = []，由于还需要记录交易记录ID，所以设计一个函数next_id，和一个变量self.count，用于跟踪交易次数。

deposit和withdraw函数根据要求实现即可，没有什么值得特别留意的地方。

class Transaction:
    def __init__(self, id, before, after):
        self.id = id
        self.before = before
        self.after = after

    def changed(self):
        """Return whether the transaction resulted in a changed balance."""
        "*** YOUR CODE HERE ***"
        if self.before != self.after:
            return True
        else:
            return False

    def report(self):
        """Return a string describing the transaction.

        >>> Transaction(3, 20, 10).report()
        '3: decreased 20->10'
        >>> Transaction(4, 20, 50).report()
        '4: increased 20->50'
        >>> Transaction(5, 50, 50).report()
        '5: no change'
        """
        msg = 'no change'
        if self.changed():
            "*** YOUR CODE HERE ***"
            if self.before > self.after:
                msg = 'decreased ' + str(self.before) + '->' + str(self.after)
            else:
                msg = 'increased ' + str(self.before) + '->' + str(self.after)
        return str(self.id) + ': ' + msg

class BankAccount:
    """A bank account that tracks its transaction history.

    >>> a = BankAccount('Eric')
    >>> a.deposit(100)    # Transaction 0 for a
    100
    >>> b = BankAccount('Erica')
    >>> a.withdraw(30)    # Transaction 1 for a
    70
    >>> a.deposit(10)     # Transaction 2 for a
    80
    >>> b.deposit(50)     # Transaction 0 for b
    50
    >>> b.withdraw(10)    # Transaction 1 for b
    40
    >>> a.withdraw(100)   # Transaction 3 for a
    'Insufficient funds'
    >>> len(a.transactions)
    4
    >>> len([t for t in a.transactions if t.changed()])
    3
    >>> for t in a.transactions:
    ...     print(t.report())
    0: increased 0->100
    1: decreased 100->70
    2: increased 70->80
    3: no change
    >>> b.withdraw(100)   # Transaction 2 for b
    'Insufficient funds'
    >>> b.withdraw(30)    # Transaction 3 for b
    10
    >>> for t in b.transactions:
    ...     print(t.report())
    0: increased 0->50
    1: decreased 50->40
    2: no change
    3: decreased 40->10
    """
    # *** YOU NEED TO MAKE CHANGES IN SEVERAL PLACES IN THIS CLASS ***
	#def __init__(self, account_holder):
    #    self.balance = 0
    #    self.holder = account_holder

    #def deposit(self, amount):
    #    """Increase the account balance by amount, add the deposit
    #    to the transaction history, and return the new balance.
    #    """
    #    self.balance = self.balance + amount
    #    return self.balance

    #def withdraw(self, amount):
    #    """Decrease the account balance by amount, add the withdraw
    #    to the transaction history, and return the new balance.
    #    """
    #    if amount > self.balance:
    #        return 'Insufficient funds'
    #    self.balance = self.balance - amount
    #    return self.balance

    # answer below
    #*** YOU NEED TO MAKE CHANGES IN SEVERAL PLACES IN THIS CLASS ***
    def next_id(self):
        self.count += 1
        return self.count

    def __init__(self, account_holder):
        self.balance = 0
        self.holder = account_holder
        self.transactions = []
        self.count = -1

    def deposit(self, amount):
        """Increase the account balance by amount, add the deposit
        to the transaction history, and return the new balance.
        """
        self.transactions.append(Transaction(self.next_id(), self.balance, self.balance + amount))
        self.balance = self.balance + amount
        return self.balance

    def withdraw(self, amount):
        """Decrease the account balance by amount, add the withdraw
        to the transaction history, and return the new balance.
        """
        if amount > self.balance:
            self.transactions.append(Transaction(self.next_id(), self.balance, self.balance))
            return 'Insufficient funds'
        self.transactions.append(Transaction(self.next_id(), self.balance, self.balance - amount))
        self.balance = self.balance - amount
        return self.balance

    # another solution
    # def next_id(self):
    #     # There are many ways to implement this counter, such as using an instance
    #     # attribute to track the next ID.
    #     return len(self.transactions)

    # def __init__(self, account_holder):
    #     self.balance = 0
    #     self.holder = account_holder
    #     self.transactions = []
    # def deposit(self, amount):
    #     """Increase the account balance by amount, add the deposit
    #     to the transaction history, and return the new balance.
    #     """
    #     self.transactions.append(Transaction(self.next_id(), self.balance, self.balance + amount))
    #     self.balance = self.balance + amount
    #     return self.balance

    # def withdraw(self, amount):
    #     """Decrease the account balance by amount, add the withdraw
    #     to the transaction history, and return the new balance.
    #     """
    #     if amount > self.balance:
    #         self.transactions.append(Transaction(self.next_id(), self.balance, self.balance))
    #         return 'Insufficient funds'
    #     self.transactions.append(Transaction(self.next_id(), self.balance, self.balance - amount))
    #     self.balance = self.balance - amount
    #     return self.balance

主要是create方法：需要调用coin构造函数创建一个对象，并且返回该实例。

worth需要留意的是不要修改它的原始价值，返回的价值是根据年份差计算得到的。

class Mint:
    """A mint creates coins by stamping on years.

    The update method sets the mint's stamp to Mint.present_year.

    >>> mint = Mint()
    >>> mint.year
    2024
    >>> dime = mint.create(Dime)
    >>> dime.year
    2024
    >>> Mint.present_year = 2104  # Time passes
    >>> nickel = mint.create(Nickel)
    >>> nickel.year     # The mint has not updated its stamp yet
    2024
    >>> nickel.worth()  # 5 cents + (80 - 50 years)
    35
    >>> mint.update()   # The mint's year is updated to 2104
    >>> Mint.present_year = 2179     # More time passes
    >>> mint.create(Dime).worth()    # 10 cents + (75 - 50 years)
    35
    >>> Mint().create(Dime).worth()  # A new mint has the current year
    10
    >>> dime.worth()     # 10 cents + (155 - 50 years)
    115
    >>> Dime.cents = 20  # Upgrade all dimes!
    >>> dime.worth()     # 20 cents + (155 - 50 years)
    125
    """
    present_year = 2024

    def __init__(self):
        self.update()

    def create(self, coin):
        "*** YOUR CODE HERE ***"
        return coin(self.year)


    def update(self):
        "*** YOUR CODE HERE ***"
        self.year = self.present_year

class Coin:
    cents = None # will be provided by subclasses, but not by Coin itself

    def __init__(self, year):
        self.year = year

    def worth(self):
        "*** YOUR CODE HERE ***"
        delta = Mint.present_year - self.year
        return self.cents + max(0, delta - 50)

class Nickel(Coin):
    cents = 5

class Dime(Coin):
    cents = 10

lab07

WWPD

=====================================================================
Assignment: Lab 7
OK, version v1.18.1
=====================================================================

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Unlocking tests

At each "? ", type what you would expect the output to be.
Type exit() to quit

---------------------------------------------------------------------
Inheritance ABCs > Suite 1 > Case 1
(cases remaining: 1)

What would Python display? If you get stuck, try it out in the Python
interpreter!

>>> class A:
...   x, y = 0, 0
...   def __init__(self):
...         return
>>> class B(A):
...   def __init__(self):
...         return
>>> class C(A):
...   def __init__(self):
...         return
>>> print(A.x, B.x, C.x)
? 0 0 0
-- OK! --

>>> B.x = 2
>>> print(A.x, B.x, C.x)
? 0 2 0
-- OK! --

>>> A.x += 1
>>> print(A.x, B.x, C.x)
? 1 2 1
-- OK! --

>>> obj = C()
>>> obj.y = 1
>>> C.y == obj.y
? False
-- OK! --

>>> A.y = obj.y
>>> print(A.y, B.y, C.y, obj.y)
? 1 1 1 1
-- OK! --

---------------------------------------------------------------------
OK! All cases for Inheritance ABCs unlocked.

Backup... 100% complete

其实还有，但是忘记截取下来了，重要性也比较低。

答案解释

以下是每道题的解释：

print(A.x, B.x, C.x)
- 答案：0 0 0
- 解释： A 是基类，B 和 C 是继承 A 的子类。初始时，x 的值在所有类中都是 0。
B.x = 2
- 答案：0 2 0
- 解释： 这一行代码将 B 类中的 x 属性设置为 2，此时 A 和 C 中的 x 值保持不变，分别为 0。
A.x += 1
- 答案：1 2 1
- 解释： A.x += 1 修改 A 类的 x 值，将其增加到 1。由于 B 有独立的 x 值，因此不受影响，B.x 依然为 2。C 类继承 A 的 x，所以其 x 值也更新为 1。
obj = C() 和 obj.y = 1
- 答案：False
- 解释： obj 是 C 类的一个实例。通过 obj.y = 1，我们为该实例 obj 的 y 属性赋值为 1，这是 obj 的一个实例属性，不会影响类属性 C.y，所以 C.y == obj.y 为 False。
A.y = obj.y 和 print(A.y, B.y, C.y, obj.y)
- 答案：1 1 1 1
- 解释： A.y = obj.y 将 A 类的 y 属性更新为 1。因为 B 和 C 类没有自己独立的 y，它们会继承 A 的 y 值，所以 B.y 和 C.y 也变为 1。obj.y 是实例属性，也为 1。

Practice

class Account:
    """An account has a balance and a holder.

    >>> a = Account('John')
    >>> a.deposit(10)
    10
    >>> a.balance
    10
    >>> a.interest
    0.02
    >>> a.time_to_retire(10.25)  # 10 -> 10.2 -> 10.404
    2
    >>> a.balance                # Calling time_to_retire method should not change the balance
    10
    >>> a.time_to_retire(11)     # 10 -> 10.2 -> ... -> 11.040808032
    5
    >>> a.time_to_retire(100)
    117
    """
    max_withdrawal = 10
    interest = 0.02

    def __init__(self, account_holder):
        self.balance = 0
        self.holder = account_holder

    def deposit(self, amount):
        self.balance = self.balance + amount
        return self.balance

    def withdraw(self, amount):
        if amount > self.balance:
            return "Insufficient funds"
        if amount > self.max_withdrawal:
            return "Can't withdraw that amount"
        self.balance = self.balance - amount
        return self.balance

    def time_to_retire(self, amount):
        """Return the number of years until balance would grow to amount."""
        assert self.balance > 0 and amount > 0 and self.interest > 0
        "*** YOUR CODE HERE ***"
        future = self.balance
        year = 0
        while future < amount:
            future += self.interest * future
            year += 1
        return year


class FreeChecking(Account):
    """A bank account that charges for withdrawals, but the first two are free!

    >>> ch = FreeChecking('Jack')
    >>> ch.balance = 20
    >>> ch.withdraw(100)  # First one's free. Still counts as a free withdrawal even though it was unsuccessful
    'Insufficient funds'
    >>> ch.withdraw(3)    # Second withdrawal is also free
    17
    >>> ch.balance
    17
    >>> ch.withdraw(3)    # Now there is a fee because free_withdrawals is only 2
    13
    >>> ch.withdraw(3)
    9
    >>> ch2 = FreeChecking('John')
    >>> ch2.balance = 10
    >>> ch2.withdraw(3) # No fee
    7
    >>> ch.withdraw(3)  # ch still charges a fee
    5
    >>> ch.withdraw(5)  # Not enough to cover fee + withdraw
    'Insufficient funds'
    """
    withdraw_fee = 1
    free_withdrawals = 2

    "*** YOUR CODE HERE ***"
    def __init__(self, account_holder):
        super().__init__(account_holder)
        self.withdraws = 0

    def withdraw(self, amount):
        self.withdraws += 1
        fee = 0
        if self.withdraws > self.free_withdrawals:
            fee = self.withdraw_fee
        return super().withdraw(amount + fee)


def without(s, i):
    """Return a new linked list like s but without the element at index i.

    >>> s = Link(3, Link(5, Link(7, Link(9))))
    >>> without(s, 0)
    Link(5, Link(7, Link(9)))
    >>> without(s, 2)
    Link(3, Link(5, Link(9)))
    >>> without(s, 4)           # There is no index 4, so all of s is retained.
    Link(3, Link(5, Link(7, Link(9))))
    >>> without(s, 4) is not s  # Make sure a copy is created
    True
    """
    "*** YOUR CODE HERE ***"
    if s is Link.empty:
        return Link.empty
    if i == 0:
        return s.rest
    else:
        return Link(s.first, without(s.rest, i - 1))


def duplicate_link(s, val):
    """Mutates s so that each element equal to val is followed by another val.

    >>> x = Link(5, Link(4, Link(5)))
    >>> duplicate_link(x, 5)
    >>> x
    Link(5, Link(5, Link(4, Link(5, Link(5)))))
    >>> y = Link(2, Link(4, Link(6, Link(8))))
    >>> duplicate_link(y, 10)
    >>> y
    Link(2, Link(4, Link(6, Link(8))))
    >>> z = Link(1, Link(2, (Link(2, Link(3)))))
    >>> duplicate_link(z, 2) # ensures that back to back links with val are both duplicated
    >>> z
    Link(1, Link(2, Link(2, Link(2, Link(2, Link(3))))))
    """
    "*** YOUR CODE HERE ***"
    if s is Link.empty:
        return Link.empty
    if val == s.first:
        remaing = s.rest
        s.rest = Link(val, remaing)
        duplicate_link(s.rest, val)
    else:
        duplicate_link(s.rest, val)

class Link:
    """A linked list.

    >>> s = Link(1)
    >>> s.first
    1
    >>> s.rest is Link.empty
    True
    >>> s = Link(2, Link(3, Link(4)))
    >>> s.first = 5
    >>> s.rest.first = 6
    >>> s.rest.rest = Link.empty
    >>> s                                    # Displays the contents of repr(s)
    Link(5, Link(6))
    >>> s.rest = Link(7, Link(Link(8, Link(9))))
    >>> s
    Link(5, Link(7, Link(Link(8, Link(9)))))
    >>> print(s)                             # Prints str(s)
    <5 7 <8 9>>
    """
    empty = ()

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

    def __repr__(self):
        if self.rest is not Link.empty:
            rest_repr = ', ' + repr(self.rest)
        else:
            rest_repr = ''
        return 'Link(' + repr(self.first) + rest_repr + ')'

    def __str__(self):
        string = '<'
        while self.rest is not Link.empty:
            string += str(self.first) + ' '
            self = self.rest
        return string + str(self.first) + '>'

总结

这个得先看一下题意：不然做起来稀里糊涂。

Add a time_to_retire method to the Account class. This method takes in an amount and returns the number of years until the current balance grows to at least amount, assuming that the bank adds the interest (calculated as the current balance multiplied by the interest rate) to the balance at the end of each year. Make sure you're not modifying the account's balance! 将time_to_retire方法添加到Account类。此方法接受amount并返回当前balance增长到至少amount之前的年数，假设银行在每年年底将利息（计算为当前balance乘以interest ）添加到balance中。确保您没有修改帐户余额！

总结就是注意利息的计算方法。

class Account:
    """An account has a balance and a holder.

    >>> a = Account('John')
    >>> a.deposit(10)
    10
    >>> a.balance
    10
    >>> a.interest
    0.02
    >>> a.time_to_retire(10.25)  # 10 -> 10.2 -> 10.404
    2
    >>> a.balance                # Calling time_to_retire method should not change the balance
    10
    >>> a.time_to_retire(11)     # 10 -> 10.2 -> ... -> 11.040808032
    5
    >>> a.time_to_retire(100)
    117
    """
    max_withdrawal = 10
    interest = 0.02

    def __init__(self, account_holder):
        self.balance = 0
        self.holder = account_holder

    def deposit(self, amount):
        self.balance = self.balance + amount
        return self.balance

    def withdraw(self, amount):
        if amount > self.balance:
            return "Insufficient funds"
        if amount > self.max_withdrawal:
            return "Can't withdraw that amount"
        self.balance = self.balance - amount
        return self.balance

    def time_to_retire(self, amount):
        """Return the number of years until balance would grow to amount."""
        assert self.balance > 0 and amount > 0 and self.interest > 0
        "*** YOUR CODE HERE ***"
        future = self.balance
        year = 0
        while future < amount:
            future += self.interest * future
            year += 1
        return year

这里关键是修改withdraw函数和__init__函数，由于FreeChecking是Account的子类，所以可以通过调用Account的构造函数进行初始化，此外由于需要跟踪免费的次数，所以设置另外一个属性self.withdraws = 0。

withdraw函数需要重新实现：每次更新self.withdraws，一旦免费次数用完就修改fee，否则为 0，后调用父类的withdraw函数即可。

class FreeChecking(Account):
    """A bank account that charges for withdrawals, but the first two are free!

    >>> ch = FreeChecking('Jack')
    >>> ch.balance = 20
    >>> ch.withdraw(100)  # First one's free. Still counts as a free withdrawal even though it was unsuccessful
    'Insufficient funds'
    >>> ch.withdraw(3)    # Second withdrawal is also free
    17
    >>> ch.balance
    17
    >>> ch.withdraw(3)    # Now there is a fee because free_withdrawals is only 2
    13
    >>> ch.withdraw(3)
    9
    >>> ch2 = FreeChecking('John')
    >>> ch2.balance = 10
    >>> ch2.withdraw(3) # No fee
    7
    >>> ch.withdraw(3)  # ch still charges a fee
    5
    >>> ch.withdraw(5)  # Not enough to cover fee + withdraw
    'Insufficient funds'
    """
    withdraw_fee = 1
    free_withdrawals = 2

    "*** YOUR CODE HERE ***"
    def __init__(self, account_holder):
        super().__init__(account_holder)
        self.withdraws = 0

    def withdraw(self, amount):
        self.withdraws += 1
        fee = 0
        if self.withdraws > self.free_withdrawals:
            fee = self.withdraw_fee
        return super().withdraw(amount + fee)

创建链表可以使用头插法或者尾插法，这里使用头插法：
- 临界情况：链表用完，返回Link.empty
- 目标情况：到达位置i，直接忽略，接上尾部即可。
- 一般情况：递归创建链表，注意更新i - 1。

def without(s, i):
    """Return a new linked list like s but without the element at index i.

    >>> s = Link(3, Link(5, Link(7, Link(9))))
    >>> without(s, 0)
    Link(5, Link(7, Link(9)))
    >>> without(s, 2)
    Link(3, Link(5, Link(9)))
    >>> without(s, 4)           # There is no index 4, so all of s is retained.
    Link(3, Link(5, Link(7, Link(9))))
    >>> without(s, 4) is not s  # Make sure a copy is created
    True
    """
    "*** YOUR CODE HERE ***"
    if s is Link.empty:
        return Link.empty
    if i == 0:
        return s.rest
    else:
        return Link(s.first, without(s.rest, i - 1))

不是新链表，只能在原来的基础上进行改动：

这里使用头插法比较方便：因为可以保留s.rest，只需要在s.first后面插入，s.rest前面插入。遇到s.first==val时进行处理，后面正常递归调用即可。

def duplicate_link(s, val):
    """Mutates s so that each element equal to val is followed by another val.

    >>> x = Link(5, Link(4, Link(5)))
    >>> duplicate_link(x, 5)
    >>> x
    Link(5, Link(5, Link(4, Link(5, Link(5)))))
    >>> y = Link(2, Link(4, Link(6, Link(8))))
    >>> duplicate_link(y, 10)
    >>> y
    Link(2, Link(4, Link(6, Link(8))))
    >>> z = Link(1, Link(2, (Link(2, Link(3)))))
    >>> duplicate_link(z, 2) # ensures that back to back links with val are both duplicated
    >>> z
    Link(1, Link(2, Link(2, Link(2, Link(2, Link(3))))))
    """
    "*** YOUR CODE HERE ***"
    if s is Link.empty:
        return Link.empty
    if val == s.first:
        remaing = s.rest
        s.rest = Link(val, remaing)
        duplicate_link(s.rest, val)
    else:
        duplicate_link(s.rest, val)

lab08

=====================================================================
Assignment: Lab 8
OK, version v1.18.1
=====================================================================

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Unlocking tests

At each "? ", type what you would expect the output to be.
Type exit() to quit

---------------------------------------------------------------------
Trees > Suite 1 > Case 1
(cases remaining: 1)

What would Python display? If you get stuck, try it out in the Python
interpreter!

>>> t = Tree(1, Tree(2)) # Enter Function if you believe the answer is <function ...>, Error if it errors, and Nothing if nothing is displayed.
? Error
-- OK! --

>>> t = Tree(1, [Tree(2)])
>>> t.label
? 1
-- OK! --

>>> t.branches[0]
? Tree(2)
-- OK! --

>>> t.branches[0].label
? 2
-- OK! --

>>> t.label = t.branches[0].label
>>> t
? Tree(2, [Tree(2)])
-- OK! --

>>> t.branches.append(Tree(4, [Tree(8)]))
>>> len(t.branches)
? 2
-- OK! --

>>> t.branches[0]
? Tree(2)
-- OK! --

>>> t.branches[1]
? Tree(4, [Tree(8)])
-- OK! --

---------------------------------------------------------------------
OK! All cases for Trees unlocked.

Backup... 100% complete

答案解释

t = Tree(1, Tree(2))
- 答案：Error
- 解释： Tree 构造函数的第二个参数应为一个包含 Tree 实例的列表。在此语句中，Tree(2) 不是列表，因此会引发错误。
t = Tree(1, [Tree(2)]) 和 t.label
- 答案：1
- 解释： t 是一个树，其根节点标签为 1，唯一的子树是 Tree(2)。所以，t.label 返回根节点的标签，即 1。
t.branches[0]
- 答案：Tree(2)
- 解释： t.branches 是一个包含 Tree(2) 的列表，t.branches[0] 返回第一个子树对象，即 Tree(2)。
t.branches[0].label
- 答案：2
- 解释： t.branches[0] 是 Tree(2)，它的 label 属性为 2。
t.label = t.branches[0].label 和 t
- 答案：Tree(2, [Tree(2)])
- 解释： t.label = t.branches[0].label 将根节点的标签从 1 改为 2，所以 t 现在的结构是 Tree(2, [Tree(2)])。
t.branches.append(Tree(4, [Tree(8)])) 和 len(t.branches)
- 答案：2
- 解释： append 操作在 t 的 branches 列表中添加了一个新的子树 Tree(4, [Tree(8)])。t 现在有两个分支，因此 len(t.branches) 为 2。
t.branches[0]
- 答案：Tree(2)
- 解释： t.branches[0] 是第一个子树，保持为 Tree(2)。
t.branches[1]
- 答案：Tree(4, [Tree(8)])
- 解释： t.branches[1] 是第二个子树，新添加的 Tree(4, [Tree(8)])。

Practice

def cumulative_mul(t):
    """Mutates t so that each node's label becomes the product of its own
    label and all labels in the corresponding subtree rooted at t.

    >>> t = Tree(1, [Tree(3, [Tree(5)]), Tree(7)])
    >>> cumulative_mul(t)
    >>> t
    Tree(105, [Tree(15, [Tree(5)]), Tree(7)])
    >>> otherTree = Tree(2, [Tree(1, [Tree(3), Tree(4), Tree(5)]), Tree(6, [Tree(7)])])
    >>> cumulative_mul(otherTree)
    >>> otherTree
    Tree(5040, [Tree(60, [Tree(3), Tree(4), Tree(5)]), Tree(42, [Tree(7)])])
    """
    "*** YOUR CODE HERE ***"
    if t.is_leaf():
        return t.label
    else:
        cal = t.label
        for son in t.branches:
            cumulative_mul(son)
        for son in t.branches:
            cal *= son.label
        t.label = cal


def prune_small(t, n):
    """Prune the tree mutatively, keeping only the n branches
    of each node with the smallest labels.

    >>> t1 = Tree(6)
    >>> prune_small(t1, 2)
    >>> t1
    Tree(6)
    >>> t2 = Tree(6, [Tree(3), Tree(4)])
    >>> prune_small(t2, 1)
    >>> t2
    Tree(6, [Tree(3)])
    >>> t3 = Tree(6, [Tree(1), Tree(3, [Tree(1), Tree(2), Tree(3)]), Tree(5, [Tree(3), Tree(4)])])
    >>> prune_small(t3, 2)
    >>> t3
    Tree(6, [Tree(1), Tree(3, [Tree(1), Tree(2)])])
    """
    while len(t.branches) > n:
        largest = max(t.branches, key=lambda x: x.label)
        t.branches.remove(largest)
    for b in t.branches:
        prune_small(b, n)


def delete(t, x):
    """Remove all nodes labeled x below the root within Tree t. When a non-leaf
    node is deleted, the deleted node's children become children of its parent.

    The root node will never be removed.

    >>> t = Tree(3, [Tree(2, [Tree(2), Tree(2)]), Tree(2), Tree(2, [Tree(2, [Tree(2), Tree(2)])])])
    >>> delete(t, 2)
    >>> t
    Tree(3)
    >>> t = Tree(1, [Tree(2, [Tree(4, [Tree(2)]), Tree(5)]), Tree(3, [Tree(6), Tree(2)]), Tree(4)])
    >>> delete(t, 2)
    >>> t
    Tree(1, [Tree(4), Tree(5), Tree(3, [Tree(6)]), Tree(4)])
    >>> t = Tree(1, [Tree(2, [Tree(4), Tree(5)]), Tree(3, [Tree(6), Tree(2)]), Tree(2, [Tree(6),  Tree(2), Tree(7), Tree(8)]), Tree(4)])
    >>> delete(t, 2)
    >>> t
    Tree(1, [Tree(4), Tree(5), Tree(3, [Tree(6)]), Tree(6), Tree(7), Tree(8), Tree(4)])
    """
    new_branches = []
    for b in t.branches:
        delete(b, x)
        if b.label == x:
            new_branches.extend(b.branches)
        else:
            new_branches.append(b)
    t.branches = new_branches
    # append 和 extend 的区别：
    # append 不管元素是否为空， extend 是将iterable中的非空元素拼接到末尾

def max_path_sum(t):
    """Return the maximum path sum of the tree.

    >>> t = Tree(1, [Tree(5, [Tree(1), Tree(3)]), Tree(10)])
    >>> max_path_sum(t)
    11
    """
    "*** YOUR CODE HERE ***"
    if t.is_leaf():
        return t.label
    cal = t.label
    val = 0
    for son in t.branches:
        val = max(max_path_sum(son), val)
    cal += val
    return cal


class Tree:
    """A tree has a label and a list of branches.

    >>> t = Tree(3, [Tree(2, [Tree(5)]), Tree(4)])
    >>> t.label
    3
    >>> t.branches[0].label
    2
    >>> t.branches[1].is_leaf()
    True
    """
    def __init__(self, label, branches=[]):
        self.label = label
        for branch in branches:
            assert isinstance(branch, Tree)
        self.branches = list(branches)

    def is_leaf(self):
        return not self.branches

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

    def __str__(self):
        return '\n'.join(self.indented())

    def indented(self):
        lines = []
        for b in self.branches:
            for line in b.indented():
                lines.append('  ' + line)
        return [str(self.label)] + lines

总结

递归调用：先更新叶子，后往上一层一层更新父亲。

def cumulative_mul(t):
    """Mutates t so that each node's label becomes the product of its own
    label and all labels in the corresponding subtree rooted at t.

    >>> t = Tree(1, [Tree(3, [Tree(5)]), Tree(7)])
    >>> cumulative_mul(t)
    >>> t
    Tree(105, [Tree(15, [Tree(5)]), Tree(7)])
    >>> otherTree = Tree(2, [Tree(1, [Tree(3), Tree(4), Tree(5)]), Tree(6, [Tree(7)])])
    >>> cumulative_mul(otherTree)
    >>> otherTree
    Tree(5040, [Tree(60, [Tree(3), Tree(4), Tree(5)]), Tree(42, [Tree(7)])])
    """
    "*** YOUR CODE HERE ***"
    if t.is_leaf():
        return t.label
    else:
        cal = t.label
        for son in t.branches:
            cumulative_mul(son)
        for son in t.branches:
            cal *= son.label
        t.label = cal

这个需要留意的是从父亲到儿子进行处理，所以先对当前节点的分支进行剪切，然后再递归到下一层逐层处理。

补充题目背景如下：

Removing some nodes from a tree is called pruning the tree. 从树中删除一些节点称为修剪树。

Complete the function prune_small that takes in a Tree t and a number n. For each node with more than n branches, keep only the n branches with the smallest labels and remove (prune) the rest. 完成函数prune_small ，它接受Tree t和数字n 。对于每个具有超过n分支的节点，仅保留具有最小标签的n分支，并删除（修剪）其余的。

Hint: The max function takes in an iterable as well as an optional key argument (which takes in a one-argument function). For example, max([-7, 2, -1], key=abs) would return -7 since abs(-7) is greater than abs(2) and abs(-1). 提示： max函数接受一个iterable以及一个可选的key参数（它接受一个单参数函数）。例如， max([-7, 2, -1], key=abs)将返回-7因为abs(-7)大于abs(2)和abs(-1) 。

def prune_small(t, n):
    """Prune the tree mutatively, keeping only the n branches
    of each node with the smallest labels.

    >>> t1 = Tree(6)
    >>> prune_small(t1, 2)
    >>> t1
    Tree(6)
    >>> t2 = Tree(6, [Tree(3), Tree(4)])
    >>> prune_small(t2, 1)
    >>> t2
    Tree(6, [Tree(3)])
    >>> t3 = Tree(6, [Tree(1), Tree(3, [Tree(1), Tree(2), Tree(3)]), Tree(5, [Tree(3), Tree(4)])])
    >>> prune_small(t3, 2)
    >>> t3
    Tree(6, [Tree(1), Tree(3, [Tree(1), Tree(2)])])
    """
    while len(t.branches) > n:
        largest = max(t.branches, key=lambda x: x.label)
        t.branches.remove(largest)
    for b in t.branches:
        prune_small(b, n)

大致思路是创建一个new_braches，替换t.branches。

Implement delete, which takes a Tree t and removes all non-root nodes labeled x. The parent of each remaining node is its nearest ancestor that was not removed. The root node is never removed, even if its label is x. 实现delete ，它采用 Tree t并删除所有标记为x非根节点。每个剩余节点的父节点是其未删除的最近祖先。根节点永远不会被删除，即使它的标签是x 。

注意，树不会断！！！所以就算删去了标记为x的非根节点，还是需要对分支进行处理。

先递归处理好儿子，再返回处理祖先。所以第三个空是delete函数，后面就是new_branches的拼接：需要留意append和extend方法的区别。

append 不管元素是否为空拼接到末尾， extend 是将iterable中的非空元素拼接到末尾

def delete(t, x):
    """Remove all nodes labeled x below the root within Tree t. When a non-leaf
    node is deleted, the deleted node's children become children of its parent.

    The root node will never be removed.

    >>> t = Tree(3, [Tree(2, [Tree(2), Tree(2)]), Tree(2), Tree(2, [Tree(2, [Tree(2), Tree(2)])])])
    >>> delete(t, 2)
    >>> t
    Tree(3)
    >>> t = Tree(1, [Tree(2, [Tree(4, [Tree(2)]), Tree(5)]), Tree(3, [Tree(6), Tree(2)]), Tree(4)])
    >>> delete(t, 2)
    >>> t
    Tree(1, [Tree(4), Tree(5), Tree(3, [Tree(6)]), Tree(4)])
    >>> t = Tree(1, [Tree(2, [Tree(4), Tree(5)]), Tree(3, [Tree(6), Tree(2)]), Tree(2, [Tree(6),  Tree(2), Tree(7), Tree(8)]), Tree(4)])
    >>> delete(t, 2)
    >>> t
    Tree(1, [Tree(4), Tree(5), Tree(3, [Tree(6)]), Tree(6), Tree(7), Tree(8), Tree(4)])
    """

    #new_branches = []
    #for _________ in ________________:
    #    _______________________
    #    if b.label == x:
    #        __________________________________
    #    else:
    #        __________________________________
    #t.branches = ___________________

    new_branches = []
    for b in t.branches:
        delete(b, x)
        if b.label == x:
            new_branches.extend(b.branches)
        else:
            new_branches.append(b)
    t.branches = new_branches
    # append 和 extend 的区别：
    # append 不管元素是否为空拼接到末尾， extend 是将iterable中的非空元素拼接到末尾

lab 整理

lab00

lab01

WWPD

答案解释

Practice

总结

lab02

WWPD

答案解释

Lambda the Free

The Truth Will Prevail

Higher Order Functions

Practice

总结

函数结构

递归逻辑分析

例子解析

my_cycle = cycle(add1, times2, add3)

my_cycle(3)(2) 的计算过程：

总结

闭包的解释

为什么 counter 能捕获 n

闭包示例

lab03

WWPD

答案解释

Lists

Comprehensions

Practice

总结

lab04

WWPD

答案解释

Practice

总结

示例

lab05

WWPD1

答案解释 1

WWPD2

答案解释 2

Case 1

Case 2

Case 3

Practice

总结

lab06

Practice

总结

lab07

WWPD

答案解释

Practice

总结

lab08

答案解释

Practice

总结

`my_cycle = cycle(add1, times2, add3)`

`my_cycle(3)(2)` 的计算过程：

为什么 `counter` 能捕获 `n`