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

語言: CN / TW / HK

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

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

課程連結

Github

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

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

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

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

https://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是非法操作,但由於之前出現了2True,所以阻斷了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,它接收兩個引數nk,返回從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次,這是一個非常巨大的差距,側面體現除了演算法的重要。一個好的演算法帶來的優化和價值在一些場景中是非常非常巨大的。