Python 教程 7 — 迭代

本章介绍迭代，即重复运行某个代码块的能力。我们已经在递归一节接触了一种利用递归进行迭代的方式；在Turtle应用—简单的重复一节中，接触了另一种利用 for 循环进行迭代的方式。在本章中，我们将讨论另外一种利用 while 语句实现迭代的方式。 不过，首先我想再多谈谈有关变量赋值的问题。

1.重新赋值 #

可能你已发现对同一变量进行多次赋值是合法的。新的赋值会使得已有的变量指向 新的值（同时不再指向旧的值）。

>>> x = 5
>>> x
5
>>> x = 7
>>> x
7

第一次打印 x 时， 它的值为 5；第二次打印时，它的值是 7。

图7-1状态图展示了 重新赋值 在状态图中看起来是什么样子。

这里我想探讨一个常见的疑惑点。由于 Python 用等号（=）来赋值，所以很容易将 a = b 这样的语句理解为数学上的相等命题；即a 和 b 相等。但是这种理解是错误的。

首先，相等是一种对称关系，赋值不是。例如，在数学上，如果 a=7a=7， 则 7=a7=a。但是在 Python 中，语句 a = 7 是合法的，7 = a 则不合法。

此外，数学中，相等命题不是对的就是错的。如果 a=ba=b，那么 aa 则是永远与 bb 相等。在 Python 中，赋值语句可以使得两个变量相等， 但是这两个变量不一定必须保持这个状态：

>>> a = 5
>>> b = a    # a 和 b 现在相等
>>> a = 3    # a 和 b 不再相等
>>> b
5

第三行改变了 a 的值，但是没有改变 b 的值，所以它们不再相等了。

给变量重新赋值非常有用，但是需要小心使用。对变量频繁重新赋值会使代码难于阅读， 不易调试。

图7-1状态图

2.更新变量 #

重新赋值的一个常见方式是 更新（update），更新操作中变量的新值会取决于旧值。

>>> x = x + 1

这个语句的意思是，“获得 x 的当前值，加1，然后将 x 的值更新为新的值。”

如果试图去更新一个不存在的变量，则会返回一个错误。这是因为 Python 是先求 式子右边的值，然后再把所求的值赋给 x：

>>> x = x + 1
NameError: name 'x' is not defined

在更新变量之前，你得先 初始化（initialize） 它，通常是通过一个简单的赋值实现：

>>> x = 0
>>> x = x + 1

通过加1来更新变量叫做 递增（increment）；减1叫做 递减（decrement）。

3.while 语句 #

计算机经常被用来自动处理重复性的任务。计算机很擅长无纰漏地重复相同或者相似的任务， 而人类在这方面做的不好。在计算机程序中，重复也被称为**迭代（iteration）**。

所以 Python 提供了使其更容易实现的语言特性。其中之一就是我们在 Turtle应用—简单的重复 一节看到的 我们已经见过两个利用递归来迭代的函数： countdown  和  print_n。由于迭代如此普遍， 所以 Python 提供了使其更容易实现的语言特性。其中之一就是我们在 Turtle应用—简单的重复 一节看到的 for 语句。后面我们还会继续介绍。

另外一个用于迭代的语句是 while 。下面是使用 while 语句实现的 countdown：

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. 如果条件为真，则运行 while 语句体，运行完再返回第一步；

这种形式的流程叫做循环（loop），因为第三步后又循环回到了第一步。

循环主体应该改变一个或多个变量的值，这样的话才能让条件判断最终变为假， 从而终止循环。不然的话，循环将会永远重复下去，这被称为**无限循环（infinite loop）**。 在计算机科学家看来，洗发水的使用说明——“抹洗发水， 清洗掉，重复”便是个无限循环，这总是会让他们觉得好笑。

对于 countdown 来说，我们可以证明循环是一定会终止的：当 n 是 0 或者负数，该循环就不会执行；不然 n 通过每次循环之后慢慢减小，最终也是会变成 0 的。

有些其他循环，可能就没那么好理解了。例如：

def sequence(n):
    while n != 1:
        print(n)
        if n % 2 == 0:       # n 是偶数
            n = n / 2
        else:                # n 是奇数
            n = n*3 + 1

循环的条件是 n != 1，所以循环会一直执行到 n 等于 1，条件判断为假时循环才终止。

每次循环，该程序打印出 n 的值，然后检查它是偶数还是奇数。如果它是偶数， 那么 n 可以被2整除；如果是奇数，则它的值被替换为 n*3 + 1。例如，如果传递给 sequence 的实参为3，那么打印出的结果将会是：3、10、5、16、8、4、2、1。

由于 n 的值时增时减，所以不能轻易保证 n 会最终变成 1，或者说这个程序能够终止。 对于某些特殊的 n 的值，可以很好地证明它是可以终止的。例如，当 n 的初始值是 2 的倍数时，则每次循环后 n 一直为偶数，直到最终变为 1。上一个示例中，程序就打印了类似的序列，从16开始全部为偶数。

难点是能否证明程序对于 所有 的正整数 n 都会终止的。目前为止， 还没有人证明 或者 证伪该命题。见冰雹猜想。

我们做个练习，利用迭代而非递归，重写之前递归一节中的 print_n 函数。

4.break #

有些时候循环执行到一半你才知道循环该结束了。这种情况下，你可以使用 break 语句 来跳出循环。

例如，假设你想从用户那里获取输入，直到用户键入“done”。你可以这么写：

while True:
    line = input('> ')
    if line == 'done':
        break
    print(line)

print('Done!')

循环条件是True，其总是为真，所以该循环会一直执行直到碰到 break。

每次循环时，程序都会给出一个尖括号（>）提示。如果用户输入“done”，执行 break 语句 跳出循环。否则，程序就会一直打印出用户所输入的内容并且跳到循环开始，以下是一个运行示例：

> not done
not done
> done
Done!

while循环的这种写法很常见，因为你可以在循环的任何地方判断条件 （而不只是在循环开始），而且你可以积极地表达终止条件（“当出现这个情况是终止”）， 而不是消极地表示（“继续运行直到出现这个情况”）。

5.平方根 #

循环常用于计算数值的程序中，这类程序一般从一个大概的值开始，然后迭代式地进行改进。

例如，牛顿法 (Newton’s method) 是计算平方根的一种方法。 假设你想求 a‘的平方根。如果你从任意一个估算值:math:‘xa‘的平方根。如果你从任意一个估算值:math:‘x 开始，则可以利用下面的公式计算出更为较为精确的估算值：y=x+a/x2y=x+a/x2

例如，假定 aa 是 4，xx 是 3：

>>> a = 4
>>> x = 3
>>> y = (x + a/x) / 2
>>> y
2.16666666667

可以看到，结果与真实值（4–√=24=2）已经很接近了，如果我们用这个值 再重新运算一遍，它将得到更为接近的值。

>>> x = y
>>> y = (x + a/x) / 2
>>> y
2.00641025641

再通过多几次的运算，这个估算可以说已经是很精确了。

>>> x = y
>>> y = (x + a/x) / 2
>>> y
2.00001024003
>>> x = y
>>> y = (x + a/x) / 2
>>> y
2.00000000003

一般来说，我们事先不知道要多少步才能得到正确答案，但是我们知道当估算值不再变动时，我们就获得了正确的答案。

>>> x = y
>>> y = (x + a/x) / 2
>>> y
2.0
>>> x = y
>>> y = (x + a/x) / 2
>>> y
2.0

当 y == x 时，我们可以停止计算了。下面这个循环就是利用一个初始估值 x， 循序渐进地计算，直到估值不再变化。

while True:
    print(x)
    y = (x + a/x) / 2
    if y == x:
        break
    x = y

对于大部分a的值，这个程序运行正常，不过一般来说，检查两个浮点数是否相等比较危险。浮点数只能大约表示：大多数有理数，如 1/31/3，以及无理数， 如 2–√2，是不能用浮点数来精确表示的。

与其检查 x 和 y 的值是否完全相等，使用内置函数 abs 来计算二者之差的绝对值或数量级更为安全：

if abs(y-x) < epsilon:
    break

这里，变量 epsilon 是一个决定其精确度的值，如 0.0000001。

6.算法 #

牛顿法就是一个 算法（Algorithm） 示例：它是解决一类问题的计算机制 （这个例子中是计算平方根）。

为了理解算法是什么，先了解什么不是算法或许有点帮助。你在学习一位数乘法时， 可能背出了乘法表。实际上，你只是记住了100个确切的答案。这种知识并不是算法性的。

不过，如果你比较 “懒”，你可能就会找到一些诀窍。比如说为了计算 nn 和 9 的乘积，你可以把 n−1n−1 作为乘积的第一位数，再把 10−n10−n 作为第二位数，从而得到它们的乘积。这个诀窍是将任意个位数 与 9 相乘的普遍解法。这就是一种算法。

类似地，你所学过的进位加法、借位减法、以及长除法都是算法。算法的特点之一 就是不需要过多的脑力计算。算法是一个机械的过程，每一步都是依 据一组简单的规则跟着上一步来执行的。

执行算法的过程是很乏味的，但是设计算法就比较有趣了，不但是智 力上的挑战，更是计算机科学的核心。

人们轻轻松松或者下意识自然而然做的一些事情，往往是最难用算法来表达的。理解自然语言就是个很好的例子。我们每个人都听得懂自然语言，但是目前还没有人能够解释我们是 怎么 做到的，至少不是以算法的形式解释。

7.调试 #

当你开始写更为复杂的程序时，你会发现大部分时间都花费在调试上。更多的 代码意味着更高的出错概率，并且会有更多隐藏bug的地方。

减少调试时间的一个方法就是“对分调试”。例如，如果程序有100行，你一次检查一行，就需要100步。

相反，试着将问题拆为两半。在代码中间部分或者附近的地方，寻找一个可以检查的中间值。加上一行 print 语句（或是其他具有可验证效果的代码），然后运行程序。

如果中间点检查出错了，那么就说明程序的前半部分存在问题。如果没问题，则说明是后半部分出错了。

每次你都这样检查，就可以将需要搜索的代码行数减少一半。经过6步之后（这比100小多了），你将会找到那或者两行出错的代码，至少理论上是这样。

在实践中，可能并不能很好的确定程序的 “中间部分” 是什么，也有可能并不是那么好检查。 计算行数并且取其中间行是没有意义的。相反，多考虑下程序中哪些地方比较容易出问题，或者 哪些地方比较容易进行检查。然后选定一个检查点，在这个断点前后出现bug的概念差不多。

8.术语表 #

重新赋值（reassignment）：给已经存在的变量赋一个新的值。

更新（update）：变量的新值取决于旧值的一种赋值方法。

初始化（initialize）：给后面将要更新的变量一个初始值的一种赋值方法。

递增（increment）：通过增加变量的值的方式更新变量（通常是加 1）。

递减（decrement）：通过减少变量的值的方式来更新变量。

迭代（iteration）：利用递归或者循环的方式来重复执行代一组语句的过程。

无限循环（infinite loop）：无法满足终止条件的循环。

算法（algorithm）：解决一类问题的通用过程。

9.练习题 #

习题7-1 #

复制平方根一节中的循环，将其封装进一个叫 mysqrt 的函数中。这个函数接受 a 作为形参，选择一个合适的 x 值，并返回 a 的平方根估算值。

为测试上面的函数，编写一个名为 test_squre_root 的函数，打印出如下表格：

a   mysqrt(a)     math.sqrt(a)  diff
- --------- ------------ ----
1.0 1.0           1.0           0.0
2.0 1.41421356237 1.41421356237 2.22044604925e-16
3.0 1.73205080757 1.73205080757 0.0
4.0 2.0           2.0           0.0
5.0 2.2360679775  2.2360679775  0.0
6.0 2.44948974278 2.44948974278 0.0
7.0 2.64575131106 2.64575131106 0.0
8.0 2.82842712475 2.82842712475 4.4408920985e-16
9.0 3.0           3.0           0.0

其中第一列是 aa 的值；第二列是通过 mysqrt 计算得到的 aa 的平方根；第三列是用 math.sqrt 计算得到的平方根；第四列则是这两个平方根之差的绝对值。

习题7-2 #

内置函数 eval 接受一个字符串，并使用 Python 解释器来计算该字符串。例如：

>>> eval('1 + 2 * 3')
7
>>> import math
>>> eval('math.sqrt(5)')
2.2360679774997898
>>> eval('type(math.pi)')
<class 'float'>

编写一个名为 eval_loop 的函数，迭代式地提示用户输入，获取输入的内容，并利用 eval 来计算其值，最后打印该值。

该程序应持续运行，知道用户输入 'done'，然后返回它最后一次计算的表达式的值。

习题7-3 #

数学家斯里尼瓦瑟·拉马努金（Srinivasa Ramanujan） 发现了一个可以用来生成 1/π1/π 近似值的无穷级数（infinite series）：1π=22–√9801∑k=0∞(4k)!(1103+26390k)(k!)43964k1π=229801∑k=0∞(4k)!(1103+26390k)(k!)43964k

编写一个名为 estimate_pi 的函数，利用上面公式来估算并返回 ππ 的值。这个函数应该使用 while 循环来计算所有项的和，直到最后一项小于 1e-15 （Python 中用于表达 10−1510−15 的写法）时终止循环。你可以将该值与 math.pi 进行比较，检测是否准确。

"""This module contains a code example related to
Think Python, 2nd Edition
by Allen Downey
http://thinkpython2.com
Copyright 2015 Allen Downey
License: http://creativecommons.org/licenses/by/4.0/
"""

from __future__ import print_function, division

import math


def factorial(n):
    """Computes factorial of n recursively."""
    if n == 0:
        return 1
    else:
        recurse = factorial(n-1)
        result = n * recurse
        return result


def estimate_pi():
    """Computes an estimate of pi.
    Algorithm due to Srinivasa Ramanujan, from 
    http://en.wikipedia.org/wiki/Pi
    """
    total = 0
    k = 0
    factor = 2 * math.sqrt(2) / 9801
    while True:
        num = factorial(4*k) * (1103 + 26390*k)
        den = factorial(k)**4 * 396**(4*k)
        term = factor * num / den
        total += term
        
        if abs(term) < 1e-15:
            break
        k += 1

    return 1 / total

print(estimate_pi())

贡献者 #

1. 翻译：@lroolle
2. 校对：@bingjin
3. 参考：@carfly

推荐阅读 #

有任何问题，可以在公众号后台回复：加群，回答相应验证信息，进入互助群询问。

​Python实用宝典 (pythondict.com)
关注公众号：Python实用宝典
更多精彩文章等你阅读