Chapter 7 Iteration 迭代 · Think Python 2e 中文版

# Chapter 7 Iteration 迭代 This chapter is about iteration, which is the ability to run a block of statements repeatedly. We saw a kind of iteration, using recursion, in Section 5.8. We saw another kind, using a for loop, in Section 4.2. In this chapter we’ll see yet another kind, using a while statement. But first I want to say a little more about variable assignment. > 這一章我們講迭代，簡單說就是指重復去運行一部分代碼。在5.8的時候我們接觸了一種迭代——遞歸。在4.2我們還學了另外一種迭代——for循環。在本章，我們會見到新的迭代方式：whie語句。但我要先再稍微講一下變量賦值。 ## 7.1 Reassignment 再賦值 As you may have discovered, it is legal to make more than one assignment to the same variable. A new assignment makes an existing variable refer to a new value (and stop referring to the old value). > 你可能已經發現了，對同一個變量可以多次進行賦值。一次新的賦值使得已有的變量獲得新的值（也就不再有舊的值了。） > （譯者注：這個其實中文很好理解，英文當中詞匯邏輯關系比較緊密，但靈活程度不如中文高啊。） ```Python >>> x = 5 >>> x = 5 >>> x >>> x 5 >>> x = 7 >>> x = 7 >>> x >>> x 7 ``` The first time we display x, its value is 5; the second time, its value is 7. > 第一次顯示x的值，是5，第二次，就是7了。 Figure 7.1 shows what reassignment looks like in a state diagram. > 圖7.1表示了再賦值的操作在狀態圖中的樣子。 At this point I want to address a common source of confusion. Because Python uses the equal sign (=) for assignment, it is tempting to interpret a statement like a = b as a mathematical proposition of equality; that is, the claim that a and b are equal. But this interpretation is wrong. > 這里我就要強調一下大家常發生的誤解。因為Python使用單等號（=）來賦值，所以有的人會以為像a=b這樣的語句就如同數學上的表達一樣來表達兩者相等，這種想法是錯誤的！ First, equality is a symmetric relationship and assignment is not. For example, in mathematics, if a=7 then 7=a. But in Python, the statement a = 7 is legal and 7 = a is not. > 首先，數學上的等號所表示的相等是一個對稱的關系，而Python中等號的賦值操作是不對稱的。比如，在數學上，如果a=7，那么7=a。而在Python，a=7這個是合乎語法的，而7=a是錯誤的。 > （譯者注：這里就是說Python中等號是一種單向的運算，就是把等號右邊的值賦給等號左邊的變量，而Python中其實也有數學上相等判斷的表達式，就是雙等號（==），這個是有對稱性的，就是說a==b，那么b==a，或者a==3，3==a也可以。） Also, in mathematics, a proposition of equality is either true or false for all time. If a=b now, then a will always equal b. In Python, an assignment statement can make two variables equal, but they don’t have to stay that way: > 另外在數學上，一個相等關系要么是真，要么是假。比如a=b，那么a就會永遠等于b。在Python里面，賦值語句可以讓兩個變量相等，但可以不始終都相等，如下所示： ```Python >>> a = 5 >>> a = 5 >>> b = a # a and b are now equal a和b相等了 >>> b = a # a and b are now equal a和b相等了 >>> a = 3 # a and b are no longer equal 現在a和b就不相等了 >>> a = 3 # a and b are no longer equal 現在a和b就不相等了 >>> b >>> b 5 ``` The third line changes the value of a but does not change the value of b, so they are no longer equal. > 第三行改變了a的值，但沒有改變b的值，所以它們就不再相等了。 Reassigning variables is often useful, but you should use it with caution. If the values of variables change frequently, it can make the code difficult to read and debug. > 對變量進行再賦值總是很有用的，但你用的時候要做好備注和提示。如果變量的值頻繁變化，就可能讓代碼難以閱讀和調試。 * * * ![Figure 7.1: State diagram.](http://7xnq2o.com1.z0.glb.clouddn.com/ThinkPython7.1jpg.jpg) Figure 7.1: State diagram. * * * ## 7.2 Updating variables 更新變量 A common kind of reassignment is an update, where the new value of the variable depends on the old. > 最常見的一種再賦值就是對變量進行更新，這種情況下新的值是在舊值基礎上進行修改得到的。 ```Python >>> x = x + 1 >>> x = x + 1 ``` This means “get the current value of x, add one, and then update x with the new value.” If you try to update a variable that doesn’t exist, you get an error, because Python evaluates the right side before it assigns a value to x: > 上面的語句的意思是：獲取x當前的值，在此基礎上加1，然后把結果作為新值賦給x。如果你對不存在的變量進行更新，你就會得到錯誤了，因為Python要先進行等號右邊的運算，然后才能賦值給x。 ```Python >>> x = x + 1 >>> x = x + 1 NameError: name 'x' is not defined ``` Before you can update a variable, you have to initialize it, usually with a simple assignment: > 在你更新一個變量之前，你要先初始化一下，一般就是簡單賦值一下就可以了： ```Python >>> x = 0 >>> x = 0 >>> x = x + 1 >>> x = x + 1 ``` Updating a variable by adding 1 is called an increment; subtracting 1 is called a decrement. > 對一個變量每次加1也可以叫做一種遞增，每次減去1就可以叫做遞減了。 ## 7.3 The while statement 循環：While語句 Computers are often used to automate repetitive tasks. Repeating identical or similar tasks without making errors is something that computers do well and people do poorly. In a computer program, repetition is also called iteration. > 計算機經常被用來自動執行一些重復的任務。重復同樣的或者相似的任務，而不出錯，這是計算機特別擅長的事情，咱們人就做不到了。在一個計算機程序里面，重復操作也被叫做迭代。 We have already seen two functions, countdown and print_n, that iterate using recursion. Because iteration is so common, Python provides language features to make it easier. One is the for statement we saw in Section 4.2. We’ll get back to that later. Another is the while statement. Here is a version of countdown that uses a while statement: > 我們已經見過兩種使用了遞歸來進行迭代的函數：倒計時函數countdown，以及n次輸出函數print_n。Python還提供了一些功能來簡化迭代，因為迭代用的很普遍。其中一個就是我們在4.2中見到的for循環語句。往后我們還要復習一下它。另外一個就是while循環語句。下面就是一個使用了while循環語句來實現的倒計時函數countdown： ```Python def countdown(n): while n > 0: print(n) n = n - 1 print('Blastoff!') ``` You can almost read the while statement as if it were English. It means, “While n is greater than 0, display the value of n and then decrement n. When you get to 0, display the word Blastoff!” > while循環語句讀起來很容易，幾乎就像是英語一樣簡單。這個函數的意思是：當n大于0，就輸出n的值，然后對n減1，到n等于0的時候，就輸出單詞『Blastoff』。 More formally, here is the flow of execution for a while statement: > 更正式一點，下面是一個while循環語句的執行流程： 1. Determine whether the condition is true or false. > 判斷循環條件的真假。 2. If false, exit the while statement and continue execution at the next statement. > 如果是假的，退出while語句，繼續運行后面的語句。 3. If the condition is true, run the body and then go back to step 1. > 如果條件為真，執行循環體，然后再調回到第一步。 This type of flow is called a loop because the third step loops back around to the top. The body of the loop should change the value of one or more variables so that the condition becomes false eventually and the loop terminates. > 這種類型的運行流程叫做循環，因為第三步會循環到第一步。循環體內要改變一個或者更多變量的值，這樣循環條件最終才能變成假，然后循環才能終止。 Otherwise the loop will repeat forever, which is called an infinite loop. An endless source of amusement for computer scientists is the observation that the directions on shampoo, “Lather, rinse, repeat”, are an infinite loop. > 否則的話，條件不能為假，循環不能停止，這就叫做無限循環。計算機科學家有一個笑話，就是看到洗發液的說明：起泡，沖洗，重復；這就是一個無限循環。 In the case of countdown, we can prove that the loop terminates: if n is zero or negative, the loop never runs. Otherwise, n gets smaller each time through the loop, so eventually we have to get to 0. > 在倒計時函數countdown里面，咱們能夠保證有辦法讓循環終止：只要n小于等于0了，循環就不進行了。否則的話，n每次就會通過循環來遞減，最終還是能到0的。 For some other loops, it is not so easy to tell. For example: > 其他一些循環就不那么好描述了。比如： ```Python 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 ``` The condition for this loop is n != 1, so the loop will continue until n is 1, which makes the condition false. > 這個循環的判斷條件是n不等于1，所以循環一直進行，直到n等于1了，條件為假，就不再循環了。 Each time through the loop, the program outputs the value of n and then checks whether it is even or odd. If it is even, n is divided by 2. If it is odd, the value of n is replaced with n*3 + 1. For example, if the argument passed to sequence is 3, the resulting values of n are 3, 10, 5, 16, 8, 4, 2, 1. > 每次循環的時候，程序都輸出n的值，然后檢查一下是偶數還是奇數。如果是偶數，就把n除以2。如果是奇數，就把n替換為n乘以3再加1的值。比如讓這個函數用3做參數，也就是sequence(3)，得到的n的值就依次為：3, 10, 5, 16, 8, 4, 2, 1. Since n sometimes increases and sometimes decreases, there is no obvious proof that n will ever reach 1, or that the program terminates. For some particular values of n, we can prove termination. For example, if the starting value is a power of two, n will be even every time through the loop until it reaches 1. The previous example ends with such a sequence, starting with 16. > 有時候n在增加，有時候n在降低，所以沒有明顯證據表明n最終會到1而程序停止。對于一些特定的n值，我們能夠確保循環的終止。例如如果起始值是一個2的倍數，n每次循環過后依然是偶數，直到到達1位置。之前的例子都最終得到了一個數列，從16開始的就是了。 The hard question is whether we can prove that this program terminates for all positive values of n. So far, no one has been able to prove it or disprove it! See [WikiPedia](http://en.wikipedia.org/wiki/Collatz_conjecture) > 真正的難題是，我們能否證明這個程序對任意正數的n值都能終止循環。目前為止，沒有人能夠證明或者否定這個命題。參考[維基百科](http://en.wikipedia.org/wiki/Collatz_conjecture) As an exercise, rewrite the function print_n from Section 5.8 using iteration instead of recursion. > 做一個練習，把5.8里面的那個n次打印函數print_n用迭代的方法來實現。 ## 7.4 break 中斷 Sometimes you don’t know it’s time to end a loop until you get half way through the body. In that case you can use the break statement to jump out of the loop. > 有時候你不知道啥時候終止循環，可能正好在中間循環體的時候要終止了。這時候你就可以用break語句來跳出循環。 For example, suppose you want to take input from the user until they type done. You could write: > 比如，假設你要讓用戶輸入一些內容，當他們輸入done的時候結束。你就可以用如下的方法實現： ```Python while True: line = input('> ') if line == 'done': break print(line) print('Done!') ``` The loop condition is True, which is always true, so the loop runs until it hits the break statement. > 循環條件就是true，意味條件總是真的，所以循環就一直進行，一直到觸發了break語句才跳出。 Each time through, it prompts the user with an angle bracket. If the user types done, the break statement exits the loop. Otherwise the program echoes whatever the user types and goes back to the top of the loop. Here’s a sample run: > 每次循環的時候，程序都會有一個大于號>來提示用戶。如果用輸入了done，break語句就會讓程序跳出循環。否則的話程序會重復用戶輸入的內容，然后回到循環的頭部。下面就是一個簡單的運行例子： ```Python >>>not done >>>not done >>>not done >>>not done >>>done >>>done Done! ``` This way of writing while loops is common because you can check the condition anywhere in the loop (not just at the top) and you can express the stop condition affirmatively (“stop when this happens”) rather than negatively (“keep going until that happens”). > 這種while循環的寫法很常見，因為這樣你可以在循環的任何一個部位對條件進行檢測，而不僅僅是循環的頭部，你可以確定地表達循環停止的條件（在這種情況下就停止了），而不是消極地暗示『程序會一直運行，直到某種情況』。 ## 7.5 Square roots 平方根 Loops are often used in programs that compute numerical results by starting with an approximate answer and iteratively improving it. > 循環經常被用于進行數值運算的程序中，這種程序往往是有一個近似值作為初始值，然后逐漸迭代去改進以接近真實值。 For example, one way of computing square roots is Newton’s method. Suppose that you want to know the square root of a. If you start with almost any estimate, x, you can compute a better estimate with the following formula: > 比如，可以用牛頓法來計算平方根。加入你要知道一個數a的平方根。如果你用任意一個估計值x來開始，你可以用下面的公式獲得一個更接近的值： ``` y = \frac{x + \frac{a}{x}}{2} ``` For example, if a is 4 and x is 3: > 比如，如果a是3，x設為3： ```Python >>> a = 4 >>> a = 4 >>> x = 3 >>> x = 3 >>> y = (x + a/x) / 2 >>> y = (x + a/x) / 2 >>> y >>> y 2.16666666667 ``` The result is closer to the correct answer (square root of 4 is 2). If we repeat the process with the new estimate, it gets even closer: > 得到的結果比初始值3更接近真實值（4的平方根是2）。如果我們用這個結果做新的估計值來重復這個操作，結果就更加接近了： ```Python >>> x = y >>> x = y >>> y = (x + a/x) / 2 >>> y = (x + a/x) / 2 >>> y 2.00641025641 >>> y 2.00641025641 ``` After a few more updates, the estimate is almost exact: > 這樣進行一些次重復之后，估計值就幾乎很準確了： ```Python >>> x = y >>> x = y >>> y = (x + a/x) / 2 >>> y = (x + a/x) / 2 >>> y 2.00001024003 >>> y 2.00001024003 >>> x = y >>> x = y >>> y = (x + a/x) / 2 >>> y = (x + a/x) / 2 >>> y 2.00000000003 >>> y 2.00000000003 ``` In general we don’t know ahead of time how many steps it takes to get to the right answer, but we know when we get there because the estimate stops changing: > 一般情況下，我們不能提前知道到達正確結果需要多長時間，但是當估計值不再有明顯變化的時候我們就知道了： ```Python >>> x = y >>> x = y >>> y = (x + a/x) / 2 >>> y = (x + a/x) / 2 >>> y 2.0 >>> y 2.0 >>> x = y >>> x = y >>> y = (x + a/x) / 2 >>> y = (x + a/x) / 2 >>> y 2.0 >>> y 2.0 ``` When y == x, we can stop. Here is a loop that starts with an initial estimate, x, and improves it until it stops changing: > 當y和x相等的時候，我們就可以停止了。下面這個循環中，用一個初始值x來開始循環，然后進行改進，一直到x的值不再變化為止： ```Python while True: print(x) y = (x + a/x) / 2 if y == x: break x = y ``` For most values of a this works fine, but in general it is dangerous to test float equality. Floating-point values are only approximately right: most rational numbers, like 1/3, and irrational numbers, like √2, can’t be represented exactly with a float. > 對大多數值來說，這個循環都挺管用的，但一般來說用浮點數來測試等式是很危險的。浮點數的值只能是近似正確：大多數的有理數，比如1/3，以及無理數，比如根號2，都不能用浮點數來準確表達的。 Rather than checking whether x and y are exactly equal, it is safer to use the built-in function abs to compute the absolute value, or magnitude, of the difference between them: > 相比之下，與其對比x和y是否精確相等，倒不如以下方法更安全：用內置的絕對值函數來計算一下差值的絕對值，也叫做數量級。 ```Python if abs(y-x) < epsilon: break ``` Where epsilon has a value like 0.0000001 that determines how close is close enough. > 這里可以讓epsilon的值為like 0.0000001，差值比這個小就說明已經足夠接近了。 ## 7.6 Algorithms 算法 Newton’s method is an example of an algorithm: it is a mechanical process for solving a category of problems (in this case, computing square roots). > 牛頓法是算法的一個例子：通過一系列機械的步驟來解決一類問題（在本章中是用來計算平方根）。 To understand what an algorithm is, it might help to start with something that is not an algorithm. When you learned to multiply single-digit numbers, you probably memorized the multiplication table. In effect, you memorized 100 specific solutions. That kind of knowledge is not algorithmic. > 要理解算法是什么，先從一些不是算法的內容來開始也許會有所幫助。當你學個位數字乘法的時候，你可能要背下來整個乘法表。實際上你記住了100個特定的算式。這種知識就不是算法。 But if you were “lazy”, you might have learned a few tricks. For example, to find the product of n and 9, you can write n?1 as the first digit and 10?n as the second digit. This trick is a general solution for multiplying any single-digit number by 9. That’s an algorithm! > 但如果你很『懶』，你就可能會有一些小技巧。比如找到一個n與9的成績，你可以把n-1寫成第一位，10-n攜程第二位。這個技巧是應對任何個位數字乘以9的算式。這就是一個算法了！ Similarly, the techniques you learned for addition with carrying, subtraction with borrowing, and long division are all algorithms. One of the characteristics of algorithms is that they do not require any intelligence to carry out. They are mechanical processes where each step follows from the last according to a simple set of rules. > 相似地，你學過的進位的加法，借位的減法，以及長除法，都是算法。這些算法的一個共同特點就是不需要任何智力就能進行。它們都是機械的過程，每一步都跟隨上一步，遵循著很簡單的一套規則。 Executing algorithms is boring, but designing them is interesting, intellectually challenging, and a central part of computer science. > 執行算法是很無聊的，但設計算法很有趣，是智力上的一種挑戰，也是計算機科學的核心部分。 Some of the things that people do naturally, without difficulty or conscious thought, are the hardest to express algorithmically. Understanding natural language is a good example. We all do it, but so far no one has been able to explain how we do it, at least not in the form of an algorithm. > 有的事情人們平時做起來很簡單，甚至都不用思考，這些事情往往最難用算法來表達。比如理解自然語言就是個例子。我們都能理解自然語言，但目前為止還沒有人能解釋我們到底是怎么做到的，至少沒有人把這個過程歸納出算法的形式。 ## 7.7 Debugging 調試 As you start writing bigger programs, you might find yourself spending more time debugging. More code means more chances to make an error and more places for bugs to hide. > 現在你已經開始寫一些比較大的程序了，你可能發現自己比原來花更多時間來調試了。代碼越多，也就意味著出錯的可能也越大了，bug也有了更多的藏身之處了。 One way to cut your debugging time is “debugging by bisection”. For example, if there are 100 lines in your program and you check them one at a time, it would take 100 steps. Instead, try to break the problem in half. Look at the middle of the program, or near it, for an intermediate value you can check. Add a print statement (or something else that has a verifiable effect) and run the program. > 『對折調試』是一種節省調試時間的方法。比如，如果你的程序有100行，你檢查一遍就要大概100步了。而對折方法就是把程序分成兩半。看程序中間位置，或者靠近中間位置的，檢查一些中間值。在這些位置添加一些print語句（或者其他能夠能起到驗證效果的東西），然后運行程序。 If the mid-point check is incorrect, there must be a problem in the first half of the program. If it is correct, the problem is in the second half. > 如果中間點檢查出錯了，那必然是程序的前半部分有問題。如果中間點沒調試，那問題就是在后半段了。 Every time you perform a check like this, you halve the number of lines you have to search. After six steps (which is fewer than 100), you would be down to one or two lines of code, at least in theory. > 每次你都這樣檢查，你就讓你要檢查的代碼數量減半了。一般六步之后（遠小于100次了），理論上你就差不多已經到代碼的末尾一兩行了。 In practice it is not always clear what the “middle of the program” is and not always possible to check it. It doesn’t make sense to count lines and find the exact midpoint. Instead, think about places in the program where there might be errors and places where it is easy to put a check. Then choose a spot where you think the chances are about the same that the bug is before or after the check. > 在實際操作當中，程序中間位置并不是總那么明確，也未必就很容易去檢查。所以不用數行數來找確定的中間點。相反的，只要考慮一下程序中哪些地方容易調試，然后哪些地方進行檢驗比較容易就行了。然后你就在你考慮好的位置檢驗一下看看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 Exercises 練習 ### Exercise 1 練習1 Copy the loop from Section 7.5 and encapsulate it in a function called mysqrt that takes a as a parameter, chooses a reasonable value of x, and returns an estimate of the square root of a. > 從7.5復制一個循環，然后改寫成名字叫做mysqrt的函數，該函數用一個a作為參數，選擇一個適當的起始值x，然后返回a的平方根的近似值。 To test it, write a function named test_square_root that prints a table like this: > 測試這個函數，寫一個叫做test_suqare_root的函數來輸出以下這樣的表格： ![](http://7xnq2o.com1.z0.glb.clouddn.com/ThinkPython%E5%B9%B3%E6%96%B9%E6%A0%B9.jpg) The first column is a number, a; the second column is the square root of acomputed with mysqrt; the third column is the square root computed by math.sqrt; the fourth column is the absolute value of the difference between the two estimates. > 第一列是數a；第二列是咱們自己寫的函數mysqrt計算出來的平方根，第三行是用Python內置的math.sqrt函數計算的平方根，最后一行是這兩者的差值的絕對值。 ### Exercise 2 練習2 The built-in function eval takes a string and evaluates it using the Python interpreter. For example: > Python的內置函數eval接收字符串作為參數，然后用Python的解釋器來運行。例如： ```Python >>> eval('1 + 2 * 3') >>> eval('1 + 2 * 3') 7 >>> import math >>> import math >>> eval('math.sqrt(5)') >>> eval('math.sqrt(5)') 2.2360679774997898 >>> eval('type(math.pi)') >>> eval('type(math.pi)') <class 'float'> ``` Write a function called eval_loop that iteratively prompts the user, takes the resulting input and evaluates it using eval, and prints the result. > 寫一個叫做eval_loop的函數，交互地提醒用戶，獲取輸入，然后用eval對輸入進行運算，把結果打印出來。 It should continue until the user enters 'done', and then return the value of the last expression it evaluated. > 這個程序要一直運行，直到用戶輸入『done』才停止，然后輸出最后一次計算的表達式的值。 ## Exercise 3 練習3 The mathematician Srinivasa Ramanujan found an infinite series that can be used to generate a numerical approximation of 1 / π: > 傳奇的數學家拉馬努金發現了一個無窮級數（1914年的論文），能夠用來計算圓周率倒數的近似值： ![](http://7xnq2o.com1.z0.glb.clouddn.com/ThinkPython7.e3.jpg) （譯者注：這位拉馬努金是一位非常杰出的數學家，自學成才，以數論為主要研究內容，可惜33歲的時候就英年早逝。他被哈代譽為超越希爾伯特的天才。） Write a function called estimate_pi that uses this formula to compute and return an estimate of π. It should use a while loop to compute terms of the summation until the last term is smaller than 1e-15 (which is Python notation for 10?15). You can check the result by comparing it to math.pi. [Solution](http://thinkpython2.com/code/pi.py) > 寫一個名叫estimate_pi的函數，用上面這個方程來計算并返回一個圓周率π的近似值。要使用一個while循環來計算出總和的每一位，最后一位要小于10的-15次方。你可以對比一下計算結果和Python內置的math.pi。 > [樣例代碼](http://thinkpython2.com/code/pi.py)