日拱一卒，一起來上伯克利的實驗課，帶你入門Python

語言: CN / TW / HK
時間 2022-05-18 03:16:00

大家好，日拱一卒，我是梁唐。Coder梁

最近經同學提醒，補做了伯克利CS61A的實驗，發現非常有意思，分享給大家。

課程連結

Github

雖然我們不是伯克利的學生，沒辦法提交實驗，得到老師的反饋。但是大部分問題我們還是可以進行本地測試的，能夠實時地看到我們的結果是否正確，因此是一個很好的鍛鍊機會。

本系列會持續更新，想要一起學習的同學不妨在評論區打個卡。

在之前的文章當中，可能沒有特別說清楚這點，也許有些同學還不知道，所以這裡再介紹一下。

首先，我們可以訪問實驗的官網，比如這個實驗的連結是：

http://inst.eecs.berkeley.edu//~cs61a/sp18/lab/lab01/#using-python

複製連結進入之後，可以看到：

右側是整個文件的目錄，我們可以點選下載lab01.zip，裡面有實驗所需要的所有內容。包括單元測試以及框架程式碼等等。我們下載解壓之後，使用命令列進入資料夾。之後就可以根據題目當中的命令提示進行測試了。

每道題目當中都會有測試命令的說明，比如本次實驗的第一題中，需要我們使用命令來回答問題。

那麼我們就遵循這個提示，在命令列輸入對應的命令，就可以回答問題了。這裡最好使用python3.6的版本，版本太高可能會報錯。

有些問題是直接進行測試，我們可以直接看到測試結果：

測試通過之後，會讓我們輸入學校的郵箱進行提交。我們當然是沒辦法提交的，這時候直接Ctrl + D退出就好了。或者可以在測試命令之後加上字尾--local，表示本地測試，不進行上傳。

這次的實驗課是一個Python的基礎練習，帶我們熟悉和掌握Python的基礎語法。

What Would Python Display (Part 1)?

第一部分，根據程式碼推測Python的輸出結果。

Q1: WWPD: Veritasiness

互動命令：python3 ok -q short_circuiting -u

在命令行當中進行答題，一共有14題：

```python

True and 13

False or 0

not 10

not None

True and 1 / 0 and False

True or 1 / 0 or False

True and 0

False or 1

1 and 3 and 6 and 10 and 15

0 or False or 2 or 1 / 0

not 0

(1 + 1) and 1

1/0 or True

(True or False) and False

```

這些題不難我就不專門放答案了，如果大家吃不準結果，直接複製出來在Python裡執行一下即可。

核心注意點只有兩個，第一個是在and計算時，如果結果都為True，會返回最後一個為True的結果，比如：1 and 3 and 6 and 10 and 15最後的結果是15.

第二個點是，進行or計算時，遇到為True的值之後，後面的運算會停止。比如0 or False or 2 or 1 / 0，雖然最後1/0是非法操作，但由於之前出現了2是True，所以阻斷了1/0的執行。

Q2: WWPD: Loops

本地測試命令：python3 ok -q loops -u

互動答題，一共有7題：

```python

n = 3 while n >= 0: ... n -= 1 ... print(n)

n = 4 while n > 0: ... n += 1 ... print(n)

def go(n): ... if n % 2 != 0: ... print(n / 2) ... return ... while n > 0: ... print(n) ... n = n // 2 go(4)

go(5)

zero = 2 while zero != 0: ... zero = zero // 2 ... print(zero)

positive = 28 while positive: ... print("positive?") ... positive -= 3

positive = -9 negative = -12 while negative: ... if positive: ... print(negative) ... positive += 3 ... negative += 3

```

同樣如果拿不準，在Python裡執行一下就可以了。不過還是建議大家人肉答題，這樣當出乎意料的結果出現時，比較鍛鍊人。

Coding Practice

程式碼練習

Q3: Repeated

實現repeated函式，它接收一個引數f表示一個函式，一個正整數n和一個引數x。它返回如下表達式的結果： f(f(...f(x)...))，即嵌套了n層f之後的結果。

參考樣例：

```python

def square(x): ... return x * x ... repeated(square, 2, 3) # square(square(3)), or 3 ** 4 81 repeated(square, 1, 4) # square(4) 16 repeated(square, 6, 2) # big number 18446744073709551616 def opposite(b): ... return not b ... repeated(opposite, 4, True) True repeated(opposite, 5, True) False repeated(opposite, 631, 1) False repeated(opposite, 3, 0) True """ ```

完成之後，進行測試：python3 ok -q repeated

答案

如果理解遞迴，使用遞迴非常簡單。

python def repeated(f, n, x): """Returns the result of composing f n times on x. """ "*** YOUR CODE HERE ***" if n == 1: return f(x) return f(repeated(f, n-1, x))

不用遞迴其實也不麻煩，我們迴圈n-1次也一樣可以得到答案：

python def repeated(f, n, x): """Returns the result of composing f n times on x. """ "*** YOUR CODE HERE ***" ret = x for _ in range(n): ret = f(ret) return ret

Q4: Sum Digits

實現一個函式，它接收一個非負整數，返回這個整數所有數字的和（使用整除和取模運算）

參考樣例：

```python

sum_digits(10) # 1 + 0 = 1 1 sum_digits(4224) # 4 + 2 + 2 + 4 = 12 12 sum_digits(1234567890) 45 ```

完成之後，進行測試：python3 ok -q sum_digits

答案

這題和上一題一樣的套路，使用遞迴和不使用遞迴都很簡單。

遞迴版本：

python def sum_digits(n): """Sum all the digits of n. """ "*** YOUR CODE HERE ***" if n < 10: return n return sum_digits(n // 10) + n % 10

非遞迴版本：

python def sum_digits(n): """Sum all the digits of n. """ "*** YOUR CODE HERE ***" ret = 0 while n > 0: ret += n % 10 n //= 10 return ret

Q5: Double Eights

實現一個函式，它接收一個數，返回它的數字當中是否包含兩個相鄰的8

參考樣例：

```python

double_eights(8) False double_eights(88) True double_eights(2882) True double_eights(880088) True double_eights(12345) False double_eights(80808080) False ```

測試命令：python3 ok -q double_eights

答案

這道題可能迭代的方法會稍微直觀一點，我們只需要將這個數字轉化成字串，然後返回是否擁有'88'的子串即可。

程式碼實現只有一行：

python def double_eights(n): """Return true if n has two eights in a row. """ "*** YOUR CODE HERE ***" return '88' in str(n)

如果不使用轉化成字串這種取巧的辦法，我們還可以每次取出n的最後兩位，如果這兩位等於88，則返回True，否則將n除以10，相當於去掉最後一位，繼續判斷最後兩位是否是88，直到n小於10為止。

python def double_eights(n): """Return true if n has two eights in a row. """ "*** YOUR CODE HERE ***" while n > 10: if n % 100 == 88: return True n //= 10 return False

基於上面迭代的方法，我們也可以寫出遞迴的解法，本質上思路是一樣的，只是程式碼實現略有不同。

python def double_eights(n): """Return true if n has two eights in a row. """ "*** YOUR CODE HERE ***" if n < 10: return False pref, suff = (n % 100) // 10, n % 10 return (pref == 8 and suff == 8) or double_eights(n // 10)

附加題

What Would Python Display (Part 2)?

根據程式碼推測Python的輸出結果第二彈。

Q6: WWPD: Truthiness

真假值判斷，互動命令：python3 ok -q truthiness -u

在命令列中答題，一個有6題：

```python

0 or True

not '' or not 0 and False

13 and False

False or 1

'' or 1 and 1/0

not 0 and 12 or 0

```

套路和之前差不多，稍微多加了幾種情況。

Q7: WWPD: What If?

命令列中答題，if語句，互動命令：python3 ok -q what_if -u

下列函式的程式碼在lab01.py中，當你被難住的時候，可以使用命令python3 -i lab01.py進行實驗。

```python

def xk(c, d): ... if c == 4: ... return 6 ... elif d >= 4: ... return 6 + 7 + c ... else: ... return 25 xk(10, 10)

xk(10, 6)

xk(4, 6)

xk(0, 0)

def how_big(x): ... if x > 10: ... print('huge') ... elif x > 5: ... return 'big' ... elif x > 0: ... print('small') ... else: ... print("nothin'") how_big(7)

how_big(12)

how_big(1)

how_big(-1)

def so_big(x): ... if x > 10: ... print('huge') ... if x > 5: ... return 'big' ... if x > 0: ... print('small') ... print("nothin'") so_big(7)

so_big(12)

so_big(1)

def ab(c, d): ... if c > 5: ... print(c) ... elif c > 7: ... print(d) ... print('foo') ab(10, 20)

def bake(cake, make): ... if cake == 0: ... cake = cake + 1 ... print(cake) ... if cake == 1: ... print(make) ... else: ... return cake ... return make bake(0, 29)

bake(1, "mashed potatoes")

```

題目不難，稍微有一些陰險，有時候需要轉個彎。

More Coding Practice

更多程式設計練習

Q8: Fix the Bug

下列程式碼片段有bug，找出其中的bug並修復

```python def both_positive(x, y): """Returns True if both x and y are positive.

>>> both_positive(-1, 1)
False
>>> both_positive(1, 1)
True
"""
return x and y > 0 # You can replace this line!

```

完成之後進行測試：python3 ok -q both_positive

答案

癥結在於Python當中只有0是False，所以應該改成：return x > 0 and y > 0

Q9: Falling Factorial

讓我們來實現一個函式failing，它接收兩個引數n和k，返回從n開始k個遞減數的乘積

參考樣例：

```python

falling(6, 3) # 6 * 5 * 4 120 falling(4, 0) 1 falling(4, 3) # 4 * 3 * 2 24 falling(4, 1) # 4 4 ```

測試命令：python3 ok -q falling

答案

幾乎沒有難度，非遞迴版本：

python def falling(n, k): """Compute the falling factorial of n to depth k. """ "*** YOUR CODE HERE ***" ret = 1 for i in range(n, n-k, -1): ret *= i return ret

遞迴版本：

python def falling(n, k): """Compute the falling factorial of n to depth k. """ "*** YOUR CODE HERE ***" if k == 0: return 1 return n * falling(n-1, k-1)

I Want to Play a Game

讓我們來玩一個猜數遊戲，選一個數，讓Python來猜測它，直到猜中。

猜數遊戲的完整程式碼在label01_extra.py中，在你的命令列中輸入python3-ilab01_extra.py來和Python程式進行互動。

guess_random函式會讓你先選一個數，然後迴圈你若干次它的猜測是否正確。如果它猜對了，輸入y，否則輸入n。Python並不擅長猜數，所以可能會猜很久，你可以通過Ctrl-C來終止程式。

隨機猜測可行，但你需要開發更好的策略。

Q10: Guess Linear

guess_random策略的一個弱點就是它可能會重複猜測某些錯誤的數字，所以我們可以使用線性猜測讓它更加合理。

注意：is_correct函式會迴圈使用者它是否猜對了，如果猜對了會返回True，否則會返回False。當你實現guess_linear時，可以隨意參考guess_random程式碼

框架程式碼：

python def guess_linear(): """Guess in increasing order and return the number of guesses.""" prompt_for_number(LOWER, UPPER) num_guesses = 1 guess = LOWER "*** YOUR CODE HERE ***" return num_guesses

答案

很簡單，一直猜測，直到猜對為止

python def guess_linear(): """Guess in increasing order and return the number of guesses.""" prompt_for_number(LOWER, UPPER) num_guesses = 1 guess = LOWER "*** YOUR CODE HERE ***" while guess <= UPPER: correct = is_correct(guess) if correct: break guess += 1 num_guesses += 1 return num_guesses

Q11: Guess Binary

挑戰性問題：guess_linear在我們的數字很大的時候，一樣會陷入很長的時間。所以我們還可以進一步優化，採取binary search即二分的思路來猜測。

整體的思路是從範圍的中間為止開始猜測，如果猜錯了，通過is_too_high函式詢問猜測的結果是太大了還是太小了，你可以每次縮小一半的猜測範圍。

is_too_high的用法如下：

框架程式碼：

```python def guess_binary(): """Return the number of attempted guesses. Implement a faster search algorithm that asks the user whether a guess is less than or greater than the correct number.

Hint: If you know the guess is greater than the correct number, then your
algorithm doesn't need to try numbers that are greater than guess.
"""
prompt_for_number(LOWER, UPPER)
num_guesses = 1
lower, upper = LOWER, UPPER
guess = (lower + upper) // 2
"*** YOUR CODE HERE ***"
return num_guesses

```

如果你選擇的數字在1到10之間，那麼不超過4次就找出答案了。

最好的測試方法是互動式地執行，思考一些邊界條件——可能會導致你的演算法出錯的情況。你可能需要經常重啟、終止你的程式來進行反覆測試。

目前為止，我們的範圍只有1到10，如果我們把它延伸到1到100會怎麼樣，你覺得在1到100的範圍內，每一個演算法會需要猜測多少次能猜到答案？

A Second Look

讓我們來試著視覺化我們剛剛開發的兩個演算法，我們提供了現成的程式碼來執行演算法1000次，並且繪製程式猜測的次數。每次猜測的數字都是隨機從1到100中選的。

bash python3 guessing_game_graph.py guess_linear python3 guessing_game_graph.py guess_binary

每一個柱表示了演算法找到正確結果的猜測次數，高度表示了對應的頻次。仔細觀察每個座標軸，對比一下這兩張圖。你會發現guess_linear有時候用了100次才猜到答案，而guess_binary最多用了多少次？

這裡提供一下我繪製出的圖的情況，首先是guess_linear：

然後是guess_binary:

答案是二分法最多需要8次，而線性猜測最多需要100次，這是一個非常巨大的差距，側面體現除了演算法的重要。一個好的演算法帶來的優化和價值在一些場景中是非常非常巨大的。

「」
「」