CS61A（Discussion1） - piterの小窝

piter

公告

欢迎来到 piter 的小窝！

关于我

标签

piter

公告

欢迎来到 piter 的小窝！

关于我

标签

piter

公告

欢迎来到 piter 的小窝！

关于我

标签

首页 / 学习 / CS61A（Discussion1）

644 字

2 分钟

CS61A（Discussion1）

2025-07-30

学习

无标签

Q1: 赛跑#

下面的 race 函数有时会返回错误的值，有时会永远运行。

1
def race(x, y):
2
    """The tortoise always walks x feet per minute, while the hare repeatedly
3
    runs y feet per minute for 5 minutes, then rests for 5 minutes. Return how
4
    many minutes pass until the tortoise first catches up to the hare.
5

6
    >>> race(5, 7)  # After 7 minutes, both have gone 35 steps
7
    7
8
    >>> race(2, 4) # After 10 minutes, both have gone 20 steps
9
    10
10
    """
11
    assert y > x and y > 0 and x > 0
12
    tortoise, hare, minutes = 0, 0, 0
13
    while tortoise - hare:
14
        tortoise += x
15
        if minutes % 10 < 5:
16
            hare += y
17
        minutes += 1
18
    return minutes

问题分析：

返回错误值：函数等待的是乌龟路程恰好等于兔子路程，而不是乌龟第一次追上或超过兔子。乌龟可能先超过兔子（差值从负变正），然后由于兔子又开始跑，差距拉大，直到未来某一刻两者路程恰好相等才返回。这时返回的不是第一次追上的时刻。
永远运行（死循环）：乌龟路程可能永远无法恰好等于兔子路程——在某分钟还落后，下一分钟直接超过，差值从负数跳到正数，跨过了零点，循环永不终止。

导致”永远运行”的例子：`race(3, 5)`#

追踪关键节点（x=3，y=5）：

Minutes	状态	乌龟	兔子	差值	说明
8	歇	24	25	-1	乌龟还差一步
9	歇	27	25	+2	乌龟超过了兔子，但差值不为0
13	跑	39	40	-1	兔子又超过了乌龟

在第 9 分钟，乌龟路程（27）超过了兔子（25），但差值是 2，不为 0，循环没有停止。之后差值在正负之间跳跃，永远无法回到 0。因此 race(3, 5) 导致无限循环。

导致”返回错误值”的例子：`race(4, 6)`#

追踪关键节点（x=4，y=6）：

Minutes	状态	乌龟	兔子	差值	说明
8	歇	32	30	+2	乌龟第一次追上（正确答案应为 8）
15	跑	60	60	0	路程恰好相等，循环停止，返回 15

在第 8 分钟，乌龟第一次超过兔子，正确答案应该是 8。但代码检查的是 tortoise == hare，没有在第 8 分钟停止，直到第 15 分钟两者路程都为 60 才停止，返回了错误值 15。

Q2: Fizzbuzz#

实现经典的 Fizz Buzz 序列。fizzbuzz 函数接受一个正整数 n，为 1 到 n 之间的每个整数打印一行输出：

能同时被 3 和 5 整除，打印 fizzbuzz
能被 3 整除（但不被 5 整除），打印 fizz
能被 5 整除（但不被 3 整除），打印 buzz
否则，打印数字 i

1
def fizzbuzz(n):
2
    """
3
    >>> result = fizzbuzz(16)
4
    1
5
    2
6
    fizz
7
    4
8
    buzz
9
    fizz
10
    7
11
    8
12
    fizz
13
    buzz
14
    11
15
    fizz
16
    13
17
    14
18
    fizzbuzz
19
    16
20
    >>> print(result)
21
    None
22
    """
23
    i = 1
24
    while i <= n:
25
        if i % 3 == 0 and i % 5 == 0:
26
            print('fizzbuzz')
27
        elif i % 3 == 0:
28
            print('fizz')
29
        elif i % 5 == 0:
30
            print('buzz')
31
        else:
32
            print(i)
33
        i += 1

注意 if 和 elif 的顺序：先检查能否同时被 3 和 5 整除，再分别检查能否被 3 或 5 整除。

Q3: is_prime#

判断 n 是否为素数：

1
def is_prime(n):
2
    """
3
    >>> is_prime(10)
4
    False
5
    >>> is_prime(7)
6
    True
7
    >>> is_prime(1)
8
    False
9
    """
10
    if n == 1:
11
        return False
12
    i = 2
13
    while i < n:
14
        if n % i == 0:
15
            return False
16
        i += 1
17
    return True

Q4: unique_digits#

返回 n 中不重复数字的个数：

1
def has_digit(n, k):
2
    """Returns whether k is a digit in n."""
3
    assert 0 <= k <= 9
4
    while n > 0:
5
        last = n % 10
6
        n = n // 10
7
        if last == k:
8
            return True
9
    return False
10

11
def unique_digits(n):
12
    """
13
    >>> unique_digits(8675309)  # All are unique
14
    7
15
    >>> unique_digits(13173131)  # 1, 3, and 7
16
    3
17
    >>> unique_digits(101)  # 0 and 1
18
    2
19
    """
20
    unique = 0
21
    while n > 0:
22
        k = n % 10
23
        n = n // 10
24
        if not has_digit(n, k):
25
            unique += 1
26
    return unique