分享程序员开发的那些事...
更新时间：2022-06-15 18:45:01
Python编程从0到1
（视频教学版）
张頔 著
本章将介绍程序设计的入门方法，主要分为以下3个阶段进行介绍。
第1阶段：1.1～1.6节
这部分介绍最基本的知识，如历史（1.1节）、表达式（1.2节）、运行程序（1.3节）、内建类型（1.4节）、流程控制结构（1.5节）和输入输出（1.6节）。这部分内容力图精简（尤其是内建类型一节），其目的在于让学习者尽快进入编程训练中。
本阶段还会简要介绍函数的定义方法（1.5.6节），以便于在示例和练习中使用。完整论述函数这一主题则是第2章将要介绍的内容。本节介绍的内建类型（列表、字典等）则还会在第3章中深入讨论。
第2阶段：1.7～1.9节
本阶段通过一组编码实例展示前述程序设计基本方法的应用。学习者，尤其是初学者，在本阶段应进行一定数量的编码练习。本阶段的示例又分为两个层次：
本阶段的最后引入了算法复杂度的初步概念及标记方法（1.9节）。
第3阶段：1.10～1.11节
本阶段主要讲述了异常处理机制（1.10节）。这是写出Python完整代码必不可少的知识。优秀的工程师能够全面地考虑各种意外情况并加以处理，从而设计出健壮的系统。在实际工作中，异常处理的重要性足以比肩本章其他全部内容，然而在初学阶段不便展开，故本部分篇幅短小，并设置为“节”归入第1章。
此外，本阶段还简要介绍了PDB调试工具（1.11节）。
在莱布尼茨①（1646～1716）生活的时代，哲学家们开始研究计算问题。人们希望能够“发现一种普遍化的数学，能用来以计算代替思考”②。1847年，英国数学家布尔建立了“布尔代数”，他创造了一套符号系统和运算法则，利用代数方法研究逻辑问题，奠定了数理逻辑的基础。19世纪70年代，人类进入电气时代。从此人类文明开始不断寻找能够完成布尔运算的单元器件，从继电器到电子管、晶体管，再到量子比特。1936年，英国数学家、逻辑学家艾伦·图灵提出了著名的图灵机模型，一台具有以下性质的机器：
图灵模型是计算机时代开启的标志。第二次世界大战则加速了人类在这条道路上的探索进程。战后，数学家从具体的计算问题（如密码破译、原子弹爆炸）中解放出来，思考计算机器的统一结构。1946年，美籍匈牙利数学家冯·诺依曼提出了奠定现代电子计算机基础的结构：
这个结构被命名为冯·诺依曼结构（或普林斯顿结构）。从此科学家和工程师们大展身手。从微观上，科学家们不断寻找更好的开关器件，以实现布尔逻辑的级联运算。从宏观上，工程师们不断地构建出更加庞大的软/硬件体系。在20世纪50～70年代，以Dijkstra为代表的计算机科学家们系统性地发展和建设了这门学科。程序设计和操作系统等领域开始出现完整的理论体系。
随着计算机技术的发展，各种各样的程序设计语言被创造出来。同其他世界性人类语言（如英语、汉语）一样，程序设计语言也将不同种族和不同生活习惯的人们联系起来。
Python诞生于1991年，设计者是Guido van Rossum。时至今日，它已经成为最流行的语言之一。相较其他主流语言（C/C++、Java、C#），其发展壮大颇具传奇色彩，而其性能并不出众的事实又为这传奇增色三分。仅从这一点看，Python就是值得学习的程序设计语言。
【思考和扩展练习】
（1）检索互联网，了解“编译型程序”和“解释型程序”，各有何优劣。
（2）Python程序属于编译型程序，还是解释型程序？根据检索结果，你对即将学到的Python语言有何预期？
人们天天都在做计算。在计算机科学中，“计算”一词的概念更为宽泛，用计算机做的一切事情都可以称为计算。表达式是计算的基本概念之一。当儿童学习1+2=3时，就是在学习表达式的计算。1和2是运算数（operand），加号是运算符（operator），计算结果3被称为表达式的值。得到结果的过程称为表达式的求值过程。在正式开始动手编码之前，我们先来了解一些表达式的基本概念。
运算数可以是1或2.5这样的数，也可以是"abc"这样的字符串。这种直接就能表示某个值的标记被称为字面值（literal）。运算数也可以是某种标记所代表的对象，比如a、s这样的标识符（identifier）。在使用标识符之前，要将其和某个对象进行关联，比如赋值操作a=5, s="abc"。
狭义的运算符是指程序设计语言定义的一系列特殊符号，从四则数学运算，到各种语言常见的索引运算符[ ]，以及部分语言特有的lambda运算符等。广义运算符则包含进行各种操作的函数，如求最大值的函数max()，或者切分字符串的函数split()。运算符和运算数组成表达式，如1+2。
如果和运算符配合使用的运算数是两个，就称该运算符是二元（binary）运算符，其运算是二元运算。其他运算数个数的运算符也有类似称呼，如一元和三元等。
运算符和运算数组成表达式。运算符和运算数的出现次序会影响表达式乃至程序设计语言的风格。
1．前缀表达式
前缀，是指运算符的位置在前。前缀风格的一个例子是函数调用，如求最大值函数max(3,2,5)。函数max接收若干个运算数，计算其中最大者作为表达式的值。这种前缀函数调用形式称为面向过程的函数调用风格。
1+2也可以写为前缀形式(+ 1 2)。Python不使用这种形式，但著名的程序设计语言Lisp就使用这种形式。①1
2．中缀表达式
中缀，顾名思义是指运算符的位置在中间。1+2毫无疑问属于中缀表达式，但更值得注意的是面向对象风格的函数调用，如"hello Python world".split(" ")。这个表达式里的运算是split函数。这个函数接受2个参数：第1个是字符串"hello Python world"，第2个是空格字符串" "。计算的过程则是以空格为分隔符切割字符串，得到一个包含切割结果的列表["hello", "Python", "world"]。
面向过程和面向对象风格的函数调用在Python中都有广泛应用。本书从开始就普遍使用这两类风格的函数调用。本书将在第2章详细介绍函数的内容，在第4章详细介绍面向对象设计的内容。
3．后缀表达式
(1 2 +)是后缀表达式。后缀表达式和人们在进行竖式演算的书写次序一致（先写数字，再写运算符，然后计算结果），如图1.1所示。
图1.1 竖式运算
某些高级计算器支持以后缀次序输入算式，如HP48G。在程序设计语言的语法规则中，后缀序比较少见。本书在1.8.5节的示例中使用了后缀表达式。
复杂的表达式可以由简单表达式和运算符组合而成。12是表达式，它可以进一步和乘法运算符组合成123，或者和加法运算符组合成12+3。乘法运算的优先级较高。括号用来改变运算符的运算次序1(2+3)。表达式自左向右计算（这对减法和除法是至关重要的），这称为运算符的结合性。
这是小学生就明白的事情，但计算机科学家们感兴趣的是如何严谨地描述上述说明。在计算机科学中，往往使用如下范式来准确定义表达式（为了方便理解，这里只讨论由数字、加号、乘号和括号组成的四则运算表达式）。
初级表达式 是 数字 或 (四则表达式)①
乘除表达式 是 初级表达式 或
乘除表达式 * 初级表达式
乘除表达式 / 初级表达式
四则表达式 是 乘除表达式 或
乘除表达式 + 四则表达式
乘除表达式 - 四则表达式
如果读者之前从未接触过这种形式的定义，那着实要动一番脑筋才能理解。请读者仔细体会上述描述，该描述明确、完整地包含了关于四则运算表达式各个方面的说明。6
上述描述表达式的一般形式被称为巴克斯范式（Backus Normal Form），这是计算机科学中用来描述语法的基本模型。精确地将问题描述成某种模型，对解决问题意义重大。比如描述成巴克斯范式的语法解析问题，可以很容易地使用bison这类语法解析器来处理。②
在上述定义中充满了用事物自身定义自身的方法，这种方法称为递归。递归是一种非常重要的程序设计方法。本书将在2.4节对其进行详细介绍。
运算符的行为取决于运算数的类型。例如，字符串类型也可以做加法和乘法：
"123" + "456" 的值是 "123456"
"123" * 2 的值是 "123123"
这两种字符串运算分别是拼接和重复。同样的运算符有不同的行为，这称为运算符重载（overloading）。在编程实践中，程序员经常受益于这种便利。本书将在2.5.5节讲述如何针对自定义类型重载运算符。
在表达式的求值过程中，对状态的改变称为表达式的副作用。Python中内建的各种运算符（此处是狭义的含义，如加、减、乘、除、比较等运算符，并不包含用户自定义的运算符或函数）是没有副作用的，但各种函数调用时常带有副作用（比如各种输入、输出函数）。在使用带有副作用的表达式构建复杂表达式时要格外留意，因为这可能带来程序员容易忽视的行为。例如：
if expA and expB :
...
这条语句用来测试表达式A和B都为真的条件。expA and expB的计算具有短路性质，即如果A为假，则整个表达式已然能够判断为假，表达式B不会被求值。如果表达式B包含函数调用，则意味着该函数不一定被调用。
不过总体说来，Python中副作用带来的麻烦并不多。程序员只要不在复杂表达式中嵌套带有副作用的函数即可避免这些容易混淆的情形。这种编码风格也能很容易遵守。①7
为什么要在一开始讨论1+1=2这些简单的内容，而非动手写一些立刻就能运行的代码呢？原因在于，清晰的核心概念是持续学习的保证。看似纷繁的知识其实都有着清晰的图景，司空见惯的简单背后隐藏着本质的原理。在程序设计语言中，称得上核心的概念极为有限。学习的过程就是对这些核心概念的认识不断提高的过程。
表达式种类繁多，工程师要花费相当多的精力在处理和设计各种表达式上。清晰地理解表达式的本质特性，能让学习者迅速抓住语言特点，进而顺利地掌握用这门语言进行程序设计的方法。
让程序运行起来是动手实践的起点②。运行Python程序的基本方式有两种：交互执行模式和脚本执行模式。本节将展示这两种方式，以及其他初学者的入门技能。
【学习目标】
Python解释器提供了交互执行模式（interactive mode）。用户在提示符（通常为>>>）下依次输入代码，执行环境在每条语句输入完毕后会即刻执行并显示结果。正确安装Python后，在系统终端中输入Python解释器命令即可进入交互执行模式。
$ python3
Python 3.7.0 (v3.7.0:1bf9cc5093, ...)
......
>>>
Python 3相较Python 2在设计上有许多先进之处（笔者认为这些先进之处是Python进几年愈发流行的重要基础）。虽然工业界已经开始全面向Python 3迁移，但许多操作系统中（如Ubuntu18.04和Mac OS等）的Python默认安装仍为2.x版本。在终端中输入python命令启动的是旧版本的Python交互执行环境。Python 3.x版本需要用户自行安装。本书将始终使用Python 3命令来表明所用Python的版本。学习者有时会误用Python 2.x执行程序，那样会导致很多示例无法正常运行。请读者在上机练习时注意这一点。本书写作伊始，Python的最新稳定版本是3.7.0。根据不同的环境和Python版本，提示信息也有所不同。>>>是提示符，说明终端正在等待用户输入命令。
在交互式执行环境中输入表达式，解释器会计算表达式的值并显示出来。读者可以尝试输入以下表达式，并查看计算结果。
>>> 1+2
3
>>> max(1, 2)
2
>>> 'hello' + 'world'
'helloworld'
>>> [1, 2, 3]
[1, 2, 3]
>>> sum([1, 2, 3])
6
在交互式执行环境中还可以输入语句。解释器会执行语句，该语句执行后的输出内容将显示在终端上。print()语句是初学Python最常用到的语句，该语句默认向标准输出打印信息，如：
>>> print('Hello world!')
Hello world!
print()函数可以接收多个欲打印的对象并将其依次输出：
>>> print("123 / 3 = ", 123/3)
123 / 3 = 41
本书将在1.6节讲述常用的输入、输出方法。
在程序设计术语中，“语句”和“表达式”是不同的概念。在Python中单独成行的表达式是语句，如1+2。只不过没有副作用的表达式语句在程序中没有太大意义，既不创造输出，也不改写状态。我们往往用表达式来改变程序的状态（如进行输入、输出），或传递其计算结果（如将其用于赋值语句）。print是函数，故上述语句print("hello world")也是表达式。print()函数不会计算出某个值（无返回值），该函数的行为就是打印输出流。可以完整地将这一行代码称为“表达式语句”，但从强调行为的角度出发，往往简称其为“语句”而非“表达式”。
交互执行环境不仅能够执行单行语句，还能够执行函数定义、分支执行等复杂语句。下面的示例定义了名为hello的函数。
>>> def hello(n):
... for i in range(n):
... print('hello world')
... <- 此处的空行用于结束函数定义
>>> hello(3)
hello world
hello world
hello world
上述代码中的def和for代码行是用来定义函数和执行循环的语句（它们就不是表达式）。函数是为了某个任务封装起来以便反复调用或能清晰阅读的一组代码。函数调用语句是在函数名后紧跟一对圆括号，圆括号内放置参数。单独使用函数名表示引用函数本身。上述示例定义的hello()函数重复打印n次hello world字符串。读者不必深究函数的诸多细节，这里的例子仅在于让读者对交互执行界面有所了解，本书将在第2章中详细讲述函数。
读者在尝试本示例时，请严格按照示例中展示的空格进行输入：for语句前面需要4个空格，print()语句前则需要8个空格。空格缩进的含义将在1.3.6节讲述。
新手往往喜欢用搜索引擎寻求帮助，专家们则首选官方文档①。最便捷的文档是Python交互执行环境中的联机文档。在终端中单独输入print（注意不要在print之后跟括号），反馈结果显示这是一个内建（built-in）函数。用help()函数可以查看帮助文档，以获得关于print()函数的详细说明。
>>> print
<built-in function print>
>>> help(print)
Help on built-in function print in module builtins:
print(...)
print(value, ..., sep=' ', end='\n', file=sys.stdout, flush=False)
Prints the values to a stream, or to sys.stdout by default.
Optional keyword arguments:
......
如果读者首次接触程序设计，会发现print()函数的帮助比想象的更复杂。尽管如此，读者也应当从现在开始就查阅文档。尽早开始查阅文档而不是只依靠教科书，能够大大加快掌握这门语言的进程，即使暂时有很多无法理解之处也当如此。
【思考和扩展练习】
（1）理解print()函数的联机文档的内容。
（2）在www.python.org上找到print()函数的文档。①
交互式环境多用来验证小代码片段，但稍微长的程序就需要保存为文件来执行。这既能够避免每次重新输入程序，也能以模块形式组织代码以供其他程序调用。编辑代码1.1文件并保存为first.py，然后按照后文的“程序运行结果”指示运行程序。
代码1.1 first.py循环打印随机数，脚本执行示例
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
from random import random # 导入模块
for i in range(10): # 循环10次
print(i, ": ", random()) # 打印随机数【代码说明】②
如上述代码1.1中的第2行所示：
-- coding: utf-8 --
【程序运行结果】
执行Python脚本是很便捷的，在终端中执行Python解释器命令即可运行脚本。
再次提醒读者，要使用Python 3解释器运行程序。
$ python3 first.py
0 : 0.7215904032844517
1 : 0.4395568410901619
2 : 0.7659605406121555
3 : 0.9665488199747889
......
8 : 0.41147705008361746
9 : 0.17374989187394063
除上述方式外，还可以像执行普通程序那样去执行脚本。给脚本加上可执行权限后，就可以通过直接输入脚本路径来执行程序，例如：
$ chmod +x first.py ~ 加上可执行权限
$ ./first.py ~ 执行脚本
0 : 0.5876725130959004
1 : 0.5600259806151905
2 : 0.6888807975267824
......
除了基本的语法机制之外，Python语言通常还提供各种设计好的功能。这些功能有些以内建对象的方式提供，比如print()函数。有些以模块的形式提供，比如此处用到的random模块。内建函数可以直接使用，模块则必须导入后再使用。在代码1.1中的如下语句：
from random import random
从random模块中导入了random()函数。本书将在2.2节中详细讲述模块的各种细节。目前，读者只需了解在导入之后才能使用该模块中的函数random()（这个函数恰巧与模块同名）。该语句的第1个random是模块名，第2个random是函数名。
在计算机科学中，术语“标识符”（identifiers）是指用来命名程序实体（如函数、变量和对象）的单位②。Python 2中的标识符由字母、数字、下划线组成，且不以数字开头。这也是很多编程语言的习惯。前文所使用过的函数print()、自定义的函数hello()，以及模块名random都是标识符。从Python 3开始，Python的标识符增加了对非ASCII字符的支持。但从习惯上，命名时仍遵循以字母、数字和下划线组成的惯例。本书不使用包含非ASCII字符的标识符，有兴趣的读者可以参见PEP-3131。
关键字（keywords）是程序设计语言为了特定用途保留的名字。Python 3.7版本中的关键字如下：
在1.3.1节示例中使用过的def就是关键字。该关键字用于函数定义。读者目前无须去记忆或探究这些关键字的作用，随着学习的不断深入，自会逐渐接触。
注意：Python是仍在不断发展中的语言，async和await关键字在3.6版本中还没有出现，在3.7版本中才作为关键字。在笔者撰写本书的时候，就遇到了以前的代码由于采用async作为参数名而导致在新版本的Python中无法运行的情况。这是书籍编写者的麻烦，但却是Python生机勃勃的表现。
初学者一般会花费很多时间在修改语法错误或其他简单错误上。有经验的工程师在进入新的编程领域时也是如此。
初学者首先要能够平和地对待这一过程。在简单错误上消耗的时间因人而异，这是学习编程的必经阶段。从笔者的教学经验来看，也的确存在一些加速通过这个阶段的方法。最直接的方法就是主动触发错误进而去理解它。
理解错误提示信息含义很有价值，不但能够加快编码进度，还能了解编程环境的“思考方式”。有意识地输入一些错误代码，观察解释器给出的错误提示，是非常有用的学习技巧。对于英文水平薄弱的学习者而言，这显得尤为有用。例如，当名字引用发生错误时，解释器会给出如下提示：
>>> printf("Hello world!")
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
NameError: name 'printf' is not defined
>>> math.sqrt(2)
......
NameError: name 'math' is not defined 第1条语句故意将print错拼为printf（这是很多C程序员初学Python时会犯的小错误），第2条语句虽然没有拼写错误，但在使用函数前没有导入模块。总而言之，当解释器找不到语句中所用的名字时，就会提示如下错误：
NameError: name '....' is not defined
初学者经过上述刻意的“试错练习”后，就能够比较轻松地掌握该类错误提示信息的含义了。当初学者看到该类错误涉及函数调用时就会意识到：函数调用拼写是否有误、是否未导入模块、函数定义的函数名是否写错。
不论是学习新语言，还是学习新框架，都有一个熟悉错误提示信息的过程。逐个讲解错误提示信息没有太大的意义，因为这需要初学者自行练习、理解。这里的示例是向初学者介绍加快这个过程的方法。即便有经验的工程师，在新的软件开发环境中全面展开工作前，通过这种“故意出错”的方式熟悉一下错误提示信息的风格也是不无裨益的。
在开始全面讲解Python语言前，先来展示一个小程序。这样做的意图在于让读者领略这门语言的风格。
本节以欧几里得算法（这是人类历史上最早记载的算法）为示例，向读者展示注释、文档字符串（docstring）、变量、循环、递归、缩进，以及函数定义等Python语法要素。
欧几里得算法：在数学中，辗转相除法，又称欧几里得算法（Euclidean algorithm），是求最大公约数的算法。辗转相除法首次出现于欧几里得的《几何原本》（第VII卷，命题i和ii）中，而在中国则可以追溯至东汉出现的《九章算术》。两个整数的最大公约数是能够同时整除它们的最大正整数。辗转相除法基于的原理是：两个整数的最大公约数等于其中较小的数和两数之差的最大公约数。（以上内容来自***）[1]
在实际操作中，可以使用带余数除法替代减法以减少步骤。如图1.2所示为欧几里得算法流程图。
在程序设计实践中，很少针对简单的程序绘制流程图。因为对于熟练的程序设计者来说，代码本身足以清晰地说明程序的执行流程。流程图往往用于描述大型软件系统的工作原理，或者用来辅助不够结构化的语言（如汇编语言）。
根据前述算法描述，计算252和105的最大公约数的计算步骤如下：
（1）252除以105，余数为42，问题转为求105和42的最大公约数。
（2）105除以42，余数为21，问题转为求42和21的最大公约数。
（3）42除以21，可以除尽，达到算法终点。
（4）结论：252和105的最大公约数为21。
图1.2 欧几里得算法流程图
代码1.2将展示欧几里得算法的Python实现。
代码1.2 gcd.py求最大公约数
#!/usr/bin/env python3
def gcd(a, b):
while b!=0:
a, b = b, a%b
return a
print(gcd(252, 105))
代码1.2的核心部分定义了用来求最大公约数的函数gcd()。为了便于说明，将这一部分进行详细说明，如图1.3所示。
【代码说明】
图1.3 gcd()函数图示
【程序运行结果】
$ ./gcd.py
21 可以使用Python 3解释器的-i 命令行选项，在启动解释器交互界面时加载执行程序文本。加载执行程序文本后，可以继续输入代码以执行：
$ python3 -i gcd.py
21
>>> gcd(12, 4)
4
>>> gcd(36, 54)
18 学习编程语言需要动手实践，所以第一步就是搭建能够运行程序的环境。从操作系统环境和版本的选择上，笔者建议的***选择是采用某个Linux的最新稳定发行版及配套的Python 3运行环境。
和有些语言（如C语言）持续多年的稳定性不同，Python仍然在快速进化中，在开始学习时就养成时刻查阅文档的习惯是必要的。
内建类型是语言自身定义的系列类型，往往包括数值、字符串和容器等。这是程序运行的基本要素之一。本节将向读者介绍Python内建类型中最基本的部分：数值、字符串和容器。在本节的最后还将介绍Python的赋值操作、引用和del操作的行为。
【学习目标】
程序设计是工程而不是数学。这意味着无法像讲授数学课那样，先引出一些基本公理，然后层层推导出整个知识体系。在程序设计中，往往最基本的概念也会涉及语言的方方面面，比如本节将要介绍的基本类型。如果一开始就全面地讲解Python的各种基本类型及其操作，不但在篇幅上不允许，而且初学者也不具备相关的背景知识。但如果不引入这些概念，便会寸步难行，因为即便是最简单的代码，也要用到基本类型和表达式。
这个矛盾将贯穿读者学习和实践程序设计的始终。本书的观点是：既然无法讲述全部细节，就将精力集中在必须要了解的内容上。
“字面值”（literals）是一个计算机科学术语，用来表示某个固定值的记号。
1．算术字面值
算术字面值（Arithmetic literals）用来表示“数”。下面的例子给出了由Python支持的部分算术字面值组成的表达式。请读者在Python的交互执行环境中输入这些表达式。交互执行环境在计算之后会直接显示表达式的值。如果用脚本执行，则需要使用print()函数打印表达式的值。
2000+ 6 * 3 # 整数和运算符组成的表达式
2018 // 50 # 取商的除法，也叫整除
2018 % 50 # 取余数
2018 * 3.14 # 3.14是浮点字面值
2018 / 50 # 浮点数除法
2018 ** 2 # 乘方运算
(20 + 18j) * 2 # Python支持虚数运算 上述表达式中出现的2018、2000等数字被称为整数字面值。除整数外，Python还支持浮点数（如3.14）和虚数（如18j）作为字面值①。
2．字符串字面值
字符串字面值（String literals）用以描述字符串类型的值，多用于生成文本或命令。Python的字符串字面值以单引号或双引号引起来②。某些在算术运算中使用的运算符也可用于字符串，当然其行为有所不同。例如加法和乘法：
>>> 'hello ' + 'world' # 用于拼接字符串
'hello world'
>>> "hello " * 4 # 用于重复字符串
'hello hello hello hello '
同一运算符针对不同类型对象的不同行为，被称为运算符重载（overloading）③。作为序列类型，字符串还可使用索引和切片运算④以取出某个字符或部分字符串。
>>> 'hello'[1] # 索引计数从0开始
'e'
>>> 'hello'[1:3] # [:]是切片
'el' 在内建运算符之外，字符串类型还用成员方法的形式定义了若干操作。
isupper() # 判断字符串是否为大写字符串
split() # 切割字符串得到包含子串的列表
upper() # 得到对应的大写字符串
具体用法如下：
>>> 'hello world'.isupper()
False
>>> 'hello world'.split()
['hello', 'world']
>>> 'hello world'.upper()
'HELLO WORLD'
读者应当已经注意到，这些函数的调用方法不同于前述print()函数。此处操作使用“对象.函数名()”的形式。这被称为面向对象风格的函数调用。点号（.）运算符之后的函数被称为成员方法，它往往是依据点号之前的对象实施某种操作。Python中相当多的内建功能都以此种形式提供，本书自然也将广泛地使用这种语法形式。第4章将详细介绍这种程序设计风格的便利之处，并详述具体方法。
内建函数len()可以用于求字符串的长度①，如下：
>>> len('hello world') # 得到字符串长度
11
用dir(str)查看字符串类型支持的全部成员方法：
>>> dir(str)
['__add__', ... , '__len__', ... , 'isupper',
'replace', ... , 'split', ... , 'upper', ...]
请读者在交互执行环境中测试这些字符串运算，并通过dir()函数查看字符串类型的各种成员方法。
读者会在dir()的输出中看到许多函数。除非是有经验的Python使用者，否则很难在短时间内全部理解这些函数的作用。但即便如此，也应当始终坚持这种积极查阅官方文档的方法。通过阅读官方文档而不是道听途说，更能准确地掌握相关知识。
【思考和扩展练习】
（1）根据dir(str)的输出，探索字符串类型支持的全部操作。
（2）查看官方文档，学习Python的字节串字面值（Bytes literals）。
（3）辨析字符串字面值、字符串类型与字符串对象。
内建类型的构造方法用来得到这些类型的对象。整数类型int，浮点数类型float，复数类型complex，以及字符串类型str都有构造方法。
int(12.34) #得到整数12
int('125') #得到整数125
float('12.34') #得到浮点数12.34
complex(1,2) #得到复数(1+2j)
str(125) #得到字符串'125'
构造方法是一种特殊的函数，本书将在2.5.3节介绍如何为自定义类型创建构造方法，目前读者只需了解如何使用它。为了获取整数进行操作，程序要经常使用整数类型的构造方法将字符串类型转换为整型。例如示例代码1.3，通过命令行参数接收任意多个参数求和。这些参数以字符串形式获得，而后被转换为整型。
代码1.3 sum.py对命令行参数求和
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
from sys import argv
sum = 0
for arg in argv[1:] :
sum += int(arg) # int() 将字符串转换为整数
print(sum)【代码说明】①
int(arg)利用整数类型构造方法通过字符串得到整数。
【程序运行结果】
$ ./sum.py 1 2 3
6
$ ./sum.py 1 4 7 10
22
术语“容器”是指用来存储对象的某种结构。程序员可以使用容器，方便地进行对象的存储和查找等操作。不同的容器类型适用于不同的操作场景。Python内建了列表（Lists）、元组（Tuples）、字典（Dictionaries）和集合（Sets）等容器类型②。
1．列表（Lists）
列表是包含零个或多个对象引用③的序列。定义列表的基本语法是在方括号中以逗号分隔其各元素。以下代码定义列表并将其关联至名字a：
a = [1, 2, 3, 4, 5, 6]
同字符串一样，列表也是序列类型，同样能用索引和切片来访问，并使用len()函数得到其长度，例如：
列表还有不同于字符串的操作，如append()/pop()方法可以添加/取出列表尾部的元素。
列表可以被修改。
列表元素可以引用不同类型的对象。以下列表中含有4个不同类型的元素：整数10、字符串"hello"、函数max()，以及列表[1,2,3]。
a = [10, "hello", max, [1, 2, 3]]
注意：Python的列表元素可以具有不同的数据类型，这一点有别于C语言的数组。其实根本原因是Python的列表存储引用，而Python的引用可以指向各种类型的对象。
列表支持许多操作，可以通过dir()命令来查看列表类型的成员方法，例如：
>>> dir(list)
['__add__', ... , '__contains__', ... , '__len__', ... ,
'__mul__', ... , 'append', ... , 'pop', ...]
观察这些成员方法可以发现，列表与字符串有很多相同的成员方法，比如__add__()，__mul__()及__len__()等。思维敏捷的读者已经可以推测到适用于字符串的加法、乘法运算符和len()函数同样能够用于列表。这个推测可以很容易地被验证：
>>> [1, 2] + [3, 4]
[1, 2, 3, 4]
>>> [1, 2, 3, 4] * 2
[1, 2, 3, 4, 1, 2, 3, 4]
>>> len([1, 2, 3, 4])
4 推测是比记忆和查阅文档更重要的能力。根据所见事实及自身经验做出推断然后验证之，这是学习新知识和探索未知知识的重要方法。能“推测中”的越多，需要学习的就越少。
【思考和扩展练习】
（1）查看参考文献[2]列举的Python运算符，再根据列表的成员方法中有__contains__()的事实，推测列表可以进行哪些操作。
（2）根据dir(list)和dir(str)的结果，推测列表和字符串还能支持哪些操作。
（3）思考len()这样的函数是如何工作的，为什么它对字符串和列表都能正常工作？
（4）为什么列表和字符串都能够进行索引运算？如何让新类型支持索引操作？
2．元组（Tuples）
与列表类似，元组也是对象序列，不同之处在于元组不可修改。元组的定义和表示使用圆括号：
t = (1, 2, 3) 在不引起歧义的情况下，圆括号可以省略：
t = 4, 5, 6 元组同样也支持混合类型、嵌套、切片及各种运算符，此处不多赘述，请读者自行练习。
【思考和扩展练习】
（1）探究元组支持的操作，并动手实践之。
（2）Python为什么要在列表之外提供元组类型。
3．集合（Sets）
集合类型无序地存储非重复的数据①。定义集合使用花括号语法，而且会自动去掉重复的元素。
>>> s = {'fox', 'cat', 'panda', 'cat'}
>>> s
{'cat', 'fox', 'panda'} # 重复的元素被去掉
既然无序，自然不支持索引和切片。
>>> s[0]
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
TypeError: 'set' object does not support indexing
集合类型支持数学意义上的集合运算，如图1.4所示。
操作示例如下：
>>> a = set('1234')
>>> a
{'1', '2', '4', '3'}
>>> b = set('3456')
>>> b
{'6', '4', '3', '5'}
>>> a - b
{'1', '2'}
>>> a | b
{'1', '4', '5', '6', '2', '3'}
>>> a & b
{'4', '3'}
>>> a ^ b
{'1', '5', '6', '2'}图1.4 集合运算
注意：这里使用了集合的构造方法set()从字符串构造出相应的字符集合。本书不再赘述各种容器类型的构造方法，对其的探寻作为习题留给读者。
【思考和扩展练习】
（1）在交互执行环境中用dir(set)命令查看集合支持的方法，并动手实践之。
（2）举出无序数据集的应用场景例子。
4．字典（Dictionaries）
字典是Python提供的一种用途广泛的存储结构。字典将存储的对象和键值（key）进行关联。字典使用“键”访问元素，而不是像序列类型（列表、元组）那样使用索引访问。任何不可修改类型①都可以作为键值。字典的定义使用花括号语法。以下示例展示了字典的创建、查询、添加和删除操作。
>>> price = {'iphone-x':8999, 'airpods':1300, 'keyboard':500}
>>> price['airpods']
1300
>>> price.update(mouse=400) # 使用update添加元素
>>> price.pop('airpods') # 取出并删除元素
>>> price.pop('keyboard')
1300
>>> price.update({'cover':100, 'bag':300})
>>> price
{'iphone-x': 8999, 'mouse': 400, 'cover': 100, 'bag': 300} 【思考和扩展练习】
（1）把数据组织成“键-值对”有何好处？
（2）列举出使用“键-值对”表示数据的场景。
5．小结
在程序中使用容器，即便仅用列表，也能让程序实现各种复杂的功能。这是本书在讲述流程控制结构前介绍容器类型的意图所在。但相较流程控制和函数等结构来说，容器操作方法的细节却又并非程序设计的本质所在，而其深层原理又属于稍有难度的提高内容。故本书只是在此对容器的简单应用稍作讲解后便迅速带领读者进入程序设计的基础核心模型：流程控制结构（1.5节）和程序执行模型（1.8节）。容器的操作细节和深层原理则推后到第3章讲述。到那时读者已具备阅读文档之基本能力，以及一定的程序分析和设计能力，当收事半功倍之效。
截至目前，本书介绍过3种序列类型：list、tuple和str。在1.5节流程控制中将介绍range类型。Python为序列类型（sequence types）①提供了独特的索引（indexing）和切片（slicing）机制，以访问序列的某个元素或某一部分。16
1．索引
在前文中已经展示过使用索引访问字符串、列表和元组的方法。像大多数其他编程语言一样，Python的索引从0开始（长度为N的序列，索引序号从0到N-1。除此之外，Python通过引入负数索引的方法，使得从尾部开始访问序列的写法很简洁。最后一个元素的索引为-1，倒数第二个索引为-2，以此类推，直至第一个元素的索引为-n。访问序列的结尾元素只需要x[-1]即可，无须使用复杂的表达式，如x[len(x)-1]。索引如图1.5所示。
图1.5 索引
2．切片
切片运算从序列类型对象中选取一系列元素，得到新的对象。下面以列表为例演示如图1.6所示的切片操作。
>>> a = [1, 3, 5, 7, 9, 11, 13, 15]
>>> a[3:7] # [起始元素:结束元素+1]
[7, 9, 11, 13]
>>> a[:7] # 省略起始索引，从头开始算起
[1, 3, 5, 7, 9, 11, 13]
>>> a[3:] # 省略结尾索引，算至末尾
[7, 9, 11, 13, 15]
>>> a[:]
[1, 3, 5, 7, 9, 11, 13, 15]
图1.6 列表切片
下面在切片运算中增加第3个参数就可以按间隔挑选元素，如图1.7所示。
图1.7 间隔切片
>>> a = [1, 3, 5, 7, 9, 11, 13, 15]
>>> a[1:7:2]
[3, 7, 11] 当步长为负时，可以实现“从后至前”的切片，例如：
>>> a[::-1] # 从尾至头，步长为-1
[15, 13, 11, 9, 7, 5, 3, 1]
切片同样适用于其他序列类型，例如：
>>> t = (1, 3, 5, 7, 9, 11, 13, 15)
>>> t[2:7:2] # 元组
(5, 9, 13)
>>> s = 'abcdefgh'
>>> s[::3] # 字符串
'adg'除去列表、元组、字符串外，Python还有用于生成等差数列的range类型，常用其控制for循环，将在1.5.4节讲述。
初学者可以选择性跳过本节的内容。①17
仅凭字面值（如100）或由字面值组成的表达式（如100+200）无法得到有价值的程序。机器之魅力在于状态的运转和变化。在前文的欧几里得算法程序中，a、b这一对“变量”不断地被赋予新的计算结果直至计算终点的过程就是例子，凡是程序大都如此。这就需要为状态或数据开辟存储空间，并进行赋值以设定某种访问标记。②
术语“左值”（lvalue），表示用来标记对象存储位置的语言要素（location value）。
表达式100+200的计算结果为300，但无处安放。仅由这样的孤立表达式构成语句，计算结果会被丢弃。而包含了赋值操作的语句a = 100+200则不同，等号右边的计算结果300将被存储于某一内存地址后关联等号左边的名字a，后者则代表了该存储位置。在此场景中，a是左值，而100+200不是。
在另一语句L[0] = a中，程序员实际上关心a代表的值（即300）而非存储位置，关心L[0]的位置而非值。这行代码的意图是L[0]所存储的引用修改为指向300，而不关心其本来指向哪里。故而在此场景中L[0]是左值，a不是。上述诸场景中，等号右边的计算结果被称为“表达式的值”，有时也被称为“右值”。
a, L[0]既可以作为表达式，也可以作为左值。200、200+300和a+200则只能作为表达式。
左值最容易被注意的特性是“出现在赋值运算符左边”，所以得中文名“左值”。但事实上应用左值的上下文不仅仅是赋值。读者在1.4.6节将看到对左值的del操作，在1.5.4节将看到左值列表用作for的循环变量。
1．左值的引用特性
在Python中左值是“引用”（reference），而非对象本身。“引用”是用来找到对象的标签，在Python的典型实现CPython中以对象的内存地址作为引用。在64位计算机系统上地址占8个字节，所以如下的赋值操作③创建了如图1.8所示的内存图景。④
>>> a = 10
>>> id(a) # id 用来查看 a 指向的地址
4476271904
>>> s = 'Hello world'
>>> id(s)
4479238256图1.8 赋值语句
虽然严谨的术语将这种性质的左值（名词）或指向行为（动词）称为“引用”，但习惯上还有以下提法（以名字a为例）：
对名字重新赋值会使名字引用新的对象。以整型变量为例，重新赋值意味着另辟空间构建新对象，再让a指向该地址①，如图1.9所示。
在交互执行环境中验证如下：
>>> a = 10
>>> id(a)
4476271904 ~ 原有地址
>>> a = 20
>>> id(a)
4476272224 ~ 另辟地址图1.9 重新赋值
在Python中做字符串操作时也有同样的行为。特别地，字符串是“不可变对象”（immutable）时，连接操作并非在原地接续，而是另辟空间①，如图1.10所示。20
图1.10 字符串操作
执行a=b时，会导致a与b指向同样的对象②，如图1.11所示。
图1.11 赋值操作a=b
当操作可变类型时要尤为注意。以如下列表对象的赋值操作为例：
>>> b = [10, 20, 30]
>>> a = b
在第2条赋值语句之后a和b指向相同的列表，如图1.12所示。
图1.12 列表的赋值操作
验证如下：
>>> b = [10, 20, 30]
>>> a = b
>>> a[1] = 9
>>> b
[10, 9, 30]
通过a对列表进行修改，再通过b对列表进行访问，可以很清晰地看到b指向和a相同的列表。Python提供了is运算符，判断两个名字是否引用相同的对象。
>>> b = [10, 20, 30]
>>> a = b
>>> a is b
True
>>> b = [10, 20, 30] ~ 另辟列表
>>> a is b
False 2．引用的无类型特性
Python的引用没有类型。这意味着某个名字可以指向任何类型的对象，如图1.13所示。习惯上，当提到“a的类型”时，实际意思是“a所指向的对象类型”。而“T类型变量a的值”的确切含义是“指向T类型对象的名字a所指向的对象的值”。除非特别强调，本书也将采用习惯上的简单说法。
在图1.13中，函数名和变量名都是引用。赋值操作让这些名字指向其他类型的对象①：21
3．None关键字
Python提供了None关键字用以设立“空引用”。执行a = None后，a就不再指向任何“具体的”对象②了。在程序设计语言中，“空引用”一般有如下3种用途：22
图1.13 将名字关联至不同类型
【思考和扩展练习】
（1）既然赋值只是修改引用，如何得到列表a的副本b？
（2）当复制列表时，列表引用的对象也需要复制吗？①23
（3）使用is和使用==判断等价性有何不同？
（4）对于两个指向None的引用a和b，a is b和a==b有何不同？
（5）测试以下两段代码的结果，并解释结果。
a = 10
b = 10
print(a is b)
a = 100000
b = 100000
print(a is b) Python提供了del操作用以删除引用。del操作删除的是表示引用的标记，而非引用的对象①，如图1.14所示。
图1.14 del操作
下面的例子将验证del操作删除的是引用而非其指向的对象这个事实。
>>> a = [1,2,3] # 创建列表，绑定至a
>>> b = a # 将b绑定至同样的列表
>>> del a # 删除a
>>> b # 仍然可以通过b访问列表
[1, 2, 3]
如何删除对象，而非仅仅删除引用呢？Python并没有明确地提供删除对象的方法。Python的运行环境为每个对象维护一个引用计数，用以记录指向该对象的引用数。当指向某个对象的引用计数为0后，对象回收机制就会在某个时刻启动。② ③ ④24
最后，用索引或切片标记的列表元素可以通过del操作删除。
>>> a = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
>>> del a[1:3]
>>> a
[0, 3, 4, 5, 6, 7, 8, 9] 现代语言的内建类型非常丰富。本节介绍了Python的数值和字符串类型，以及列表、元组、集合和字典4种容器类型。Python设计者在内建类型上构造的操作能够反映这门语言的核心编程手段和设计思路。对于初学程序设计的读者来说，了解这些知识对于后面的学习是必要的。对于有经验的学习者来说，将这些特性与自己熟悉的其他语言进行比对思考是很有价值的。
本节还重点讲述了Python的引用及相关特性。Python中的对象都是通过引用访问的。引用没有类型，可以指向各种对象。赋值操作就是让引用指向新的对象，而del操作则是对引用的删除。
通过本节的学习，读者应当初步了解在Python中，“数据”是如何存储和表示的。这是接下来用各种流程控制手段对数据进行操作、写出复杂程序的基础。
在解决实际问题时，需要根据情况做出判断，执行不同的指令或循环执行某个指令序列。程序设计语言通过流程控制指令实现该功能。本节将介绍Python的逻辑表达式、分支控制语句if、while和for。在本节的最后将向读者讲述创建简单函数的方法。
【学习目标】
1．基本语法
if分支语句的作用是控制程序在不同的情况下执行不同的代码，基本语法如图1.15所示。
首先计算if关键字之后的表达式，如果值为真，就执行其后的语句块，否则执行else关键字后的语句块。执行流程如图1.16所示。
图1.15 if-else语法
图1.16 if-else流程图
2．完整语法
完整的if分支语句如图1.17所示。
图1.17所示语句的流程是：依次测试表达式，执行第一个求值结果为真的分支语句块。如果表达式均不成立，则执行else分支的语句块。在一条if-else语句中，if分支有且只能有一个，elif分支有零个或多个，else分支有零个或一个。执行流程如图1.18所示。
图1.17 完整的if-else语法
图1.18 if-elif-else执行流程
示例代码1.4从终端读入成绩，根据不同的分数打印成绩级别。
代码1.4 score.py打印成绩级别
#!/usr/bin/env python3
score = int(input()) # 从终端读入整数
assert 0 <= score <= 100, 'invalid input'
if score >= 90:
print('Grade A') # 90 - 100
elif score >= 70:
print('Grade B') # 70 - 89
elif score >= 60:
print('Grade C') # 60 - 69
else:
print('Grade D') # 0 - 60【代码说明】
【程序运行结果】
$ ./score.py
98 ~ 键盘输入
Grade A ~ 程序输出 分支控制语句的执行依赖于if-elif关键字后的表达式求值结果。下一节（1.5.2节）将介绍表达式的“真假”判断，以及如何通过逻辑运算将其组成更复杂的表达式。
【思考和扩展练习】
几乎所有语言都有if-else结构，但略有不同。查询你听说过的其他编程语言①，找到其中的if-else结构和Python的结构进行对比。25
布尔运算是对“真”“假”二值逻辑的运算。Python中有专门的布尔类型（bool），其值为True或False。布尔类型可以通过布尔运算组成更复杂的逻辑表达式。首先要关心的是表达式的值为“真”的情形：
注意：is运算符用来比较两个名字是否指向同一个对象（在CPython实现中即为比较对象的内存地址），而==运算符是用来比较两个对象的值是否相等。
以下是一些示例。
布尔类型表达式：
123 > 50
123 in [1, 12, 123]
a is b
非布尔类型表达式：
a 如果 a 不为 None，则判断为 True
123 非 0 值判断为 True
None 空对象判断为 False
习惯上用{0,1}来表示真、假，0意味着逻辑假，1意味着逻辑真。有4种基本布尔运算：“非”“与”“或”“异或”。非运算又可与后3种运算组成“与非”“或非”“异或非”运算。布尔运算如图1.19所示。
Python提供了3种布尔运算符：非运算（not）、与运算（and）和或运算（or）。用布尔运算可以组合成复杂的逻辑表达式，例如：
图1.19 布尔运算
需要注意的是，布尔运算有“短路性质”。即，如果计算到某个表达式就可以得出结论，那么后续的表达式就不会计算。比如上述例子，如果x<10为真，由或运算的性质就能够断定整个表达式为真。在表达式有副作用的情况下要尤其注意，因为处于布尔运算后面的表达式不一定被求值。这是需要避免的程序设计风格。
【思考和扩展练习】
（1）为什么多数程序设计语言在逻辑运算中不提供异或运算？
（2）自学位运算和位运算符。
1．基本语法
while循环用以反复地执行某段代码，直至某种条件不成立①。while循环的基本语法如图1.20所示。26
图1.20 while语法
while语句首先测试表达式的值，如果值为真，则执行其后的语句块。执行后继续测试表达式，如果值为真，则再次执行其后的语句块，如此周而复始，直至表达式为假。其流程如图1.21所示。
图1.21 while 流程图
以下代码展示Python中的无限循环：
while True:
____print("hello") 第1行的表达式为布尔值True，这是Python的关键字。对True的测试当然为真。由于循环内没有其他跳出循环的指令，该循环会一直循环下去。第2行print语句以4个空格缩进，是while的循环体语句块。在交互式执行界面输入该代码，会得到无限循环打印的'hello'字符串①。27
在绝大多数情况下，循环总要终止②。在循环过程中，程序要改变某些状态或接收外部输入，以获得循环的终止条件。在1.3.6节我们已经见过用while循环实现的欧几里得算法。接下来的例子将向读者展示while循环的另一个具体应用。
2．斐波那契数列示例
斐波那契数列（Fibonacci sequence），是法国数学家列昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入的数列：
1, 1, 2, 3, 5, 8, 13, 21, 34, ……
该数列从第3项开始，每一项都等于前两项之和。如图1.22所示为用斐波那契数列生成鹦鹉螺的螺旋线。
图1.22 用斐波那契数列生成鹦鹉螺的螺旋线
代码1.5打印斐波那契数列值在50以内的前若干项。
代码1.5 fib.py 打印斐波那契数列
#!/usr/bin/env python3
a, b = 1, 1
while a < 50:
print(a, end=' ')
a, b = b, a+b
【代码说明】
如图1.23所示形象地说明了代码的执行过程。
初学者在阅读代码时如果感到吃力，可以在纸上写出类似的过程以便于理解。经过一段时间的操练后，头脑中会慢慢建立起直观的图景，那时就可以直接想象代码的执行过程了。
【程序运行结果】①
$ ./fib.py
1 1 2 3 5 8 13 21 34 55 89 $
本书将在后文的讲解中反复使用到计算斐波那契数列问题。
图1.23 斐波那契数列递推计算过程
3．完整语法
在Python中，可以通过else关键字为while循环指定一个“结束动作”，如图1.24所示。
图1.24 完整的while语法
在测试表达式的值为假时，while循环终止，执行else后面的结束语句块，流程如图1.25所示。
可以将上述打印斐波那契数列的代码1.5修改如代码1.6所示。
代码1.6 打印斐波那契数列，结尾换行
#!/usr/bin/env python3
a, b = 1, 1
while a < 50:
print(a, end=' ')
a, b = b, a+b
else:
print()
【程序运行结果】
$ ./fib.py
1 1 2 3 5 8 13 21 34
$
执行程序后，可以看到在while循环结束后，程序友好地输出换行。
图1.25 完整的while语句流程图
4．break和continue语句
和其他很多语言一样，Python的循环中也提供了break和continue指令。break用于结束整个循环，continue用于结束本次循环。从执行流程上说，前者用于跳出循环，后者用于跳回到循环起始。以break退出循环时，不执行else后的语句块。流程图1.26所示为while语句中break和continue的执行流程。
示例代码1.7将展示break和continue语句的用法。程序从控制台读入10行文本，统计每一行的单词总数，在输入完毕后打印单词总数。在执行过程中，如果用户输入空行，则跳过继续要求输入，如果用户输入quit，则直接跳出程序。
代码1.7 words.py统计输入的单词数目，break和continue
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
from sys import stdin
cnt = 0
total_words = 0
while cnt < 10:
line = stdin.readline().strip() # strip去掉行位的换行符
if line == '' :
continue # 是空行则跳过
elif line == 'quit' :
break # 是quit则退出
else :
words = len(line.split())
print('words', words)
total_words += words # 统计总词数
cnt += 1 # 循环计数
else:
print('-'*10)
print('total words: ', total_words)图1.26 while循环中continue和break语句流程图
【代码说明】
$ ./words.py
hello world ~ 用户输入
words 2
I love Python ~ 用户输入
words 3
quit ~ 用户输入
$ 1．基本语法
for循环用来对可迭代对象进行遍历操作，基本语法如图1.27所示。
图1.27 for循环的基本语法
紧跟for关键字之后的是一个左值列表，in关键字之后表达式的求值结果应当是可迭代对象①。for循环每次取出可迭代对象的一个值，将其赋值给in关键字前面的左值，然后执行循环体语句块。
【示例1】 用for遍历列表容器。
用for循环遍历容器是非常方便的。以下示例显示了如何使用for循环遍历列表。由于代码简单，直接在交互式执行环境进行演示如下：
>>> fruits = ['apple', 'banana', 'grape']
>>> for item in fruits:
... print('I have a ' + item + 's.')
I have apples.
I have bananas.
I have grapes.
在上述示例中，for循环体执行了3次，在循环执行的过程中，变量item取遍列表fruits中的3个值。对元组、字符串、集合遍历方法和列表类似，请读者自行实验。
【示例2】 用for遍历字典。
字典存储的“键值对”稍微复杂，因此遍历形式也多一些。可以使用keys方法取出字典的键进行遍历，或者用values()方法取出字典的值进行遍历。示例如下：
>>> price = {
... 'apple':3.12,
... 'banana':4.23,
... 'grape':5.11
... }
>>> for key in price.keys():
... print('I have ' + key + 's.')
I have apples.
I have bananas.
I have grapes.
如果希望在遍历的时候同时使用键和值，可以用items()方法取出字典的键和值，赋值给一组循环变量。例如：
>>> for key,value in price.items():
... print('key' + '\t: ' + value + '/kg')
apple : 3.12/kg
banana : 4.23/kg
grape : 5.11/kg
【示例3】 在循环中计数。
有时候希望在循环中计数，Python中提供了enumerate类型用来从可迭代类型构造出枚举类型。enumerate配合循环的用法如下：
>>> fruits = ['apple', 'banana', 'grape']
>>> for i,item in enumerate(fruits):
... print(i, item)
1 apple
2 banana
3 grape
【示例4】 用range对象进行循环。
如果希望for循环能够进行固定次数循环，就要使用range对象。range对象“代表了”等差数列，但并不存储这些值①。可以使用list构造方法构造出列表如下：30
>>> list(range(5)) ~ 起点为0的整数数列
[0, 1, 2, 3, 4]
>>> list(range(5,10)) ~ 公差为1的等差数列
[5, 6, 7, 8, 9]
>>> list(range(1,10,2)) ~ 公差为2的等差数列
[1, 3, 5, 7, 9]
或者直接用for循环遍历数列。以下示例展示了固定5次的循环。其中，循环变量i在循环中取遍0，1，2，3，4。
>>> for i in range(5):
... print('+ ' * (i+1) )
+
+ +
+ + +
+ + + +
+ + + + + 2．完整语法
for循环也支持else语句块，完整语法如图1.28所示。
图1.28 for循环的完整语法
当循环正常结束时，执行else之后的语句块。在for循环里也可以使用break和continue，行为和while中类似。以break结束循环时，else语句块不会执行。其流程如图1.29所示。
图1.29 for循环的完整语法流程
【思考和扩展练习】
（1）查阅文档，找到可迭代对象的说明。
（2）查阅其他语言的for循环语法，比较与Python的异同。
条件表达式也使用if-else关键字，所以在这里一并介绍。条件表达式语法如下：
x if C else y
当条件C为真时，表达式的值为x，否则为y。恰当地使用条件表达式，可以让代码很简洁。如果需要根据不同的条件，计算不同的值，就可以考虑使用条件表达式。
?注意：条件表达式可以用在适用表达式的地方，如if-while的条件，或者给某个左值赋值。前一节所述的if语句不是表达式，不能用于类似上下文的地方。
到目前为止，本书示例已经调用过很多内建函数，如len()和help()等。通过调用函数并传递不同的参数，程序员可以反复使用某种功能。将需要反复使用的代码设计为函数，是令人愉快的事情。本节将介绍创建简单函数的方法。
本书将在2章完整讲述函数的各种知识。之所以先简单介绍编写简单函数的方法，是因为只须稍微具备相关知识就能大大扩展编程技能。如果按部就班等到第2章之后再编写函数，则无疑会失去很多学习乐趣和教学时机。
定义函数的语法如图1.30所示。def关键字用来定义函数。在函数语句块中可以包含所有我们学过的赋值、分支控制和表达式计算等语句。在函数中可以使用return语句返回值，当return语句执行时，函数执行完毕，程序跳转回调用函数的代码处继续执行。示例代码1.8将前述（1.5.3节）计算斐波那契数列的代码改写成函数。
图1.30 函数定义语法
注意：在程序能够调用函数前，函数定义语句必须已经被执行过。也就是说，函数定义需要放置在函数调用之前（或者通过导入模块的方式加载执行）。
代码1.8 fib.py函数定义和调用的完整例子
#!/usr/bin/env python3
def fib(n):
a, b = 1, 1
result = []
while a < n:
result.append(a)
a, b = b, a+b
return result
print(fib(10))
print(fib(30))
【程序运行结果】
$ ./fib.py
[1, 1, 1, 2, 3, 5, 8]
[1, 1, 1, 2, 3, 5, 8, 13, 21] 本节重点讲述了Python的3种分支控制结构：if-else分支、while循环和for循环。其中，前两个比较简单，直接用表达式的求值结果作为程序执行流程的控制条件；for循环则是比较高级的抽象，用以遍历可迭代对象，如range对象及列表等各种容器。
本节还简单讲述了函数的定义语法。函数是程序设计的重要手段，将重复的代码封装为函数，可以让程序变得简洁、清晰。
分支控制和函数是随时随地要用到的程序设计方法，本书将在1.7节通过一组示例，让读者进一步熟悉这些方法。
程序需要从外部获得信息并将计算结果传递出去。本节将介绍最常用的3种与程序传递信息的方式：标准I/O、命令行参数和环境变量。
【学习目标】
原始的输入输出是键盘、磁盘、终端等设备，“流”是对这些输入输出设备的抽象。
本书已经反复使用print()函数在终端输出信息，本节将会讨论向各种各样的“目的地”进行输出的方法。print()函数的默认行为是向标准输出流进行写入操作。在使用终端启动程序的默认情况下（就像本书一直以来做的一样），标准输出流被关联至终端。如果程序希望从终端读取数据，最简单的方法是使用input()函数。该函数从标准输入流读取数据，在终端启动程序时，标准输入流也被关联至终端。I/O流的默认配置，如图1.31所示。
图1.31 I/O流的默认配置
代码1.9从标准输入流读取一个字符串，使用eval()函数进行表达式计算。再将表达式本身连同等号和计算结果输出至标准输出流。
代码1.9 stdio.py读写标准输入/输出流
#!/usr/bin/env python3
e = input()
print(e, '=', eval(e))
代码执行示例：
$ ./stdio.py
1+2+3 ~ 输入
1+2+3 = 6 ~ 输出
在讨论更多的输入/输出函数之前，先介绍UNIX系统提供的一个重要机制：I/O重定向。
程序优先采用标准输入/输出流进行通信的一个重要动机是可以很容易地对其进行重定向。通过重定向标准输入流，可以在不修改可执行文件的情况下，让程序从文本文件中获取输入表达式。重定向标准输入流，如何1.32所示。
图1.32 重定向标准输入流
编辑一个文件input.txt包含一行文本：1+2+3+4。然后将文件置于和上一节的stdio.py程序相同的目录下，用如下命令运行程序。
$ ./stdio.py < input.txt
1+2+3+4 = 10 ~ 输出
可以看到，程序会直接在终端输出运行结果。在启动程序的命令中，小于号标记（<）告诉执行环境，在启动程序时，将标准输入流关联至指定文件input.txt。类似地，可以在启动程序时，将标准输出重定向至某个文件：
$ ./stdio.py > output.txt
1+2+3+4+5 ~ 用户终端输入
$ cat output.txt ~ 用cat命令查看输出的文件
1+2+3+4+5 = 15
重定向标准输出流，如何1.33所示。
图1.33 重定向标准输出流
重定向标记（＞）告诉执行环境，在启动程序时，将标准输出流关联至指定文件output.txt。可以看到程序不再输出至终端，而是创建output.txt文件进行输出。也可以同时重定向程序的标准输入和标准输出至不同的文件，请读者自行尝试。
【思考和扩展练习】
（1）思考在图1.33中，数字0和1有何实际含义。
（2）I/O重定向是如何实现的。
基于标准I/O工作的程序可以很容易通过管道行（pipeline）进行串接。这是将程序组装起来完成更复杂任务的便捷方法。例如，要对如下文本数据（学号 姓名 成绩）data.txt：
01|张三|95
02|李四|99
03|王五|80
进行两项处理：
$ tr "|" "," < data.txt
01,张三,95
02,李四,99
03,王五,80 sort命令可以根据指定的分隔符（-t）及指定列（-k）进行数值排序（-n）：
$ sort -n -t "|" -k 3 < data.txt
02|李四|99
01|张三|95
03|王五|80
现在我们想把这两个程序组合起来，在一条指令中完成任务，并且不使用临时文件。使用竖线 | 连接要执行的程序，就可以将前面程序的标准输出作为后面程序的标准输入，如图1.34所示。
运行结果：
$ sort -n -t "|" -k 3 < data.txt | tr "|" ","
03,王五,80
01,张三,95
02,李四,99
上述管道行串接I/O如图1.34所示。
图1.34 管道行串接I/O
【思考和扩展练习】
思考管道行是如何实现的。
启动程序时，操作系统通常会为进程打开3个流：标准输入、标准输出和标准错误。在shell（终端运行环境）中启动程序时，这3个流默认关联至终端。一般来说，各种编程环境对这3个流均有定义。在Python中可以通过导入sys模块来访问这3个流（stdin、stdout、stderr）。通过流对象进行I/O处理，可以获得比input()之类简单、I/O函数更全面的处理能力。
代码1.10和代码1.11分别展示了从标准输入流按行读入数据和一次性读入全部数据的方法。请读者尝试补齐并运行这些代码片段。本书将在1.8节用到这些方法。
代码1.10 片段：从标准输入按行读入数据
from sys import stdin
for line in stdin:
....
代码1.11 片段：从标准输入一次性读入全部数据
from sys import stdin
all = stdin.read():
.... 命令行参数是在程序启动时向程序传递的参数，用来指定源文件、目标文件或控制程序的具体行为。比如UNIX下的查看文件列表命令ls。加-l命令行参数调用时，会列出更详细的文件信息如下：
$ ls
1.txt data.txt argv.py rmsp.py
$ ls -l ~ 带命令行参数的调用
total 64
-rw-r--r-- 1 zhangdi staff 51 9 21 13:27 1.txt
-rw-r--r-- 1 zhangdi staff 51 10 11 22:02 argv.py
-rw-r--r-- 1 zhangdi staff 31 9 22 10:00 data.txt
-rwxr-xr-x 1 zhangdi staff 347 9 21 17:50 rmsp.py
命令行参数是执行环境向程序传参的机制，各种编程语言大都提供处理命令行参数的方法。Python通过导入sys模块的argv符号对命令行参数列表进行访问。其中，argv[0]是脚本名①，从argv[1]开始依次是命令行的各个参数。命令行参数如图1.35所示。31
图1.35 命令行参数
代码1.12打印全部命令参数。
代码1.12 argv.py打印全部命令行参数
#!/usr/bin/env python3
from sys import argv
for i,arg in enumerate(argv):
print("arg", i, ":", arg)
【程序运行结果】
$ ./argv.py cat dog monkey
arg 0 : ./argv.py
arg 1 : cat
arg 2 : dog
arg 3 : monkey
可以将代码1.2所示求最大公约数的函数改为从命令行接收参数的程序。该程序接收两个命令行参数，计算最大公约数之后将结果写入标准输出，如代码1.13所示。
代码1.13 gcd.py求最大公约数，使用命令行参数
#!/usr/bin/env python3
from sys import argv
a = int(argv[1])
b = int(argv[2])
while b!=0:
a, b = b, a%b
print(a)【程序运行结果】
$ ./gcd.py 24 15
3
$ ./gcd.py 125 205
5
【思考和扩展练习】
上一节的标准I/O对象stdin和本节的命令行参数对象argv都来自sys模块。查阅文档了解更多sys模块的知识。
环境变量是操作系统在程序运行时指定的一组环境参数。程序可以读取这些参数的值，并据此改变自身行为。在UNIX/Linux终端中输入env命令，可以看到系统设置的环境变量。由于环境变量很多，这里只列出以下几个：
$ env
......
TMPDIR=/var/folders/j_/d0ry5sq101144mmw2nlc8w8m0000gn/T/
......
USER=zhangdi
......
LANG=zh_CN.UTF-8
......【代码说明】
程序可以通过导入os模块中的environ字典对象访问环境变量，如代码1.14所示。
代码1.14 sayhi.py输出包含用户名的欢迎句子
#!/usr/bin/env python3
from os import environ
print("hello", environ['USER'])【程序运行结果】
$ ./sayhi.py
hello zhangdi 截至目前，本书的程序都是使用拼接生成包含某种可变部分的字符串，不但功能有限，而且可读性差。格式化字符串是用模板标记生成字符串的方法，在许多语言中都有实现。学习格式化字符串要掌握两个关键点，一是在字符串模板内指定可变部分来源的语法，二是控制显示格式的语法。
1．格式化字面值
在串字面值前加上字母'f'或'F'，就可以通过花括号占位符在字面值中指定替换的部分所对应的变量或表达式如下：
>>> name = 'Mike'
>>> f'My name is {name}'
'My name is Mike'
>>> fruit = 'Apple'
>>> price = 1.20
>>> F'{fruit}: ${price}/kg'
'Apple: $1.2/kg'
>>> F'{fruit} FOR SALE: ${price*0.8}/kg'
'Apple: $0.96/kg' 2．format()方法
使用字符串的format()方法，可以在设计模板时略去引用的变量名，从而反复使用该模板，如下：
>>> name = 'Mike'
>>> 'My name is {}'.format(name)
'My name is Mike'
>>> fruit = 'Apple'
>>> price = 1.20
>>> '{}: ${}/kg'.format(fruit,price)
'Apple: $1.2/kg'
在花括号占位符内可以加入序号以指定占位符对应的来源，如下：
>>> fruit = 'Apple'
>>> price = 1.20
>>> '{0} {0}: ${1}/kg'.format(fruit,price)
'Apple Apple: $1.2/kg' 3．显示格式标记
在上述例子中，浮点数1.20被显示为1.2，而0.96被显示为0.96。如果希望准确控制小数点后面显示两位数，就要在花括号占位符内加入冒号跟随的标记{:.2f}，从而使结果更像“价格”。
>>> fruit = 'Apple'
>>> price = 1.20
>>> F'{fruit}: ${price:.2f}/kg'
'Apple: $1.20/kg'
>>> '{0}: ${1:.2f}/kg'.format(fruit,price)
'Apple: $1.20/kg'注意：读者不需要努力练习以记忆各种显示格式标记。因为格式化字符串远远不能满足“排版需求”，所以工程师在绝大多数情况下只使用格式化字符串的“拼接替换”机制生成核心内容。更多的格式排版需求往往由CSS之类能够精确控制格式的标记语言另行实现。各种格式标记在日常编程中使用频率很低，即便记住也可能在一段时间后遗忘。富有经验的工程师在遇到实际的格式化需求时，通常是查阅文档或上网搜索相关的内容。
本节讲述了程序与外部环境传递信息的基本方法。在有宿主操作系统的环境下，最基本的信息传递方式有I/O流、命令行参数和环境变量。I/O流，尤其是标准I/O流，通常用来进行数据传输。命令行参数通常用来对程序行为进行精确控制。环境变量用以向程序提供运行环境的配置信息。利用I/O重定向或其他进程控制手段，可以很容易地将基于这些通信方式的程序集成到更大的软件体系中。
本节中的部分问题涉及微积分（1.7.5节）和数值计算（1.7.6节）的初步知识。如果读者不了解这些知识，可以跳过相关小节，这并不会影响阅读本书后面的章节。
本节是为初学程序设计的读者准备的内容，目的在于让读者通过一系列示例掌握各种分支控制结构。读者了解语法后，需要通过练习才能获得实在的编程能力。出于直观、趣味性考虑，本节中的部分例子使用了turtle绘图库。相关示例会引导读者逐步接触这个绘图库。
【学习目标】
注意：在学习本节内容时，上策是先阅读问题描述然后尝试自己动手编程解决问题，中策是先阅读代码获得思路然后动手独立写出，下策是抄写代码理解后再行独立写出。对于有一点程序设计基础的读者，建议采用上策或中策。对于完全没有程序设计基础的读者来说，采用先抄写的方法也许是必经之路。
问题描述：编写函数，打印如下金字塔图形。该函数接收一个参数n，用以指定金字塔层数。再编写程序，通过接收命令行参数获得金字塔层数。
*
* * *
* * * * * 笔者在教学中发现大部分初学者都能用循环正确地打印出该图案，但很多人都经历了混乱的调试过程。初学者在一开始往往都能想到使用固定次数循环来控制打印，但在具体打印空格和星号的次数上，往往需要反复试凑。究其原因，主要是没有清晰地推算循环次数和所打印内容之间的关系。下面展示了推算循环次数的过程，无论是初学者还是有经验的工程师，都应当尽量养成先使用纸、笔推演而后编码的习惯。越是避免在敲击键盘时思考，就越能够避免错误。
以打印4层金字塔图案为例：用range(4)对象控制for循环，循环变量会取遍0、1、2、3，于是可以推算打印的前置空格数和星号数目如下：
进一步写出代码1.15所示程序。
代码1.15 pyramid.py打印金字塔
#!/usr/bin/env python3
def pyramid(n):
for i in range(1,n+1):
print(' '* 2 * (n-i) , end='')
print('* ' *(i*2-1) )
if __name__ == '__main__':
from sys import argv
pyramid(int(argv[1]))
【代码说明】
$ ./pyramid.py 7
*
* * *
* * * * *
* * * * * * *
* * * * * * * * *
* * * * * * * * * * *
* * * * * * * * * * * * * 【思考和扩展练习】
（1）使用while循环完成本例。
（2）思考如何不使用循环完成本例。①
问题描述：3X+1问题又称Collatz猜想[3]。从任意正整数n开始，如果是奇数就乘以3再加1，如果是偶数就除以2。如此经过若干步，一定会得到1。编写程序（见代码1.16），针对前若干个正整数验证猜想的正确性。
代码1.16 threex.py验证3X+1猜想
#!/usr/bin/env python3
def threex(n):
cnt = 0
while n!=1 :
cnt += 1
if n%2 :
n = n*3+1
else:
n = n/2
else:
return cnt
if __name__ == '__main__':
from sys import argv
for i in range(1, int(argv[1])+1):
print("{}: {}".format(i, threex(i)))
【代码说明】
【程序运行结果】
$ ./threex.py 10
1: 0
2: 1
3: 7
4: 2
5: 5
6: 8
7: 16
8: 3
9: 19
10: 6
【思考和扩展练习】
上述示例如果猜想不正确，程序能正常结束吗？如何修改程序以处理这种情况？
问题描述：编写程序绘制正多边形。程序从命令行接收正多边形的边数及外接圆直径。
Python标准库的turtle模块①提供了绘图功能。它的工作原理是控制一个绘图笔在平面上移动以绘制曲线。程序中反复使用如下两条命令来绘制图形：
绘制正多边形的实现，如代码1.17所示。
代码1.17 polygon.py绘制正多边形
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
from sys import argv
from math import sin, pi # 正弦函数和圆周率
import turtle
n = int(argv[1]) # 命令行参数1是边数
d = float(argv[2]) # 命令行参数2是外接圆直径
t = turtle.Pen() # 获得画笔
t.pensize(2) # 设定线宽
# 绘制多边形
for _ in range(n):
t.forward(d*sin(pi/n))
t.left(360/n)
t.hideturtle() # 隐藏光标
turtle.exitonclick() # 单击画布退出 【代码说明】
在代码中的for循环仅仅起到控制循环次数的作用，循环变量并没有使用。所以代码使用下划线用作循环变量名，以提示读者并不需要在循环体内访问它。
for _ in range(n):
【程序运行结果】
$ ./polygon.py 8 200
会出现画布窗口和如图1.36所示绘制的图形。
【思考和扩展练习】
（1）如何修改上述示例程序，使第2个参数成为可选参数（当只传一个参数时，程序默认以100为外接圆半径绘制正多边形）？
（2）阅读argparse和getopt模块的文档。修改程序的调用方式，使其支持更灵活的命令行参数传递形式：
$ ./polygon.py -n 8 -d 200 -s 3
其中-n、-d、-s分别代表边数、直径和线宽。思考如何设计这些参数的默认值。
（3）当用户执行程序而没有传递任何参数时，程序应当有什么行为？根据你的想法修改程序。
（4）编写程序，绘制如图1.37所示的图形。
问题描述：在400×400的直角坐标范围内绘制正弦曲线。
为了充分利用绘制空间，首先对正弦曲线进行适当变换：
绘制正弦曲线的实现代码，见代码1.8。
代码1.18 sin.py绘制正弦曲线
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
import turtle
from math import sin,pi
def drawline(t,x1,y1,x2,y2): # 绘制直线
s = t.pen() # 保存笔的状态
t.penup() # 抬起笔
t.goto(x1,y1) # 移动到线段起点
t.pendown() # 放下笔
t.goto(x2,y2) # 绘制直线
t.pen(s) # 恢复笔的状态
def move(t,x,y):
s = t.pen()
t.penup()
t.goto(x,y)
t.pen(s)
def func(x):
return 200 * sin(pi*x/100) + 200
t = turtle.Pen()
t.pensize(2)
# 绘制坐标轴
drawline(t,-20,0,410,0)
drawline(t,0,-20,0,410)
# 绘制正弦曲线
move(t, 0, func(0))
for i in range(1,400):
t.goto(i, func(i))
# 隐藏绘图笔
t.hideturtle()
turtle.exitonclick()【代码说明】
【程序运行结果】
$ ./sin.py 会出现画布窗口和如图1.38所示绘制的图形。
【思考和扩展练习】
（1）思考如何为坐标轴加上刻度和箭头，编写程序实现之。
（2）思考如何编写通用的程序，用以绘制各种数学函数。
问题描述：编写程序，模拟蒙特卡洛方法求如图1.39所示的正弦曲线包围的阴影部分面积的过程。
蒙特卡洛方法：随机在给定的区域内生成点，统计落在阴影内部的点的比例，将总面积乘以该比例，即可得到阴影面积的近似值，如图1.40所示。
图1.38 使用turtle库绘制的正弦曲线
图1.39 正弦曲线阴影面积
图1.40 蒙特卡洛方法
在400×400的区域内绘制半周期的正弦曲线，曲线方程为：
具备微积分知识的读者可以很容易地求出阴影面积为：
不具备微积分知识的读者可以默认接受这个结果。有了精确的计算结果，可以将代码1.19的运行结果和该数据进行比对。
代码1.19 monte_sim.py模拟蒙特卡洛方法
#!/usr/bin/env python3
import turtle
import random
from math import sin,pi
from sys import argv
n = int(argv[1]) # 命令参数用来指定点数
t = turtle.Pen() # 获取画笔
t.pensize(2) # 设定线宽
for _ in range(4): # 绘制 400×400 正方形
t.forward(400)
t.left(90)
def f(x): # 正弦函数
return 400 * sin(pi*x/400)
for i in range(401): # 绘制正弦曲线
t.goto(i, f(i))
def move(t, x, y): # 移动光标，用来画点
s = t.pen()
t.penup()
t.goto(x, y)
t.pen(s)
count = 0 # 计数阴影内点数
for i in range(n):
x = random.uniform(0, 400) # 产生[0,400]区间随机数
y = random.uniform(0, 400)
if(y < f(x)):
move(t, x, y)
t.dot(10, 'black')
count += 1
else:
move(t, x, y-5)
t.circle(5, 360)
else:
print(f"total dots: {n}")
print(f"inner dots: {count}")
print("area is {}".format(400*400*count/n))
t.hideturtle()
turtle.exitonclick() 【程序运行结果】
以500点数运行程序，运行结果如下：
$ ./monte_sim.py 500
total dots: 500
inner dots: 316
area is 101120.0
会出现画布窗口和如图1.41所示绘制的图形
【思考和扩展练习】
（1）学习过概率和统计理论的读者，请计算蒙特卡洛方法的误差。
（2）请尝试根据图1.42所示，用细长矩形面积之和近似求出相应面积。
（3）编写程序，绘制图1.42。
数值计算是计算机的重要应用领域。对于工科类学生而言，数值计算显得尤为重要。
问题描述：用简单迭代法求方程x3-13x+12=0的根。
上述方程可以因式分解为(x+4)·(x-1)·(x-3)，可知方程有3个根-4、1、3。很多方程无法进行简单因式分解，也无法推导出求根公式，这时候用数值方法得到方程的根就是唯一办法。
埃特金迭代法的基本思想：
首先将待求解的方程f(x)=0变换为，选定x0，用如下公式进行迭代计算：
得到迭代序列x0,x1,…,xn,…在很多情况下，数列会收敛到f( x)=0的一个根。当接近迭代终点时，要注意被0除的问题。一般取一个很小的在时结束计算。
如果不知道循环的次数，但知道循环的终止条件，往往使用while循环比较合适。对待求解的方程进行变换得到：
埃特金迭代法的实现，如代码1.20所示。
代码1.20 root.py埃特金迭代法
#!/usr/bin/env python3
from sys import argv
x = float(argv[1]) # 从命令行获得迭代初值
def phi(x): # 迭代函数
return (x**3 + 12)/13
while True :
x1 = phi(x)
x2 = phi(x1)
print(x,x1,x2) # 打印中间结果
if abs(x2-x1)<1e-20 : # 判断是否达到迭代终点
x = x2
break
else:
x = x2 - (x2-x1)**2/(x2-2*x1+x)
# 打印最终结果
print(f'root: x={x2}') 【程序运行结果】
在运行示例中，分别以(-5, 0, 5)作为初值进行迭代，求得方程的3个根(-4.0, 1.0, 3.0)。
$ ./root.py -5
-5.0 -8.692307692307692 -49.596757816603045
-4.633637431126367 -6.729765889795242 -22.522262116636398
-4.312840370941419 -5.2477987986386605 -10.193937651157373
-4.094912686583765 -4.358828075852047 -5.447310810361147
-4.010442530089406 -4.038657780017554 -4.144120330725059
-4.000136664117704 -4.00050462321364 -4.001863459239868
-4.000000023640827 -4.000000087289208 -4.00000032229862
-4.000000000000001 -4.0000000000000036 -4.000000000000013
-4.0 -4.0 -4.0
root: x=-4.0
$ ./root.py 0
0.0 0.9230769230769231 0.9835790063373131
0.9878226984900146 0.9972239345965173 0.9993611463086975
0.9999899539303033 0.9999976816995139 0.9999994650088204
0.9999999999930131 0.9999999999983876 0.999999999999628
1.0 1.0 1.0
root: x=1.0
$ ./root.py 5
5.0 10.538461538461538 90.95329295192745
4.590330617466819 8.363344380828009 45.921426836094376
4.168971910508688 6.496776475808971 22.016663146300097
3.75821991161O83297 5.006301015765117 10.574859382657447
3.3976795481820954 3.9402755107943324 5.628908896564066
3.140785338015766 3.3063368589557487 3.703417152213995
3.0224099593916924 3.046892308809036 3.0989219574182623
3.000651549290658 3.00135351167482 3.0028124081264953
3.0000005663187896 3.000001176200785 3.000002442879512
3.0000000000004285 3.00000000000089 3.0000000000018483
3.0 3.0 3.0
root: x=3.0 【思考和扩展练习】
（1）思考埃特金迭代法在哪些情况下可能会陷入无穷循环，修改程序以摆脱这种情况。
（2）选取不同的迭代初值，查看迭代行为，思考如何确定迭代初值。
（3）上述方程也可以使用作为迭代公式，比较不同迭代公式的行为。
（4）思考如何编写通用的埃特金迭代算法，使之适用于不同的方程。
（5）查阅互联网，研究还有哪些求解非线性方程的迭代方法，编程实现并与埃特金方法比较。
本节介绍的示例和习题涉及多个领域。读者（尤其是本科低年级的学生或中学生）应当积极在其他学科的学习中充分使用Python。程序设计能力对数学、科学和工程学的学习有很大帮助。
在上一节中，本书向读者展示了程序设计的一些具体示例。通过这些示例，读者应当已经了解到编写代码的初步方法。但这些示例比较初级。这种初级在于，从问题描述本身出发就容易设计并编写程序。比如埃特金迭代法，虽然其原理涉及较复杂的数学，但从编程角度来说，只需要按照算法步骤描述，就可轻易写出程序。
本书将向读者展示程序设计的核心思考方法。使用这些方法，可以让工程师在面临具体的局部问题时能够设计出恰当的程序。本节提出的问题种类分为以下3个层次：
这和在本书1.1节中提到的基本模型“图灵机”是相吻合的。图灵机模型的核心思想正是由状态机配合线性存储器完成各种各样的计算任务。为了突出设计程序的本质方法，本节的前几个示例将程序设计手段限制于最简单的输入和输出、控制结构，以及简单的字符和字符串处理方面。
输入和输出、赋值、运算、条件判断、循环和分支、顺序存储结构，学会了这些，就足以写出解决各种问题的程序。基本上各种程序设计语言都支持这些特性。本节将带领读者使用这些核心程序设计手段，解决各种程序设计问题。核心能力一旦建立，就会自然得以推而广之。
【学习目标】
为了凸显本质，往往要在其他方面作出简化。1.8.1节、1.8.2节和1.8.3节讨论的问题从形式上来说大多都很简单，尤其是1.8.2节和1.8.3节。不仅如此，起初的几个例子还把IO手段限制在单个字符方面。因为唯有这样才能尽早向读者展示本节的核心主题。这就好比徒手盖房，虽然房子很简陋，但却对一砖一瓦都心中有数。
注意：在初学阶段使用高级工具会阻碍核心能力的建立。
从标准输入流中逐个获得字符并输出的代码片段如下：
from sys import stdin
for c in stdin.read():
print(c, end='') 上述代码中，stdin.read()方法从标准输入流读取全部数据。用for循环的循环变量c会取遍标准输入流的每个字符。print()函数将字符输出。这段程序只是简单地将输入复制到输出，每次一个字符。接下来的例子将根据具体问题的需求在循环里对数据进行处理。
最简单的程序是无状态的，即程序在计算过程中不需要“记住”什么。这类程序只需根据输入进行分类讨论即可，最常使用的就是if-else结构。在这类问题中使用查找表结构往往能让代码更简洁。
注意：在实际问题中，单纯的“不需记忆状态”程序很少。但程序是由很多代码片段组成的，其中很多都具有无状态特性。清晰、高效地处理这部分代码，能大大提高编码质量。
问题描述：根据手机中九宫格按键上的字母和数字的对应关系，如图1.43所示，将输入中的英文字母转换成对应的数字。
图1.43 手机中的九宫格按键盘
举例来说，程序应当在收到如下输入时：
010 - PYTHONer
+86 138PROGRAMM
给出如下输出：
010 - 79846637
+86 13877647266问题分析：解决这个问题要构建下述程序结构。
程序结构如图1.44所示。
图1.44 程序结构
既然I/O已经被限制在单个字符上，如何设计“替换机制”就是首要问题。根据不同输入决定不同的输出内容来看，这是一个“分情况讨论”的问题。显然可以使用1.5.1节介绍的if-else结构。这就是下文“版本1”所示的解决方案。
版本1：使用if-else结构
这个简单的问题具有一定代表性。笔者在教学过程中做过试验，在现场练习中让学生编写代码，绝大多数初学者都会使用如下if-else结构：
if c=='A' or c=='B' or c=='C':
print(c, end='')
elif c=='D' or c=='E' or c=='F':
... 这样写当然能够正确处理这个问题，但相当烦琐，如代码1.21所示。
代码1.21 tel.py if-else 版本的字符转换
#!/usr/bin/env python3
from sys import stdin
for c in stdin.read():
c = c.upper()
if c=='A' or c=='B' or c=='C':
print(2, end='')
elif c=='D' or c=='E' or c=='F':
print(3, end='')
elif c=='G' or c=='H' or c=='I':
print(4, end='')
elif c=='J' or c=='K' or c=='L':
print(5, end='')
elif c=='M' or c=='N' or c=='O':
print(6, end='')
elif c=='P' or c=='Q' or c=='R' or c=='S':
print(7, end='')
elif c=='U' or c=='V' or c=='W':
print(8, end='')
elif c=='X' or c=='Y' or c=='Z':
print(9, end='')
else:
print(c, end='')【程序运行结果】
$ ./tel.py
010 – PYTHONer ~ 输入
+86 138PROGRAMM ~ 输入
（按 ctrl + D键结束输入）
010 – 79846637 ~ 程序输出
+86 13877647266 ~ 程序输出
为了不用每次都输入测试数据，可以将其保存至文本文件中，使用输入重定向为程序提供数据。将输入数据存入data.txt文件中，然后执行如下程序：
$ ./tel.py < data.txt
010 - 79846637
+86 13877647266 关于该程序的讨论：
首先要指出的是该程序虽然行数很多，但结构清晰、易懂，不失为解决问题的良好起点。同时应当注意到代码中存在大量的冗余，如图1.45所示。①34
图1.45 tel.py版本1的冗余之处
注意：程序设计语言提供了多种机制以消除冗余的代码。这是程序员应掌握的主要技巧之一。作为初学者，应当对“冗余的代码”保持敏感。在工程实践中大规模消除冗余代码的努力往往能够换来生产力的显著提高。请参见本节末尾的“思考和扩展练习”，尝试消除代码1.21的冗余之处。
当条件的取值集合为连续整数时，应当首先考虑使用顺序存储结构作为查找表，这通常能使程序格外简洁和高效。于是有了以下版本2的解决方案。
版本2：使用ASCII码作为查找表索引
大写字母A至Z的ASCII码②为65～90。将字母转换为大写，然后转换为ASCII码，即可得到连续整数。再从结果中减去起始偏移65，即可得到从0开始的整数序列。在Python中使用ord函数计算字符的ASCII码，如代码1.22所示。
代码1.22 tel.py查找表版本的字符转换
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
from sys import stdin
table = '22233344455566677778889999'
A = ord('A') # 字母 A 的 ASCII 码
for c in stdin.read():
if c.isalpha():
print(table[ord(c.upper()) - A], end='')
else:
print(c, end='') 版本3：使用字典作为查找表
字典结构可以实现一般性的查找表，不受“连续整数索引”限制，见代码1.23。
代码1.23 tel.py查找表版本的字符转换
#!/usr/bin/env python3
from sys import stdin
table = {
'A':2, 'B':2, 'C':2, 'D':3, 'E':3, 'F':3,
'G':4, 'H':4, 'I':4, 'J':5, 'K':5, 'L':5,
'M':6, 'N':6, 'O':6, 'P':7, 'Q':7, 'R':7, 'S':7,
'T':8, 'U':8, 'V':8, 'W':9, 'X':9, 'Y':9, 'Z':9
}
for c in stdin.read():
print(table.get(c.upper(), c), end='') 【代码说明】
字典类型的get()方法（table.get()）用于根据键取出值。该方法与索引取值（[ ]）的不同之处在于可以传递第2个参数以指定查无此键时返回的默认值。
版本4：使用maketrans和translate
查找表替换在字符串中是如此常用，以至于Python将其实现为内建功能。开发者使用maketrans和translate可以构建一个转换表并据此对字符串进行转换。使用Python内建查找表替换的程序如代码1.24所示。①
代码1.24 tel.py使用maketrans生成查找表的版本
#!/usr/bin/env python3
from sys import stdin
table = bytes.maketrans(b'ABCDEFGHIJKLMNOPQRSTUVWXYZ',
b'22233344455566677778889999')
print(stdin.read().upper().translate(table))
笔者在多年的教学过程中发现，很多有过数年工作经验的工程师在遇到实际问题时首先考虑if-else结构，因为if-else能够解决一切“分情况讨论”问题。虽然比较省事，但这样做往往会导致烦琐的代码（有时也低效）。笔者的建议是，如果掌握了多种技巧，而这些技巧的应用领域有包含关系（比如用查找表能解决的问题用if-else都能解决，如图1.46所示），在遇到问题时应当首先尝试那些应用范围较小的技巧，这往往会让你写出更漂亮的代码。具体到本节的问题而言，就是先考虑能否用查找表解决问题，如果不行，再用if-else分支进行逐个条件的判断。
【思考和扩展练习】
（1）针对版本1：使用in操作符消除反复判断的级联or逻辑表达式。
elif c in 'DEF' :
...
elif c in 'GHI' :
...
（2）针对版本1：print()函数每次都要指定参数end='?'。参见2.6.3节的扩展练习，利用那里提及的partial()函数消除此种冗余。
（3）针对版本1：思考有何方式消除级联elif冗余。
（4）分析4个版本实现的性能，并思考如何实际验证你的结论。
（5）bytes.maketrans()和str.maketrans()都能生成转换表，二者有何区别？
前一节所示程序的特点是输出仅与当前输入有关：当输入字母A时就输出数字2，当输入M时就输出数字6。程序的核心就是循环加上查找逻辑，不需要“记住什么”。但一般的场景是：输出不仅取决于输入，还取决于“状态”。
当在键盘上按回车键时，计算机显然不是每次都给出一样的结果。比如，在字处理软件的编辑框中按回车键会换行，在第一人称的射击游戏中按回车键则往往是开枪。这就是状态对行为的影响。
这类程序归纳起来具有如下行为：
具有状态记忆特性的程序执行过程如图1.47所示。
接下来将以一个具体示例来说明这类程序的结构和设计方法。
问题描述：缩减文本中的连续空格，将标准输入文本中的连续空格缩减为一个。这个问题是有现实意义的，很多程序设计语言都是“空格不敏感”的，编译系统在处理时往往要去掉多余的空格。
输入示例：
int main( ) {
return 0 ;
}
输出示例：
int main( ) {
return 0 ;
}图1.47 具有状态记忆特性的程序执行过程
问题分析：本问题虽然也很简单，但和1.8.2节的“手机中的九宫格键盘文本替换问题”有本质的不同。程序接收到空格字符，不能仅仅根据该字符确定输出行为，而是需要根据前一个字符是否是空格来决定。程序需要记住“上一个收到的字符是否是空格”这个事实，如图1.48所示。
图1.48 程序的状态变化
状态是“非此即彼”，看起来似乎是布尔类型，但为了将来的扩展方便，我们使用整数变量s来记录，值为0表示“之前没收到空格”，值为1表示“之前恰好收到空格”。如图1.49所示为程序工作时的状态转换过程。
图1.49 去除连续空格的状态机模型
在图1.49中，圆圈表示两个状态：
也可以用查找表结构写出上述模型，如图1.50所示。
图1.50 状态机查找表
查找表更容易和代码对应，但没有状态转移图直观。在实践中，如果状态图简单，则无须使用表格形式；如果复杂，则拆分状态图并配合使用表格，以避免错误。将上述模型转换为代码是非常容易的事情，不同的状态对应依据状态s值的程序分支，不同输入的行为（空格和非空格）则是再嵌套一层依据变量c值的程序分支，在最底层的分支里要做两件事情，即输出某个字符（或不输出）和修改状态。
版本1：状态机模型
根据前述模型，写出完整的程序，如代码1.25所示。
代码1.25 rmsp.py缩减连续空格
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
from sys import stdin, exit
s = 0
for c in stdin.read():
if s==0: # 状态0
if c==' ':
print(' ', end='') # 转换曲线1
s=1
else:
print(c, end='') # 转换曲线4
s=0
elif s==1: # 状态1
if c==' ':
print('', end='') # 转换曲线2
s=1
else:
print(c, end='') # 转换曲线3
s=0
else:
raise ValueError(f's={s}') # 不会执行至此【代码说明】
【程序运行结果】
将问题描述中的示例保存至文本文件input.txt中，运行程序结果如下：
$ ./rmsp.py < input.txt
int main( ) {
return 0 ;
} 版本2：使用正则表达式处理文本替换
识别或替换某种文本模式，是程序设计的常见问题。在程序设计中，对这类问题的标准解法是采用“正则表达式”模型。许多程序设计语言都将正则表达式作为语言标准的一部分实现。用Python中的正则表达式机制替换多个连续空格为单个空格只需要一行代码，完整程序如代码1.26所示。
代码1.26 字母转换——正则表达式
#!/usr/bin/env python3
from sys import stdin
import re
s = stdin.read()
s = re.sub(r' +', ' ', s)
print(s, end='')【代码说明】
扩展问题：更加复杂的状态。
前述例子使用了最简单的状态机（之所以最简单，是因为只有两个状态），现在稍微拓展一下问题：将双引号围绕起来的文本看做字符串，保留其中的空格数量不变，仅仅缩减双引号外的空格。为了简化问题，假设双引号总是成对出现，并且不考虑在双引号中还有转义双引号的情形。
输入示例：
" xxx xx xx"
int main( ) {
"doc string ..."
return 0 ;
}
输出示例：
" xxx xx xx"
int main( ) {
"doc string ..."
return 0 ;
}
这样一来，程序还需要记住“在双引号里”这个状态。于是便有3个状态：刚收到空格（引号外）、刚收到非空格字符（引号外），以及在双引号内部的状态。注意，在引号内部是不需要区分空格和非空格字符的。
状态图的扩展：可以完全保留之前画的状态转换图，只是在上面再添加一个新状态2（引号内），再辅以一些转换箭头，如图1.51虚线部分所示。
图1.51 为状态机增加状态
版本3：在原有程序（代码1.25）上增加状态
既然状态转换图可以原样保留略作修改，那么之前的代码也可以整个拿过来再添加一些分支即可，如代码1.27所示。
代码1.27 字母转换（3个状态、保留双引号内空格）
#!/usr/bin/env python3
from sys import stdin, exit
s = 0
for c in stdin.read():
if s==0:
if c==' ':
print(' ', end='')
s=1
elif c='"':
print('"', end='')
s=2
else:
print(c, end='')
s=0
elif s==1:
if c==' ':
print('', end='')
s=1
elif c='"':
print('"', end='')
s=2
else:
print(c, end='')
s=0
elif s==2:
if c='"':
print('"', end='')
s=0;
else:
print(c, end='')
s=2
else:
exit()注意：状态机是一种标准的程序设计手段。即便不了解这种模型的程序员也总是不自觉地设定一些状态并编写代码，处理状态的转换。理解这种模型的普遍性意义，能够更系统化地设计程序和软件系统，提升编码效率，避免或减少错误。
【思考和扩展练习】
（1）在互联网上检索正则表达式教程，学习正则表达式。
（2）查阅Python文档，了解Python对正则表达式的支持。
（3）如下是一个带注释的C语言程序。编写程序去除注释。实现要求：C语言有两种注释方式，用//表示单行注释，用/ /表示跨行注释。将每段注释替换为一个空格。保留单行注释末尾的换行符。无须考虑/*字符在字符串或字符中的情况（假设没有字符串字面值）。
// comment
int main(void) { // comment
/* comment */
return 1*5+1/5; /* comment
* comment */
}
上述代码片段应当被替换为：
int main(void) {
return 1*5+1/5;
} 有时候，仅仅记住有限个确定状态是不够的，这时就需要通过某种数据结构来存储数量不确定的数据。基本的数据结构是线性结构，这也最符合存储器的物理结构，如图1.52所示。
图1.52 配合线性存储器的程序
能够动态扩展长度，支持任意位置插入删除的线性结构被称为列表（这正是Python的内建数据类型“列表”得名的原因）。然而，更简单的结构只在线性结构的一端放入或取出数据，这种结构被称为“栈”（stack）。稍微复杂一点的线性结构在一端放入数据，在另一端取出数据，这种结构被称为“队列”（queue）。①
栈在列表的一端添加和删除数据，这两个操作被称为入栈（push）和出栈（pop），也被形象地译为“压入”和“弹出”。栈操作示意图如图1.53所示。
图1.53 栈操作示意图
Python的列表类型可以很容易地实现入栈和出栈操作。向列表尾部添加元素的方法被命名为append，这是列表类型的习惯。只使用append()和pop()对列表进行访问，就相当于在使用一个栈，例如：
>>> s = []
>>> s.append('P')
>>> s.append('O')
>>> s.append('T')
>>> s
['P', 'O', 'T']
>>> s.pop()
'T'
>>> s.pop()
'O'
>>> s.pop()
'P'
>>>
队列在列表的一端添加数据，在另一端获取并删除数据。队列是和栈相对称的数据结构。队列的特点是先进先出（FIFO First-in，First-out），或称为“先来先服务”。读者可以形象地把队列想象成一个管道，从管道的一端放入数据，从另一端取出数据。数据的取出顺序也就是放入的顺序。在计算机科学术语中，向队列中添加数据被称为“入队”（enqueue），从队列中取出数据被称为“出队”（dequeue）。队列操作示意图如图1.54所示。
图1.54 队列示意图
Python的queue模块的Queue对象实现了典型的队列结构。该对象针对线程间的消息通信场景而设计，所以使用get()和put()作为出队和入队的方法名。
>>> q = Queue()
>>> a.put('A')
>>> q.put('A')
>>> q.put('B')
>>> q.put('C')
>>> q.get()
'A'
>>> q.get()
'B'
>>> q.get()
'C'
Python的collections模块实现了更一般的双端队列（double-ended queue）结构deque，在两端都可以进行存、取操作。
>>> from collections import deque
>>> dq = deque()
>>> dq.append('A')
>>> dq.append('B')
>>> dq.append('C')
>>> dq
deque(['A', 'B', 'C'])
>>> dq.popleft()
'A'
>>> dq.popleft()
'B'
>>> dq.popleft()
'C'本节介绍了两种重要的结构：栈和队列。接下来的1.8.5节和1.8.6节将分别举例介绍这两种数据结构在程序设计中的应用。
为了演示栈这种结构在程序设计中的应用，请看如下问题：
注意：本节的示例将在异常处理（1.10节）中再次用到。不要轻易因为逆波兰表达式的概念有些晦涩而跳过本节。
问题描述：逆波兰表达式是将运算符写在运算数后面的表达式①，也叫做后缀表达式，参见1.2.3节。下面给出了逆波兰表达式的例子。逆波兰表达式是不需要括号和优先级规则的，运算的次序已经包含在运算符的出现次序中了。在以下示例中，第2列的括号是为了让读者方便理解特意加上的。
逆波兰 加上括号便于理解 对应的中缀表达式
1 2 + 1 + 2
1 2 + 3 * (1 2 +) 3 * (1 + 2) * 3
4 8 3 2 * - / (4 (8 (3 2 *) -) /) 4 / (8 - 3 * 2)
计算过程如图1.55所示。
图1.55 逆波兰表达式计算过程
在类UNIX操作系统的命令行中，默认安装的程序dc可以用来计算逆波兰表达式。运行dc后，输入表达式，以p结尾即可看到表达式的结果。②
$ dc
1 2 + p 输入
3 输出
1 2 + 3 * p
9
4 8 3 2 * - / p
2
请读者试着写下一些逆波兰表达式进行计算，用dc程序验证结果。
问题分析：在计算过程中可以看到，从左至右扫描的程序在看到运算符之前需要“记住”已经出现的运算数。需要记住的运算数的数量是不定的。进一步观察可以发现如下事实：后出现的运算数总是先进行运算。比如算式4 8 3 2 * - /，运算过程如下：
在这个过程中需要一个后进先出的存储结构来存储扫描到的操作数，这就是栈。
栈是一种逻辑结构，任何实现了“后进先出（LIFO：Last-in，First-out）”的结构都可以被称为栈。在本例中以Python的列表实现栈，append()方法在列表的尾部添加数据（入栈），pop()方法在列表的尾部读取数据并移除（出栈）。使用栈这种抽象数据类型，计算逆波兰表达式的方法可以描述如下：
这个描述很抽象，但理解抽象的算法描述也是程序员必备的能力之一。常用的方法是构造一个例子，根据算法的描述，按部就班求解一遍。以2(3+4)为例，该表达式的逆波兰表示为2 3 4 + 。从左向右扫描表达式会首先遇到3个操作数2、3、4，这3个操作数依次入栈。再扫描到+运算符，根据算法描述，把栈顶的运算数3、4出栈计算3+4，得到结果7，将其入栈。这时候栈里的数据是2、7。最后扫描到运算符，同样将栈顶运算数取出进行计算，27得到结果14，将其入栈。扫描完毕，此时栈顶元素14就是计算结果。计算过程示意图，如图1.56所示。
代码实现：根据上述算法描述，可以写出如代码1.28所示程序。
代码1.28 rpn.py逆波兰表达式计算
#!/usr/bin/env python3
from sys import stdin
from operator import add, sub, mul, floordiv
op_dict = {
'+': add,
'-': sub,
'*': mul,
'/': floordiv
}
for line in stdin :
s = []
for tok in line.split():
if tok.isdigit():
s.append(int(tok))
else:
op = op_dict[tok]
b = s.pop()
a = s.pop()
s.append(op(a, b))
else:
print(s[0])图1.56 逆波兰表达式算法中栈的变化
【代码说明】
>>> s = "13 24 56 + *"
>>> s.split()
['13', '24', '56', '+', '*']【程序运行结果】
$ ./|rpn.py
1 2 3 4 * + - ~ 输入
-13 ~ 输出
2 3 4 + * ~ 输入
14 ~ 输出 【思考和扩展练习】
（1）UNIX/Linux命令行的dc程序用p命令来打印栈顶元素，quit命令退出。另外，dc程序会将输入当做连续的算式，而非一行一个。请编写程序，模拟dc的这种行为。
（2）修改代码1.28，使其支持浮点数表达式。
（3）当用户在终端输入无效表达式时会导致什么情况发生？如何处理这些情况？①
（4）以下是中缀表达式((1+2)3)转换为后缀表达式(1 2 + 3 )的算法过程。阅读并理解该算法，根据算法编写转换程序。
（1）自左开始扫描表达式。
（2）如果扫描到数，则输出。
（3）如果扫描到左括号，则入栈。
（4）如果扫描到右括号，反复读取栈顶：如果栈顶不是左括号，则将栈顶的运算符出栈输出。直至栈顶为左括号，将这个左括号出栈丢弃，同时丢弃前述右括号。
（5）如果不是上述情况，则扫描到的定然是运算符，反复读取栈顶：如果栈顶为运算符，并且扫描到的运算符小于等于栈顶运算符优先级，则栈顶运算符出栈输出。直至栈顶为较低优先级运算符或左括号，将扫描到的运算符入栈。
（6）扫描结束后，栈里的所有运算符出栈输出。
（7）输出即为逆波兰表达式。
栈是有重要意义的数据结构。当问题本身具有“后进先出”的特性时，其解法往往会涉及栈。这种特性是普遍的。因为人的头脑构建复杂概念的方式是递归的（由小的概念不断复合构成大概念），而对复杂问题的解析往往需要先拆解大问题为多个小问题，然后解决依次得到的小问题，再返回来解决最初的大问题。本节用来举例的后缀表达式计算和扩展练习的表达式转换正是递归概念的体现（参见1.2.4节）。本书将在2.4节详细讨论递归，并且在2.4.6节揭示递归和栈的关系。
队列在通信相关应用中有着天然的应用：先发送的数据当然先处理。但在初学阶段不适宜用此类问题举例，因为这涉及通信协议，如TCP/IP协议等复杂知识。本节以广度优先搜索（Breadth-First-Searching，这是由Edward F. Moore在1959年首先发表的算法[4]）解决简单寻路问题为示例，展示队列这种数据结构在程序设计中的应用。
问题描述：在N×N的方格形地图内有出发点、目的地和障碍物，如图1.57所示。寻找从出发点到目的地的最短路径。本例设定只能上、下、左、右移动，不能走斜线。
问题建模：首先要将问题转换为Python可以处理的数据类型。在本例中使用嵌套列表来描述二维方格地图。用字符O表示通路，用字符#表示障碍物。在地图边上用障碍物加了一圈“围栏”，这样在寻路的过程中不用刻意判断是否到达地图边界，如图1.58所示。
为此设计两个函数make_terrain()和draw_terrain()，前者用以根据障碍物坐标列表生成地图，后者打印地图，如代码1.29所示。
图1.57 寻路地图场景
图1.58 用嵌套列表表示二维地图
代码1.29 terrain.py生成和绘制二维地图
def make_terrain(x, y, obstacle ):
m = []
m.append(list('#'*(y+2)))
for _ in range(x):
m.append(list('#'+'O'*y+'#'))
m.append(list('#'*(y+2)))
for ob in obstacle:
m[ob[0]][ob[1]] = '#'
return m
def draw_terrain(m):
print()
for row in m:
for grid in row:
if(grid=='O'):
print(' ', end=' ')
else:
print(grid, end=' ')
else:
print() 【程序运行结果】
生成前述两堵墙的7×7地图：
$ python3 -i terrain.py
>>> wall = ((3,3), (4,3), (5,3), (4,6), (5,6))
>>> s = make_terrain(7, 7, wall)
>>> draw_terrain(s)
# # # # # # # # #
# #
# #
# # #
# # # #
# # # #
# #
# #
# # # # # # # # #
算法分析：解决这个问题有很多种方法，在本节中使用普通的广度优先搜索算法来处理。本书将在3.6节的综合练习中介绍更先进的算法来解决类似的问题。
广度优先算法的关键是维护一个“探路前线”，每次从这个“前线”中拿出一个节点继续探路，将新探到的节点置为新的前线。探路的过程是尽可能地先搜索邻近的位置（广度优先）①：优先从那些较早搜索过的节点再往外搜索。这就符合先进先出的特性，用队列结构存储“探路前线”。广度优先搜索的示意图，如图1.59所示。
假设从S出发到E点。首先从S开始向四周探路，走一步可以到达S点上、下、左、右的位置，在地图中标记这些点到出发点的距离（S右边是障碍物所以不标注）。此时探路的前线变为3个标注为1的点，通过这3个点再次向外探路得到5个标注为2的点。如此周而复始，最终标记完全部的点。标记的数字就是从出发点走到这些点的最短步数。为了找到路径，还需要从终点反向构建路径。构建方法也很简单，只要沿着某一条数字递减的路径一直递减到0即可。用广度优先算法的寻路过程，如图1.60所示。
完整的算法描述：
（1）将起始位置距离值设为0，将该位置放入队列。
（2）当队列空时则转到步骤（5）。当队列不空时，取出元素，访问取出位置的邻居。
（3）如果邻居位置没有访问过，将邻居节点置为已访问，并且将距离置为取出节点的距离+1。
（4）转到步骤（2）。
（5）此时已经完成地图全部位置的探索，从目的节点反向出发。
（6）探索周围邻居，找到一个距离值小的节点记录下来。
（7）如果该节点距离值是0，则算法结束。如果该节点距离值不是0，则以该节点为出发点转到步骤（6）。
根据该算法描述，写出如代码1.30所示程序。
图1.59 广度优先搜索的示意图
图1.60 用广度优先算法的寻路过程
代码1.30 bfs.py搜索最短路径
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
from terrain import make_terrain, draw_terrain
from queue import Queue
def bfs(row, col, wall, S, E):
m = make_terrain(row, col, wall)
q = Queue()
q.put(S)
m[S[0]][S[1]] = 0
while not q.empty():
x,y = q.get()
neighbor = (x-1,y), (x+1,y), (x,y-1), (x,y+1)
for i,j in neighbor:
if m[i][j]=='O':
m[i][j] = m[x][y] + 1
q.put((i,j))
# 以下为构建路径
path_map = make_terrain(row, col, wall)
x, y = E[0], E[1]
path_map[x][y] = 'E'
while m[x][y] != 0:
neighbor = (x-1,y), (x+1,y), (x,y-1), (x,y+1)
for i,j in neighbor:
v = m[i][j]
if v != '#' and v < m[x][y]:
x, y = i, j
path_map[x][y] = '*'
break;
else:
path_map[x][y]='S'
return path_map
【程序运行结果】
将terrain.py和bfs.py置于相同目录下，执行程序：①43
$ python3 -i bfs.py
>>> wall = ((3,3), (4,3), (5,3), (4,6), (5,6))
>>> S, E = (3,2), (4,7)
>>> draw_terrain( bfs(7,7,wall,S,E) )
# # # # # # # # #
# #
# * * * * * * #
# S # * #
# # # E #
# # # #
# #
# #
# # # # # # # # #
【思考和扩展练习】
（1）如图1.61所示，游戏地图往往有不同类型的“地形”，比如硬地、草地和森林，经过不同地形所耗费的行动力也不同。如何解决这种场景下的寻路问题呢？
图1.61 具有地形的地图
（2）游戏地图不仅有正方形格点，还有蜂窝状格点，如图1.62所示。如何表示蜂窝状的地图格点？如何处理相应的寻路问题呢？
图1.62 蜂窝状地图
本节讲述了程序设计的基本模型（这些基本模型并不简单）：状态机和线性存储器模型，这是图灵计算模型的核心。没有现成工具直接解决问题时，工程师可以回退到基本模型构建解决方案。
在线性存储模型部分，本节介绍了栈和队列这两种数据结构。这两种结构的应用是普遍的，很多问题的解决手段或直接或间接地都用到了栈和队列。
熟练掌握基本模型，而后将这些基本模型灵活运用于具体领域，是用程序设计解决实际问题的前提。