iT邦幫忙

第 12 屆 iT 邦幫忙鐵人賽

DAY 9
0
Software Development

從零開始學Python系列 第 9

[Day 09] 從零開始學Python - 例外處理、遞迴:誰用三生浮世的煙火,換你一次長憶的交錯

註:本文同步刊載在Medium,若習慣Medium的話亦可去那邊看呦!

先來解答昨天的問題吧!

  1. 為了表現出串列表達式的用法,
    這邊我們就先不將range的部分和取偶數合併,
    不然使用range(2, 11, 2)就行了。
    連同2的寫法如下:
lt1 = []
for i in range(1, 11): # 記得每層都是用縮排表示
	if i % 2 == 0:
		for j in range(1, 11):
			if j % 2 == 0:
				lt1.append(i * j)
print(lt1)

lt2 = [i * j for i in range(1, 11) if i % 2 == 0 for j in range(1, 11) if j % 2 == 0] # 我們可以用不只一層的for來處理列表生成式
print(lt2)

執行結果參考如下:

C:\Users\Desolve>python fromzero.py
[4, 8, 12, 16, 20, 8, 16, 24, 32, 40, 12, 24, 36, 48, 60, 16, 32, 48, 64, 80, 20, 40, 60, 80, 100]
[4, 8, 12, 16, 20, 8, 16, 24, 32, 40, 12, 24, 36, 48, 60, 16, 32, 48, 64, 80, 20, 40, 60, 80, 100]
  1. 以現有給出來的內容,我們可以寫成類似以下的小遊戲:
ans, guess = 37, 0
l, r = 1, 100
while ans != guess: # 猜對就離開,猜錯則繼續
	guess = int(input('請在' + str(l) + '到' + str(r) + '之間猜一個數:'))
	if guess < ans:
		print('您猜的數字比答案還要小,請再猜大一點~')
		l = guess + 1 # 範圍會被限縮到比剛剛猜的數字還要大做為左邊界
	elif guess > ans:
		print('您猜的數字比答案還要大,請再猜小一點~')
		r = guess - 1

print('恭喜你猜出答案啦!')

請留意,這只是按照我們現在已經學到的部分來撰寫的,
以這個解法來說的話就包含了以下幾個明顯的bug
(程式臭蟲,指程式碼中有一些問題導致運行會當掉或是輸出結果有問題,
可能是輸入錯誤,也有可能是程式的邏輯本身出的問題):

  1. 輸入非數字的時候會因為無法轉換成整數而使程式當掉。
  2. 輸入數字可以限縮範圍,但我們並沒有真的限制使用者只能輸入這個範圍內的數字。
    請參照執行結果,應該能理解上面兩點所造成的問題。
C:\Users\Desolve>python fromzero.py
請在1到100之間猜一個數:90
您猜的數字比答案還要大,請再猜小一點~
請在1到89之間猜一個數:10
您猜的數字比答案還要小,請再猜大一點~
請在11到89之間猜一個數:-5
您猜的數字比答案還要小,請再猜大一點~
請在-4到89之間猜一個數:88
您猜的數字比答案還要大,請再猜小一點~
請在-4到87之間猜一個數:34
您猜的數字比答案還要小,請再猜大一點~
請在35到87之間猜一個數:37
恭喜你猜出答案啦!

C:\Users\Desolve>python fromzero.py
請在1到100之間猜一個數:67u
Traceback (most recent call last):
  File "fromzero.py", line 4, in <module>
    guess = int(input('請在' + str(l) + '到' + str(r) + '之間猜一個數:'))
ValueError: invalid literal for int() with base 10: '67u'

C:\Users\Desolve>python fromzero.py
請在1到100之間猜一個數:st
Traceback (most recent call last):
  File "fromzero.py", line 4, in <module>
    guess = int(input('請在' + str(l) + '到' + str(r) + '之間猜一個數:'))
ValueError: invalid literal for int() with base 10: 'st'

接下來我們來講今天的第一個主題:
如昨天的第三題來說,我們會發現使用者永遠可以超乎你的想像。
這時候你希望得到可以轉成1~100的字串,並且能夠處理掉輸入錯誤的問題的話,
該怎麼辦呢?

如果你能將使用者輸入的每一種內容都分門別類,
當然可以用if...elif...else的形式來進行解決,
如果沒有想要分那麼精細呢?
我們可以使用Python的錯誤處理機制try...except...。
基本語法如下:

try:
    有可能發生例外的程式碼
except:
    發生例外時,執行這個區塊的程式碼處理

讓我們改一下前面的程式碼看看:

ans, guess = 37, 0
l, r = 1, 100
while ans != guess:
	try:
		guess = int(input('\n請在' + str(l) + '到' + str(r) + '之間猜一個數:'))
	except: # 加入continue,直接跳過後面的範圍處理,回到迴圈的開頭
		print('請輸入正常的數字,不要加其他字母或符號呦!')
		continue
	if guess < l or guess > r: # 超出範圍的部分同樣也要跳過(當然,也可以用elif和下面的判斷連起來)
		print('請輸入正確範圍內的數字!')
		continue
	if guess < ans:
		print('您猜的數字比答案還要小,請再猜大一點~')
		l = guess + 1
	elif guess > ans:
		print('您猜的數字比答案還要大,請再猜小一點~')
		r = guess - 1

print('恭喜你猜出答案啦!')

在上面的程式中,當我們用try包住input那行以後,
一旦我們輸入了不是數字的東西,原本Python會報錯並結束程式,
此時就會改成來到except處來執行對應的程式碼。
(如果沒輸入錯誤,except的部分就會被忽略)

事實上,不同的例外在Python當中會有不同的錯誤類型,
如果你想要分開精細地處理不同類型的例外的話,
就要寫成如下型式:

try:
    有可能發生例外的程式碼
except 例外1 as 命名1:
    處理例外1的種類所造成的例外的程式碼(發生什麼事情可以從命名1的變數印出)
except 例外2 as 命名2:
    ...
except 例外3 as 命名3:
    ...

當一個例外發生時會依序由上到下檢查符合哪一個種類的例外,
先滿足條件的獨佔(可以想成類似if...elif的檢查方式)
例外的類別有像是UppercaseException, IndexError, ValueError等等,
他們的共同的大類別都是Exception。

你也可以使用raise Exception(傳入值)來主動將例外丟出。
(如果你有做好處理的準備的話)
同時,它可以帶著給定的訊息,有助於我們判斷到底是怎麼一回事。

>>> try:
...     raise Exception('讚讚')
... except Exception as exc:
...     print(exc)
...
讚讚

接下來我們要來講一個日後各位一定碰得到也很常用的方法:遞迴(Recursion)
什麼是遞迴呢?
遞迴就是當一個函式在使用時,中途不斷呼叫自己,藉以達到某些目的或完成某些問題。
通常狀況下,寫得正常的遞迴應該會不斷在過程中將要計算的問題進行簡化,
最終只剩下我們要的東西,同時沒有再繼續呼叫函式。
聽起來......超級無敵抽象的阿!!!
沒關係,讓我們看看實際的範例。
還記得那個白目的小男孩高斯嗎?
假設我們不會公式,希望使用Python來幫我們手算1~100,
按現有前面學過的東西,你可能會這樣寫:

# 別命名成sum(),它是Python已經有的東西,可以用來計算一個串列的所有值加總
# 預設算到100
def cal(end=100):
    res = 0 # res意思是result, 你要命名成ans也可以,看自己習慣
    for i in range(1, end + 1): # range的範圍記得是頭算尾不算,所以要加1
        res += i
    return res

print(cal())

如果你不會range的話可能就真的要一個一個加了!
那麼,從遞迴的角度是怎麼看待這件事情的呢?
答案是一個一個處理
既然cal(100)是1加到100,那麼cal(99)就是1加到99;
因此,cal(100)就相當於100加上cal(99)囉!
以此類推,我們可以得到cal(end)會等於end + cal(end - 1)。

於是,我們可以將函式按照這個概念重寫成下面的樣子:

# 好像哪裡怪怪的?
def cal(end):
    return end + cal(end - 1)

有沒有覺得哪邊怪怪的?
我們忘記一件事情,就是當碰到cal(1)的時候,
它本身應該要直接等於1才對,
不然按照這樣呼叫下去,cal輸入的值會變成0, -1, -2, -3, ...,
但不會停下來XD!
那我們再改寫一下:

def cal(end):
    return end + cal(end - 1) if end != 1 else 1

說明一下,上面的式子前面還沒有講過,但應該不難理解,
這是屬於Python的三元運算子,使用if跟else,
也就是說,當end != 1時,這行會回傳前面那段"end + cal(end - 1)"
否則,就回傳1(也就是當end為1時,直接回傳1就對了!)。

實際在呼叫函式的時候,例如將100代入,
我們會先呼叫cal(100),發現cal(100)要算100+cal(99);
Python會將100先記錄下來,先去算cal(99),
也就是等算出cal(99)後,再回過頭來加上100;
cal(99)又會被拆成99+cal(98),以此類推。

由於函式執行時實際上需要記憶體空間,這種還沒得到結果的函式,
往下又呼叫了東西的話,就會再疊上下一段的函式,
也就是在電腦的記憶體中會有地方放cal(100), cal(99), cal(98)...
一路堆疊上去,這樣子的結構被我們稱之為呼叫堆疊(call stack)

所以假設一個函式還沒完成,
就又在裡面呼叫另一個函式(可能是自己或別人)的話,
call stack就會越疊越高,從而占用大量記憶體。

因此,一般來說程式語言都會限制call stack最大的堆疊的函式數量,
以Python來說,可以用以下的方式來檢查call stack的限制:

>>> import sys # import我們會在後面進行介紹
>>> print(sys.getrecursionlimit())
1000

所以如果我們將剛剛的cal改成1000的話,這個程式就廢了XD!

C:\Users\Desolve>python fromzero.py
Traceback (most recent call last):
  File "fromzero.py", line 4, in <module>
    print(cal(1000))
  File "fromzero.py", line 2, in cal
    return end + cal(end - 1) if end != 1 else 1
  File "fromzero.py", line 2, in cal
    return end + cal(end - 1) if end != 1 else 1
  File "fromzero.py", line 2, in cal
    return end + cal(end - 1) if end != 1 else 1
  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded in comparison

我們總結一下建立一個遞迴函式的條件:

  1. 我們可以將一個要計算的東西拆小
    不管是拆成一部分已知一部分未知
    或是拆成數塊比較小的部分都可以。
  2. 在越拆分越小的時候,
    要至少有一個狀態是可以直接得到結果的(比如剛剛的cal(1)=1),
    因而,讓所有的區塊最後都能變成已知,從而可以計算出結果

讀者可能會有一些疑惑:
看起來遞迴好像就簡單一點,但是沒有迴圏快阿!
而且迴圏也不會有限制call stack的層數的問題,為什麼不用迴圏呢?

好問題!
我們現在示範的只是很簡單的範例,
事實上在絕大多數狀況下,可以用遞迴的問題,用迴圏也寫得出來,
這邊通常會稱使用迴圏寫出來的解法為迭代解(iterative solution)。

問題是......
越難的題目,通常遞迴解就會很常比迭代解還要容易思考,
而迭代解有時候會需要用到比較複雜的推導,才能夠寫出來!

所以如果未來讀者在學了Python以後,
可能還學了一些別的進階的應用,當面試的時候被考到白板題,
在沒有特別的狀況下,請盡量先確定給出自己遞迴解,
有信心的話,再更進一步去嘗試迭代解,會比較穩妥。

補充:
感謝FB 程式人雜誌 社團的網友Cheng-En Chuang留言補充如下,
「想更深入了解遞迴的運作的話,請參考他的解說及提供的參考資料:
有點雞蛋裡挑骨頭,但遞迴在Python裡面有深度限制是因為沒做tail-call optimization。
在其他有做tail-call optimization的語言裡面就不會有深度限制,
另外在某些語言裡面recursion也不一定比iteration慢。
甚至在Python裡面也可以用decorator達到tail-call效果:
https://towardsdatascience.com/python-stack-frames-and-tail-call-optimization-4d0ea55b0542

那我們一樣來練習題目吧!

  1. 假定有一個樓梯,你從第0階要爬到第n階,
    每次你只能選擇爬1階或者爬2階,這樣稱做一步。
    請寫出一個函式名為cs,給定n的値以後(n > 0),
    計算出從第0階爬到第n階的方法共有幾種不同的變化?
    例:
    cs(1) = 1 (1)
    cs(2) = 2 (1+1, 2)
    cs(3) = 3 (1+2, 2+1, 1+1+1)
    cs(4) = 5 (1+1+2, 2+2, 1+2+1, 2+1+1, 1+1+1+1)
    請分別給出遞迴解和迭代解。

對初學者來說,可能不是那麼容意思考,請務必好好觀察函式之間的關係。

辛苦啦!我們明天見!


上一篇
[Day 08] 從零開始學Python - 程式結構與流程語法:如果對手太弱太簡單,那不是很爽嗎?(下)
下一篇
[Day 10] 從零開始學Python - 模組與套件:借一段往日旋律,宛轉悠揚
系列文
從零開始學Python30

尚未有邦友留言

立即登入留言