# 第七章 迭代

这一章我们讲迭代,简单说就是指重复去运行一部分代码。在5.8的时候我们接触了一种迭代——递归。在4.2我们还学了另外一种迭代——for循环。在本章,我们会见到新的迭代方式:whie语句。但我要先再稍微讲一下变量赋值。

# 7.1 再赋值

你可能已经发现了,对同一个变量可以多次进行赋值。一次新的赋值使得已有的变量获得新的值(也就不再有旧的值了。)

(译者注:这个其实中文很好理解,英文当中词汇逻辑关系比较紧密,但灵活程度不如中文高啊。)

    >>> x = 5
    >>> x
    5
    >>> x = 7
    >>> x
    7
1
2
3
4
5
6

第一次显示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里面,赋值语句可以让两个变量相等,但可以不始终都相等,如下所示:

    >>> 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
1
2
3
4
5

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

对变量进行再赋值总是很有用的,但你用的时候要做好备注和提示。如果变量的值频繁变化,就可能让代码难以阅读和调试。


Figure 7.1: State diagram. Figure 7.1: State diagram.


# 7.2 更新变量

最常见的一种再赋值就是对变量进行更新,这种情况下新的值是在旧值基础上进行修改得到的。

    >>> x = x + 1
    
1
2

上面的语句的意思是:获取x当前的值,在此基础上加1,然后把结果作为新值赋给x。如果你对不存在的变量进行更新,你就会得到错误了,因为Python要先进行等号右边的运算,然后才能赋值给x。

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

在你更新一个变量之前,你要先初始化一下,一般就是简单赋值一下就可以了:

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

对一个变量每次加1也可以叫做一种递增,每次减去1就可以叫做递减了。

# 7.3 循环:While语句

计算机经常被用来自动执行一些重复的任务。重复同样的或者相似的任务,而不出错,这是计算机特别擅长的事情,咱们人就做不到了。在一个计算机程序里面,重复操作也被叫做迭代。

我们已经见过两种使用了递归来进行迭代的函数:倒计时函数countdown,以及n次输出函数print_n。Python还提供了一些功能来简化迭代,因为迭代用的很普遍。其中一个就是我们在4.2中见到的for循环语句。往后我们还要复习一下它。另外一个就是while循环语句。下面就是一个使用了while循环语句来实现的倒计时函数countdown:

    def countdown(n):
        while n > 0:
            print(n)
            n = n - 1
        print('Blastoff!')
1
2
3
4
5

while循环语句读起来很容易,几乎就像是英语一样简单。这个函数的意思是:当n大于0,就输出n的值,然后对n减1,到n等于0的时候,就输出单词『Blastoff』。

更正式一点,下面是一个while循环语句的执行流程:

  1. 判断循环条件的真假。

  2. 如果是假的,退出while语句,继续运行后面的语句。

  3. 如果条件为真,执行循环体,然后再调回到第一步。

这种类型的运行流程叫做循环,因为第三步会循环到第一步。循环体内要改变一个或者更多变量的值,这样循环条件最终才能变成假,然后循环才能终止。

否则的话,条件不能为假,循环不能停止,这就叫做无限循环。计算机科学家有一个笑话,就是看到洗发液的说明:起泡,冲洗,重复;这就是一个无限循环。

在倒计时函数countdown里面,咱们能够保证有办法让循环终止:只要n小于等于0了,循环就不进行了。否则的话,n每次就会通过循环来递减,最终还是能到0的。

其他一些循环就不那么好描述了。比如:

    
    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
1
2
3
4
5
6
7
8

这个循环的判断条件是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值都能终止循环。目前为止,没有人能够证明或者否定这个命题。

参考维基百科 做一个练习,把5.8里面的那个n次打印函数print_n用迭代的方法来实现。

# 7.4 中断

有时候你不知道啥时候终止循环,可能正好在中间循环体的时候要终止了。这时候你就可以用break语句来跳出循环。 比如,假设你要让用户输入一些内容,当他们输入done的时候结束。你就可以用如下的方法实现:

    
    while True:
        line = input('> ')
        if line == 'done':
            break
            print(line)
        print('Done!')
1
2
3
4
5
6
7

循环条件就是true,意味条件总是真的,所以循环就一直进行,一直到触发了break语句才跳出。

每次循环的时候,程序都会有一个大于号>来提示用户。如果用输入了done,break语句就会让程序跳出循环。否则的话程序会重复用户输入的内容,然后回到循环的头部。下面就是一个简单的运行例子:

    >>>not done
    >>>not done
    >>>done
    Done!
1
2
3
4

这种while循环的写法很常见,因为这样你可以在循环的任何一个部位对条件进行检测,而不仅仅是循环的头部,你可以确定地表达循环停止的条件(在这种情况下就停止了),而不是消极地暗示『程序会一直运行,直到某种情况』。

# 7.5 平方根

循环经常被用于进行数值运算的程序中,这种程序往往是有一个近似值作为初始值,然后逐渐迭代去改进以接近真实值。

比如,可以用牛顿法来计算平方根。加入你要知道一个数a的平方根。如果你用任意一个估计值x来开始,你可以用下面的公式获得一个更接近的值:

比如,如果a是3,x设为3:

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

得到的结果比初始值3更接近真实值(4的平方根是2)。如果我们用这个结果做新的估计值来重复这个操作,结果就更加接近了:

    
    >>> x = y
    >>> y = (x + a/x) / 2
    >>> y 
    2.00641025641
1
2
3
4
5

这样进行一些次重复之后,估计值就几乎很准确了:

    >>> x = y
    >>> y = (x + a/x) / 2
    >>> y 2.00001024003
    >>> x = y
    >>> y = (x + a/x) / 2
    >>> y
    2.00000000003
1
2
3
4
5
6
7

一般情况下,我们不能提前知道到达正确结果需要多长时间,但是当估计值不再有明显变化的时候我们就知道了:

    
    >>> x = y
    >>> y = (x + a/x) / 2
    >>> y
    2.0
1
2
3
4
5

当y和x相等的时候,我们就可以停止了。下面这个循环中,用一个初始值x来开始循环,然后进行改进,一直到x的值不再变化为止:

    while True:
        print(x)
        y = (x + a/x) / 2
        if y == x:
            break
        x = y
1
2
3
4
5
6

对大多数值来说,这个循环都挺管用的,但一般来说用浮点数来测试等式是很危险的。浮点数的值只能是近似正确:大多数的有理数,比如1/3,以及无理数,比如根号2,都不能用浮点数来准确表达的。

相比之下,与其对比x和y是否精确相等,倒不如以下方法更安全:用内置的绝对值函数来计算一下差值的绝对值,也叫做数量级。

    
    if abs(y-x) < epsilon:
        break
1
2
3

这里可以让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的解释器来运行。例如:

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

写一个叫做eval_loop的函数,交互地提醒用户,获取输入,然后用eval对输入进行运算,把结果打印出来。

这个程序要一直运行,直到用户输入『done』才停止,然后输出最后一次计算的表达式的值。

# 练习3

传奇的数学家拉马努金发现了一个无穷级数(1914年的论文),能够用来计算圆周率倒数的近似值:

(译者注:这位拉马努金是一位非常杰出的数学家,自学成才,以数论为主要研究内容,可惜33岁的时候就英年早逝。他被哈代誉为超越希尔伯特的天才。)

写一个名叫estimate_pi的函数,用上面这个方程来计算并返回一个圆周率π的近似值。要使用一个while循环来计算出总和的每一位,最后一位要小于10的-15次方。你可以对比一下计算结果和Python内置的math.pi。

样例代码