第七章:迭代

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

重新赋值

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

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

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

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

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

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

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

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

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

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

图7-1状态图

图7-1状态图

更新变量

重新赋值的一个常见方式是 更新(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)

while 语句

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

所以 Python 提供了使其更容易实现的语言特性。其中之一就是我们在简单的重复一节看到的 我们已经见过两个利用递归来迭代的函数: `countdownprint_n。由于迭代如此普遍, 所以 Python 提供了使其更容易实现的语言特性。其中之一就是我们在简单的重复一节看到的 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 都会终止的。目前为止, 还没有人证明 或者 证伪该命题。(见: http://en.wikipedia.org/wiki/Collatz_conjecture 。)

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

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循环的这种写法很常见,因为你可以在循环的任何地方判断条件 (而不只是在循环开始),而且你可以积极地表达终止条件(“当出现这个情况是终止”), 而不是消极地表示(“继续运行直到出现这个情况”)。

平方根

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

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

\[y = \frac{x + a/x}{2}\]

例如,假定 \(a\) 是 4,\(x\) 是 3:

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

可以看到,结果与真实值(\(\sqrt{4} = 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/3\),以及无理数, 如 \(\sqrt{2}\),是不能用浮点数来精确表示的。

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

if abs(y-x) < epsilon:
    break

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

算法

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

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

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

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

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

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

调试

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

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

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

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

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

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

术语表

重新赋值(reassignment):
给已经存在的变量赋一个新的值。
更新(update):
变量的新值取决于旧值的一种赋值方法。
初始化(initialize):
给后面将要更新的变量一个初始值的一种赋值方法。
递增(increment):
通过增加变量的值的方式更新变量(通常是加 1)。
递减(decrement):
通过减少变量的值的方式来更新变量。
迭代(iteration):
利用递归或者循环的方式来重复执行代一组语句的过程。
无限循环(infinite loop):
无法满足终止条件的循环。
算法(algorithm):
解决一类问题的通用过程。

练习题

习题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

其中第一列是 \(a\) 的值;第二列是通过 mysqrt 计算得到的 \(a\) 的平方根;第三列是用 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 / \pi\) 近似值的无穷级数(infinite series):

\[\frac{1}{\pi} = \frac{2\sqrt{2}}{9801} \sum^\infty_{k=0} \frac{(4k)!(1103+26390k)}{(k!)^4 396^{4k}}\]

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

答案: http://thinkpython2.com/code/pi.py

贡献者

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