# 第七章 迭代 這一章我們講迭代，簡單說就是指重復去運行一部分代碼。在 5.8 的時候我們接觸了一種迭代——遞歸。在 4.2 我們還學了另外一種迭代——for 循環。在本章，我們會見到新的迭代方式：whie 語句。但我要先再稍微講一下變量賦值。 ## 7.1 再賦值 你可能已經發現了，對同一個變量可以多次進行賦值。一次新的賦值使得已有的變量獲得新的值（也就不再有舊的值了。） >（譯者注：這個其實中文很好理解，英文當中詞匯邏輯關系比較緊密，但靈活程度不如中文高啊。） ```py >>> x = 5 >>> x 5 >>> x = 7 >>> x 7 ``` 第一次顯示 x 的值，是 5，第二次，就是 7 了。 圖 7.1 表示了再賦值的操作在狀態圖中的樣子。 這里我就要強調一下大家常發生的誤解。因為 Python 使用單等號（=）來賦值，所以有的人會以為像 a=b 這樣的語句就如同數學上的表達一樣來表達兩者相等，這種想法是錯誤的！ 首先，數學上的等號所表示的相等是一個對稱的關系，而 Python 中等號的賦值操作是不對稱的。比如，在數學上，如果 a=7，那么 7=a。而在 Python，a=7 這個是合乎語法的，而 7=a 是錯誤的。 （譯者注：這里就是說 Python 中等號是一種單向的運算，就是把等號右邊的值賦給等號左邊的變量，而 Python 中其實也有數學上相等判斷的表達式，就是雙等號（==），這個是有對稱性的，就是說 a==b，那么 b==a，或者 a==3，3==a 也可以。） 另外在數學上，一個相等關系要么是真，要么是假。比如 a=b，那么 a 就會永遠等于 b。在 Python 里面，賦值語句可以讓兩個變量相等，但可以不始終都相等，如下所示： ```py >>> a = 5 >>> b = a # a and b are now equal a 和 b 相等了 >>> a = 3 # a and b are no longer equal 現在 a 和 b 就不相等了 >>> b 5 ``` 第三行改變了 a 的值，但沒有改變 b 的值，所以它們就不再相等了。 對變量進行再賦值總是很有用的，但你用的時候要做好備注和提示。如果變量的值頻繁變化，就可能讓代碼難以閱讀和調試。 ________________________________________  Figure 7.1: State diagram. ________________________________________ ## 7.2 更新變量 最常見的一種再賦值就是對變量進行更新，這種情況下新的值是在舊值基礎上進行修改得到的。 ```py >>> x = x + 1 ``` 上面的語句的意思是：獲取 x 當前的值，在此基礎上加 1，然后把結果作為新值賦給 x。如果你對不存在的變量進行更新，你就會得到錯誤了，因為 Python 要先進行等號右邊的運算，然后才能賦值給 x。 ```py >>> x = x + 1 NameError: name 'x' is not defined ``` 在你更新一個變量之前，你要先初始化一下，一般就是簡單賦值一下就可以了： ```py >>> x = 0 >>> x = x + 1 ``` 對一個變量每次加 1 也可以叫做一種遞增，每次減去 1 就可以叫做遞減了。 ## 7.3 循環：While 語句 計算機經常被用來自動執行一些重復的任務。重復同樣的或者相似的任務，而不出錯，這是計算機特別擅長的事情，咱們人就做不到了。在一個計算機程序里面，重復操作也被叫做迭代。 我們已經見過兩種使用了遞歸來進行迭代的函數：倒計時函數 countdown，以及 n 次輸出函數 print_n。Python 還提供了一些功能來簡化迭代，因為迭代用的很普遍。其中一個就是我們在 4.2 中見到的 for 循環語句。往后我們還要復習一下它。另外一個就是 while 循環語句。下面就是一個使用了 while 循環語句來實現的倒計時函數 countdown： ```py def countdown(n): while n > 0: print(n) n = n - 1 print('Blastoff!') ``` while 循環語句讀起來很容易，幾乎就像是英語一樣簡單。這個函數的意思是：當 n 大于 0，就輸出 n 的值，然后對 n 減 1，到 n 等于 0 的時候，就輸出單詞『Blastoff』。 更正式一點，下面是一個 while 循環語句的執行流程： 1. 判斷循環條件的真假。 2. 如果是假的，退出 while 語句，繼續運行后面的語句。 3. 如果條件為真，執行循環體，然后再調回到第一步。 這種類型的運行流程叫做循環，因為第三步會循環到第一步。循環體內要改變一個或者更多變量的值，這樣循環條件最終才能變成假，然后循環才能終止。 否則的話，條件不能為假，循環不能停止，這就叫做無限循環。計算機科學家有一個笑話，就是看到洗發液的說明：起泡，沖洗，重復；這就是一個無限循環。 在倒計時函數 countdown 里面，咱們能夠保證有辦法讓循環終止：只要 n 小于等于 0 了，循環就不進行了。否則的話，n 每次就會通過循環來遞減，最終還是能到 0 的。 其他一些循環就不那么好描述了。比如： ```py def sequence(n): while n != 1: print(n) if n % 2 == 0: # n is even n = n / 2 else: # n is odd n = n*3 + 1 ``` 這個循環的判斷條件是 n 不等于 1，所以循環一直進行，直到 n 等于 1 了，條件為假，就不再循環了。 每次循環的時候，程序都輸出 n 的值，然后檢查一下是偶數還是奇數。如果是偶數，就把 n 除以 2。如果是奇數，就把 n 替換為 n 乘以 3 再加 1 的值。比如讓這個函數用 3 做參數，也就是 sequence(3)，得到的 n 的值就依次為：3, 10, 5, 16, 8, 4, 2, 1. 有時候 n 在增加，有時候 n 在降低，所以沒有明顯證據表明 n 最終會到 1 而程序停止。對于一些特定的 n 值，我們能夠確保循環的終止。例如如果起始值是一個 2 的倍數，n 每次循環過后依然是偶數，直到到達 1 位置。之前的例子都最終得到了一個數列，從 16 開始的就是了。 真正的難題是，我們能否證明這個程序對任意正數的 n 值都能終止循環。目前為止，沒有人能夠證明或者否定這個命題。 參考[維基百科](http://en.wikipedia.org/wiki/Collatz_conjecture) 做一個練習，把 5.8 里面的那個 n 次打印函數 print_n 用迭代的方法來實現。 ## 7.4 中斷 有時候你不知道啥時候終止循環，可能正好在中間循環體的時候要終止了。這時候你就可以用 break 語句來跳出循環。 比如，假設你要讓用戶輸入一些內容，當他們輸入 done 的時候結束。你就可以用如下的方法實現： ```py while True: line = input('> ') if line == 'done': break print(line) print('Done!') ``` 循環條件就是 true，意味條件總是真的，所以循環就一直進行，一直到觸發了 break 語句才跳出。 每次循環的時候，程序都會有一個大于號>來提示用戶。如果用輸入了 done，break 語句就會讓程序跳出循環。否則的話程序會重復用戶輸入的內容，然后回到循環的頭部。下面就是一個簡單的運行例子： ```py >>>not done >>>not done >>>done Done! ``` 這種 while 循環的寫法很常見，因為這樣你可以在循環的任何一個部位對條件進行檢測，而不僅僅是循環的頭部，你可以確定地表達循環停止的條件（在這種情況下就停止了），而不是消極地暗示『程序會一直運行，直到某種情況』。 ## 7.5 平方根 循環經常被用于進行數值運算的程序中，這種程序往往是有一個近似值作為初始值，然后逐漸迭代去改進以接近真實值。 比如，可以用牛頓法來計算平方根。加入你要知道一個數 a 的平方根。如果你用任意一個估計值 x 來開始，你可以用下面的公式獲得一個更接近的值： $$y = \frac{x + \frac{a}{x}}{2}$$ 比如，如果 a 是 3，x 設為 3： ```py >>> a = 4 >>> x = 3 >>> y = (x + a/x) / 2 >>> y 2.16666666667 ``` 得到的結果比初始值 3 更接近真實值（4 的平方根是 2）。如果我們用這個結果做新的估計值來重復這個操作，結果就更加接近了： ```py >>> x = y >>> y = (x + a/x) / 2 >>> y 2.00641025641 ``` 這樣進行一些次重復之后，估計值就幾乎很準確了： ```py >>> x = y >>> y = (x + a/x) / 2 >>> y 2.00001024003 >>> x = y >>> y = (x + a/x) / 2 >>> y 2.00000000003 ``` 一般情況下，我們不能提前知道到達正確結果需要多長時間，但是當估計值不再有明顯變化的時候我們就知道了： ```py >>> x = y >>> y = (x + a/x) / 2 >>> y 2.0 ``` 當 y 和 x 相等的時候，我們就可以停止了。下面這個循環中，用一個初始值 x 來開始循環，然后進行改進，一直到 x 的值不再變化為止： ```py while True: print(x) y = (x + a/x) / 2 if y == x: break x = y ``` 對大多數值來說，這個循環都挺管用的，但一般來說用浮點數來測試等式是很危險的。浮點數的值只能是近似正確：大多數的有理數，比如 1/3，以及無理數，比如根號 2，都不能用浮點數來準確表達的。 相比之下，與其對比 x 和 y 是否精確相等，倒不如以下方法更安全：用內置的絕對值函數來計算一下差值的絕對值，也叫做數量級。 ```py if abs(y-x) < epsilon: break ``` 這里可以讓 epsilon 的值為 like 0.0000001，差值比這個小就說明已經足夠接近了。 ## 7.6 算法 牛頓法是算法的一個例子：通過一系列機械的步驟來解決一類問題（在本章中是用來計算平方根）。 要理解算法是什么，先從一些不是算法的內容來開始也許會有所幫助。當你學個位數字乘法的時候，你可能要背下來整個乘法表。實際上你記住了 100 個特定的算式。這種知識就不是算法。 但如果你很『懶』，你就可能會有一些小技巧。比如找到一個 n 與 9 的成績，你可以把 n-1 寫成第一位，10-n 攜程第二位。這個技巧是應對任何個位數字乘以 9 的算式。這就是一個算法了！ 類似地，你學過的進位的加法，借位的減法，以及長除法，都是算法。這些算法的一個共同特點就是不需要任何智力就能進行。它們都是機械的過程，每一步都跟隨上一步，遵循著很簡單的一套規則。 執行算法是很無聊的，但設計算法很有趣，是智力上的一種挑戰，也是計算機科學的核心部分。 有的事情人們平時做起來很簡單，甚至都不用思考，這些事情往往最難用算法來表達。比如理解自然語言就是個例子。我們都能理解自然語言，但目前為止還沒有人能解釋我們到底是怎么做到的，至少沒有人把這個過程歸納出算法的形式。 ## 7.7 調試 現在你已經開始寫一些比較大的程序了，你可能發現自己比原來花更多時間來調試了。代碼越多，也就意味著出錯的可能也越大了，bug 也有了更多的藏身之處了。 『對折調試』是一種節省調試時間的方法。比如，如果你的程序有 100 行，你檢查一遍就要大概 100 步了。而對折方法就是把程序分成兩半。看程序中間位置，或者靠近中間位置的，檢查一些中間值。在這些位置添加一些 print 語句（或者其他能夠能起到驗證效果的東西），然后運行程序。 如果中間點檢查出錯了，那必然是程序的前半部分有問題。如果中間點沒調試，那問題就是在后半段了。 每次你都這樣檢查，你就讓你要檢查的代碼數量減半了。一般六步之后（遠小于 100 次了），理論上你就差不多已經到代碼的末尾一兩行了。 在實際操作當中，程序中間位置并不是總那么明確，也未必就很容易去檢查。所以不用數行數來找確定的中間點。相反的，只要考慮一下程序中哪些地方容易調試，然后哪些地方進行檢驗比較容易就行了。然后你就在你考慮好的位置檢驗一下看看 bug 是在那個位置之前還是之后。 ## 7.8 Glossary 術語列表 reassignment: Assigning a new value to a variable that already exists. >再賦值：對一個已經存在的有值變量賦予一個新的值。 update: An assignment where the new value of the variable depends on the old. >更新：根據一個變量的舊值，進行一定的修改，再賦值給這個變量。 initialization: An assignment that gives an initial value to a variable that will be updated. >初始化：給一個變量初始值，以便于后續進行更新。 increment: An update that increases the value of a variable (often by one). >遞增：每次給一個變量增加一定的值（一般是加 1） decrement: An update that decreases the value of a variable. >遞減：每次給一個變量減去一定的值。 iteration: Repeated execution of a set of statements using either a recursive function call or a loop. >迭代：重復執行一系列語句，使用遞歸函數調用的方式，或者循環的方式。 infinite loop: A loop in which the terminating condition is never satisfied. >無限循環：終止條件永遠無法滿足的循環。 algorithm: A general process for solving a category of problems. >算法：解決某一類問題的一系列通用的步驟。 ## 7.9 練習 ### 練習 1 從 7.5 復制一個循環，然后改寫成名字叫做 mysqrt 的函數，該函數用一個 a 作為參數，選擇一個適當的起始值 x，然后返回 a 的平方根的近似值。 測試這個函數，寫一個叫做 test_suqare_root 的函數來輸出以下這樣的表格：  第一列是數 a；第二列是咱們自己寫的函數 mysqrt 計算出來的平方根，第三行是用 Python 內置的 math.sqrt 函數計算的平方根，最后一行是這兩者的差值的絕對值。 ### 練習 2 Python 的內置函數 eval 接收字符串作為參數，然后用 Python 的解釋器來運行。例如： ```py >>> eval('1 + 2 * 3') 7 >>> import math >>> eval('math.sqrt(5)') 2.2360679774997898 >>> eval('type(math.pi)') <class 'float'> ``` 寫一個叫做 eval_loop 的函數，交互地提醒用戶，獲取輸入，然后用 eval 對輸入進行運算，把結果打印出來。 這個程序要一直運行，直到用戶輸入『done』才停止，然后輸出最后一次計算的表達式的值。 ## 練習 3 傳奇的數學家拉馬努金發現了一個無窮級數（1914 年的論文），能夠用來計算圓周率倒數的近似值：  （譯者注：這位拉馬努金是一位非常杰出的數學家，自學成才，以數論為主要研究內容，可惜 33 歲的時候就英年早逝。他被哈代譽為超越希爾伯特的天才。） 寫一個名叫 estimate_pi 的函數，用上面這個方程來計算并返回一個圓周率π的近似值。要使用一個 while 循環來計算出總和的每一位，最后一位要小于 10 的-15 次方。你可以對比一下計算結果和 Python 內置的 math.pi。 >[樣例代碼](http://thinkpython2.com/code/pi.py)