日拱一卒,一起來上伯克利的實驗課,帶你入門Python
大家好,日拱一卒,我是梁唐。Coder梁
最近經同學提醒,補做了伯克利CS61A的實驗,發現非常有意思,分享給大家。
雖然我們不是伯克利的學生,沒辦法提交實驗,得到老師的反饋。但是大部分問題我們還是可以進行本地測試的,能夠實時地看到我們的結果是否正確,因此是一個很好的鍛鍊機會。
本系列會持續更新,想要一起學習的同學不妨在評論區打個卡。
在之前的文章當中,可能沒有特別說清楚這點,也許有些同學還不知道,所以這裡再介紹一下。
首先,我們可以訪問實驗的官網,比如這個實驗的連結是:
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次,這是一個非常巨大的差距,側面體現除了演算法的重要。一個好的演算法帶來的優化和價值在一些場景中是非常非常巨大的。
- 日拱一卒,麻省理工教你效能分析,火焰圖、系統呼叫棧,黑科技滿滿
- 日拱一卒,麻省理工教你Debug,從此debug不再脫髮
- 日拱一卒,麻省理工教你學Git,工程師必備技能
- 日拱一卒,配置開發環境不再愁,麻省理工手把手教你
- 日拱一卒,麻省理工CS入門課,命令列這樣用也太帥了
- 日拱一卒,麻省理工YYDS,一節課讓我學會用vim
- 日拱一卒,麻省理工教你CS基礎,那些酷炫無比的命令列工具
- LeetCode周賽297,一小時AK你也可以
- 聽說你入行好幾年還只會cd和ls,麻省理工開了這門課……
- 日拱一卒,伯克利CS61A完結撒花
- 日拱一卒,伯克利教你用SQL處理資料
- LeetCode周賽296,難度較低的新手練習場
- 日拱一卒,伯克利教你Python核心技術,迭代器和生成器
- 日拱一卒,伯克利CS61A,教你用Python寫一個Python直譯器
- 日拱一卒,伯克利教你lisp,神一樣的程式語言
- LeetCode周賽295,賽後看了大佬的程式碼,受益匪淺
- 日拱一卒,伯克利的Python期中考試,你能通過嗎?
- 日拱一卒,伯克利教你資料結構
- 日拱一卒,伯克利教你學Python,面向物件和繼承
- LeetCode周賽294,硬核壓軸題的手速場