Python程式設計從0到1
（視訊教學版）
第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.7節）；這部分程式的核心是将實際問題（以繪圖和數學計算為主）轉換成代碼進行解決。解決這類問題需要具備基本的編碼知識和對問題的準确了解。本節的目的在于展示基本方法（如循環分支）的應用。
- “有技巧”的程式（1.8節）；這部分程式用到了程式設計中最基本的模型和算法，即狀态機、棧、隊列和搜尋等。這些技巧雖然基礎但不簡單。在初學階段了解甚至掌握這些技術帶來的好處是巨大的。
本階段的最後引入了算法複雜度的初步概念及标記方法（1.9節）。
第3階段：1.10～1.11節
本階段主要講述了異常處理機制（1.10節）。這是寫出Python完整代碼必不可少的知識。優秀的工程師能夠全面地考慮各種意外情況并加以處理，進而設計出健壯的系統。在實際工作中，異常處理的重要性足以比肩本章其他全部内容，然而在初學階段不便展開，故本部分篇幅短小，并設定為“節”歸入第1章。
此外，本階段還簡要介紹了PDB調試工具（1.11節）。
1.1 曆 史
在萊布尼茨①（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 表 達 式
人們天天都在做計算。在計算機科學中，“計算”一詞的概念更為寬泛，用計算機做的一切事情都可以稱為計算。表達式是計算的基本概念之一。當兒童學習1+2=3時，就是在學習表達式的計算。1和2是運算數（operand），加号是運算符（operator），計算結果3被稱為表達式的值。得到結果的過程稱為表達式的求值過程。在正式開始動手編碼之前，我們先來了解一些表達式的基本概念。
1.2.1 運算數
運算數可以是1或2.5這樣的數，也可以是"abc"這樣的字元串。這種直接就能表示某個值的标記被稱為字面值（literal）。運算數也可以是某種标記所代表的對象，比如a、s這樣的辨別符（identifier）。在使用辨別符之前，要将其和某個對象進行關聯，比如指派操作a=5, s="abc"。
1.2.2 運算符
狹義的運算符是指程式設計語言定義的一系列特殊符号，從四則數學運算，到各種語言常見的索引運算符[ ]，以及部分語言特有的lambda運算符等。廣義運算符則包含進行各種操作的函數，如求最大值的函數max()，或者切分字元串的函數split()。運算符和運算數組成表達式，如1+2。
如果和運算符配合使用的運算數是兩個，就稱該運算符是二進制（binary）運算符，其運算是二進制運算。其他運算數個數的運算符也有類似稱呼，如一進制和三元等。
1.2.3 表達式的風格
運算符和運算數組成表達式。運算符和運算數的出現次序會影響表達式乃至程式設計語言的風格。
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節的示例中使用了字尾表達式。
1.2.4 表達式的嵌套
複雜的表達式可以由簡單表達式和運算符組合而成。12是表達式，它可以進一步和乘法運算符組合成123，或者和加法運算符組合成12+3。乘法運算的優先級較高。括号用來改變運算符的運算次序1(2+3)。表達式自左向右計算（這對減法和除法是至關重要的），這稱為運算符的結合性。
這是國小生就明白的事情，但計算機科學家們感興趣的是如何嚴謹地描述上述說明。在計算機科學中，往往使用如下範式來準确定義表達式（為了友善了解，這裡隻讨論由數字、加号、乘号和括号組成的四則運算表達式）。
初級表達式 是 數字 或 (四則表達式)①
乘除表達式 是 初級表達式 或
乘除表達式 * 初級表達式
乘除表達式 / 初級表達式
四則表達式 是 乘除表達式 或
乘除表達式 + 四則表達式
乘除表達式 - 四則表達式 如果讀者之前從未接觸過這種形式的定義，那着實要動一番腦筋才能了解。請讀者仔細體會上述描述，該描述明确、完整地包含了關于四則運算表達式各個方面的說明。6
上述描述表達式的一般形式被稱為巴克斯範式（Backus Normal Form），這是計算機科學中用來描述文法的基本模型。精确地将問題描述成某種模型，對解決問題意義重大。比如描述成巴克斯範式的文法解析問題，可以很容易地使用bison這類文法解析器來處理。②
在上述定義中充滿了用事物自身定義自身的方法，這種方法稱為遞歸。遞歸是一種非常重要的程式設計方法。本書将在2.4節對其進行詳細介紹。
1.2.5 資料類型
運算符的行為取決于運算數的類型。例如，字元串類型也可以做加法和乘法：
"123" + "456" 的值是 "123456"
"123" * 2 的值是 "123123"
這兩種字元串運算分别是拼接和重複。同樣的運算符有不同的行為，這稱為運算符重載（overloading）。在程式設計實踐中，程式員經常受益于這種便利。本書将在2.5.5節講述如何針對自定義類型重載運算符。
1.2.6 副作用
在表達式的求值過程中，對狀态的改變稱為表達式的副作用。Python中内建的各種運算符（此處是狹義的含義，如加、減、乘、除、比較等運算符，并不包含使用者自定義的運算符或函數）是沒有副作用的，但各種函數調用時常帶有副作用（比如各種輸入、輸出函數）。在使用帶有副作用的表達式建構複雜表達式時要格外留意，因為這可能帶來程式員容易忽視的行為。例如：
if expA and expB :
... 這條語句用來測試表達式A和B都為真的條件。expA and expB的計算具有短路性質，即如果A為假，則整個表達式已然能夠判斷為假，表達式B不會被求值。如果表達式B包含函數調用，則意味着該函數不一定被調用。
不過總體說來，Python中副作用帶來的麻煩并不多。程式員隻要不在複雜表達式中嵌套帶有副作用的函數即可避免這些容易混淆的情形。這種編碼風格也能很容易遵守。①7
1.2.7 小結
為什麼要在一開始讨論1+1=2這些簡單的内容，而非動手寫一些立刻就能運作的代碼呢？原因在于，清晰的核心概念是持續學習的保證。看似紛繁的知識其實都有着清晰的圖景，司空見慣的簡單背後隐藏着本質的原理。在程式設計語言中，稱得上核心的概念極為有限。學習的過程就是對這些核心概念的認識不斷提高的過程。
表達式種類繁多，工程師要花費相當多的精力在處理和設計各種表達式上。清晰地了解表達式的本質特性，能讓學習者迅速抓住語言特點，進而順利地掌握用這門語言進行程式設計的方法。
1.3 運 行 程 序
讓程式運作起來是動手實踐的起點②。運作Python程式的基本方式有兩種：互動執行模式和腳本執行模式。本節将展示這兩種方式，以及其他初學者的入門技能。
【學習目标】
- 掌握通過互動式界面執行指令的方法；
- 掌握通過指令行運作Python腳本的方法；
- 了解通過主動出錯，進而熟悉新語言執行環境的方法；
- 掌握Python程式的注釋方法；
- 嘗試閱讀簡單程式。
1.3.1 互動執行模式
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節講述。
1.3.2 查閱幫助文檔
新手往往喜歡用搜尋引擎尋求幫助，專家們則首選官方文檔①。最便捷的文檔是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.3.3 執行Python程式腳本
互動式環境多用來驗證小代碼片段，但稍微長的程式就需要儲存為檔案來執行。這既能夠避免每次重新輸入程式，也能以子產品形式組織代碼以供其他程式調用。編輯代碼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()) # 列印随機數 【代碼說明】②
- Python靠縮進來标記語句塊。這意味着程式員必須認真對待縮進。Python建議使用4個空格進行縮進。這也就是說，讀者在抄寫上面的程式時，print一行開頭要敲4個空格。
- 要特别注意for行尾的冒号是不可少的，它用于引出後續的語句塊。
- Python的注釋以#開始，Python沒有專門的跨行注釋文法③。注釋不影響程式的功能，但對于程式的維護是非常重要的。能夠寫出清晰、簡潔的注釋是優秀程式員的重要品質；
- 程式中出現非ASCII編碼（如中文注釋）時，就需要在代碼頭部指定UTF-8字元集。
如上述代碼1.1中的第2行所示：
-- coding: utf-8 --
- 腳本以#!開頭的第1行為shell①指明Python解釋器的位置。像單個程式一樣執行腳本時，shell會使用首行指定的解釋器。
【程式運作結果】
執行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是函數名。
1.3.4 辨別符和關鍵字
在計算機科學中，術語“辨別符”（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生機勃勃的表現。
1.3.5 運作環境的錯誤提示
初學者一般會花費很多時間在修改文法錯誤或其他簡單錯誤上。有經驗的工程師在進入新的程式設計領域時也是如此。
初學者首先要能夠平和地對待這一過程。在簡單錯誤上消耗的時間因人而異，這是學習程式設計的必經階段。從筆者的教學經驗來看，也的确存在一些加速通過這個階段的方法。最直接的方法就是主動觸發錯誤進而去了解它。
了解錯誤提示資訊含義很有價值，不但能夠加快編碼進度，還能了解程式設計環境的“思考方式”。有意識地輸入一些錯誤代碼，觀察解釋器給出的錯誤提示，是非常有用的學習技巧。對于英文水準薄弱的學習者而言，這顯得尤為有用。例如，當名字引用發生錯誤時，解釋器會給出如下提示：
>>> 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 初學者經過上述刻意的“試錯練習”後，就能夠比較輕松地掌握該類錯誤提示資訊的含義了。當初學者看到該類錯誤涉及函數調用時就會意識到：函數調用拼寫是否有誤、是否未導入子產品、函數定義的函數名是否寫錯。
不論是學習新語言，還是學習新架構，都有一個熟悉錯誤提示資訊的過程。逐個講解錯誤提示資訊沒有太大的意義，因為這需要初學者自行練習、了解。這裡的示例是向初學者介紹加快這個過程的方法。即便有經驗的工程師，在新的軟體開發環境中全面展開工作前，通過這種“故意出錯”的方式熟悉一下錯誤提示資訊的風格也是不無裨益的。
1.3.6 示例：歐幾裡得算法
在開始全面講解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行定義了有兩個參數的函數gcd()。函數是一段可以被反複調用的代碼。gcd()函數計算參數a和b的最大公約數，并通過第4行的return語句傳回計算結果。
- 第2行while語句，請讀者注意這行代碼，用了4個空格進行縮進，表示這條語句屬于gcd()函數（代碼1.2中沒有縮進的最後一行print()語句就不屬于gcd()函數）。while關鍵字後面跟随的條件判斷"b!=0"表示當這個條件為真時就反複執行之後的第3行語句。
- 第2行語句是指派語句，将b的值和a除以b的餘數，再次指派給a和b。這行語句每執行一次，就完成了一次“輾轉相除”。這行語句前有8個空格，表明這行語句受前一條while語句控制，直至while之後的"b!=0"條件不為真才停止執行。換言之，就是當某次餘數為0時停止執行。這實際上就是圖1.2描述的歐幾裡得算法。
- 第4行語句是傳回語句，将最後剩下的公約數a傳回。
- 最後使用print語句将gcd(252, 105)的傳回值列印出來。
圖1.3 gcd()函數圖示
【程式運作結果】
$ ./gcd.py
21 可以使用Python 3解釋器的-i 指令行選項，在啟動解釋器互動界面時加載執行程式文本。加載執行程式文本後，可以繼續輸入代碼以執行：
$ python3 -i gcd.py
21
>>> gcd(12, 4)
4
>>> gcd(36, 54)
18 1.3.7 小結
學習程式設計語言需要動手實踐，是以第一步就是搭建能夠運作程式的環境。從作業系統環境和版本的選擇上，筆者建議的最佳選擇是采用某個Linux的最新穩定發行版及配套的Python 3運作環境。
和有些語言（如C語言）持續多年的穩定性不同，Python仍然在快速進化中，在開始學習時就養成時刻查閱文檔的習慣是必要的。
1.4 内建類型、指派和引用
内建類型是語言自身定義的系列類型，往往包括數值、字元串和容器等。這是程式運作的基本要素之一。本節将向讀者介紹Python内建類型中最基本的部分：數值、字元串和容器。在本節的最後還将介紹Python的指派操作、引用和del操作的行為。
- 了解Python的字面值類型；
- 了解Python的内建容器類型；
- 了解内建類型的運算；
- 了解指派語句和引用的概念。
程式設計是工程而不是數學。這意味着無法像講授數學課那樣，先引出一些基本公理，然後層層推導出整個知識體系。在程式設計中，往往最基本的概念也會涉及語言的方方面面，比如本節将要介紹的基本類型。如果一開始就全面地講解Python的各種基本類型及其操作，不但在篇幅上不允許，而且初學者也不具備相關的背景知識。但如果不引入這些概念，便會寸步難行，因為即便是最簡單的代碼，也要用到基本類型和表達式。
這個沖突将貫穿讀者學習和實踐程式設計的始終。本書的觀點是：既然無法講述全部細節，就将精力集中在必須要了解的内容上。
1.4.1 字面值
“字面值”（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）辨析字元串字面值、字元串類型與字元串對象。
1.4.2 構造方法
内建類型的構造方法用來得到這些類型的對象。整數類型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) 【代碼說明】①
- argv[1:]為全部的指令行參數，參見1.4.4節與1.6.5節；
- sum += int(arg)相當于sum=sum+int(arg)；
- int(arg)利用整數類型構造方法通過字元串得到整數。
$ ./sum.py 1 2 3 6 $ ./sum.py 1 4 7 10 22
1.4.3 容器類型
術語“容器”是指用來存儲對象的某種結構。程式員可以使用容器，友善地進行對象的存儲和查找等操作。不同的容器類型适用于不同的操作場景。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章講述。到那時讀者已具備閱讀文檔之基本能力，以及一定的程式分析和設計能力，當收事半功倍之效。
1.4.4 索引和切片
截至目前，本書介紹過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節講述。
1.4.5 左值、指派和引用
初學者可以選擇性跳過本節的内容。①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為“變量”時，強調a指向内容不确定或可變的事實；
- 當提及“a的值”時，所指的是a指向對象的值；
- 當提及“引用a”時，往往強調的是a所指向的對象；
- 當提及“對a指派”時，往往指讓a指向另外的對象；
- 有時由于C語言習慣或強調名詞屬性時，也稱a為“指針”（pointer）。
對名字重新指派會使名字引用新的對象。以整型變量為例，重新指派意味着另辟空間建構新對象，再讓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
- a = 'hello world'，a被首先關聯至字元串字面值；
- 定義函數foo的語句将函數對象關聯至名字foo；
- a = foo，将a關聯至foo所指向的函數對象；
- foo = 10，将foo關聯至數字字面值10，a仍然指向函數。
3．None關鍵字
Python提供了None關鍵字用以設立“空引用”。執行a = None後，a就不再指向任何“具體的”對象②了。在程式設計語言中，“空引用”一般有如下3種用途：22
- 在參數中使用None一般表示預設行為；
- 在函數傳回值中使用None一般表示出錯或未找到；
-
表示序列的終點。
例如：
- 字元串的分隔方法str.split()可以用sep參數指定分隔字元集，預設的sep參數為None，表示使用空白字元分隔；
- 字典的get方法用以根據鍵值擷取對應的對象a = dict.get(key)，如果沒有該鍵值，則傳回None；
- 在本書3.2節講述連結清單時，使用None表示連結清單終點。
帶你讀《Python程式設計從0到1》之一：基 礎第1章 基 礎
圖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) 1.4.6 del操作
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] 1.4.7 小結
現代語言的内建類型非常豐富。本節介紹了Python的數值和字元串類型，以及清單、元組、集合和字典4種容器類型。Python設計者在内建類型上構造的操作能夠反映這門語言的核心程式設計手段和設計思路。對于初學程式設計的讀者來說，了解這些知識對于後面的學習是必要的。對于有經驗的學習者來說，将這些特性與自己熟悉的其他語言進行比對思考是很有價值的。
本節還重點講述了Python的引用及相關特性。Python中的對象都是通過引用通路的。引用沒有類型，可以指向各種對象。指派操作就是讓引用指向新的對象，而del操作則是對引用的删除。
通過本節的學習，讀者應當初步了解在Python中，“資料”是如何存儲和表示的。這是接下來用各種流程控制手段對資料進行操作、寫出複雜程式的基礎。
1.5 流程控制結構
在解決實際問題時，需要根據情況做出判斷，執行不同的指令或循環執行某個指令序列。程式設計語言通過流程控制指令實作該功能。本節将介紹Python的邏輯表達式、分支控制語句if、while和for。在本節的最後将向讀者講述建立簡單函數的方法。
- 掌握Python的邏輯表達式；
- 掌握Python的循環和分支控制語句；
- 掌握Python建立簡單函數的方法。
1.5.1 if分支語句
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 - 程式使用input()函數從終端讀入資料，讀入的資料是字元串形式，需使用int構造方法将其轉換為整數；
- assert語句的作用是測試代碼執行的前提條件，如果不成立就會抛出異常，在預設狀況下會退出程式；
- 在每一個if-elif分支後是用于測試score變量的邏輯表達式，其中>=運算符用于測試大于等于關系是否成立。
$ ./score.py
98 ~ 鍵盤輸入
Grade A ~ 程式輸出 分支控制語句的執行依賴于if-elif關鍵字後的表達式求值結果。下一節（1.5.2節）将介紹表達式的“真假”判斷，以及如何通過邏輯運算将其組成更複雜的表達式。
幾乎所有語言都有if-else結構，但略有不同。查詢你聽說過的其他程式設計語言①，找到其中的if-else結構和Python的結構進行對比。25
1.5.2 布爾運算
布爾運算是對“真”“假”二值邏輯的運算。Python中有專門的布爾類型（bool），其值為True或False。布爾類型可以通過布爾運算組成更複雜的邏輯表達式。首先要關心的是表達式的值為“真”的情形：
- 算術比較運算符（如>、>=、==、<=、<、!=）關系成立時；
- in運算符測試的包含關系成立時；②
- is運算符測試的引用相同關系成立時；
- 非布爾類型（值為整數類型、字元串或其他對象類型）的表達式在需要時（單獨用作條件判斷或參與布爾運算時），值可以被隐式轉換為bool類型，非0值和非空對象的布爾值為真，否則為假。
注意：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.5.3 while循環
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 - 變量a和b賦初值1；
- 循環的執行條件是a<50；
- 循環中不斷更新a和b的值以存儲計算出來的最新數列項；
- 循環中将a的值列印出來；
- end=' '是print的關鍵字參數（參見2.1.8節），使print以空格作為輸出結尾。
如圖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語句流程圖
- stdin.readline()從标準輸入（參見1.6.4節）讀入一行文本，作為字元串類型（str）傳回；
- str類型的strip()方法用以去掉行尾的換行符；
- split()方法用以将字元串按空格分隔後作為清單傳回。
$ ./words.py
hello world ~ 使用者輸入
words 2
I love Python ~ 使用者輸入
words 3
quit ~ 使用者輸入
$ 1.5.4 for循環
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) )
+
+ +
+ + +
+ + + +
+ + + + + for循環也支援else語句塊，完整文法如圖1.28所示。
圖1.28 for循環的完整文法
當循環正常結束時，執行else之後的語句塊。在for循環裡也可以使用break和continue，行為和while中類似。以break結束循環時，else語句塊不會執行。其流程如圖1.29所示。
圖1.29 for循環的完整文法流程
（1）查閱文檔，找到可疊代對象的說明。
（2）查閱其他語言的for循環文法，比較與Python的異同。
1.5.5 條件表達式
條件表達式也使用if-else關鍵字，是以在這裡一并介紹。條件表達式文法如下：
x if C else y
當條件C為真時，表達式的值為x，否則為y。恰當地使用條件表達式，可以讓代碼很簡潔。如果需要根據不同的條件，計算不同的值，就可以考慮使用條件表達式。
?注意：條件表達式可以用在适用表達式的地方，如if-while的條件，或者給某個左值指派。前一節所述的if語句不是表達式，不能用于類似上下文的地方。
1.5.6 定義簡單函數
到目前為止，本書示例已經調用過很多内建函數，如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] 1.5.7 小結
本節重點講述了Python的3種分支控制結構：if-else分支、while循環和for循環。其中，前兩個比較簡單，直接用表達式的求值結果作為程式執行流程的控制條件；for循環則是比較進階的抽象，用以周遊可疊代對象，如range對象及清單等各種容器。
本節還簡單講述了函數的定義文法。函數是程式設計的重要手段，将重複的代碼封裝為函數，可以讓程式變得簡潔、清晰。
分支控制和函數是随時随地要用到的程式設計方法，本書将在1.7節通過一組示例，讓讀者進一步熟悉這些方法。
1.6 輸入/輸出
程式需要從外部獲得資訊并将計算結果傳遞出去。本節将介紹最常用的3種與程式傳遞資訊的方式：标準I/O、指令行參數和環境變量。
- 了解I/O重定向的方法；
- 掌握用Python進行标準I/O讀寫的方法；
- 了解傳遞指令行參數的方法；
- 掌握用Python讀取指令行參數；
- 掌握Linux設定環境變量的方法；
- 掌握用Python讀取環境變量的方法。
1.6.1 标準輸入/輸出（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.6.2 重定向标準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重定向是如何實作的。
1.6.3 用管道行串接I/O
基于标準I/O工作的程式可以很容易通過管道行（pipeline）進行串接。這是将程式組裝起來完成更複雜任務的便捷方法。例如，要對如下文本資料（學号 姓名 成績）data.txt：
01|張三|95
02|李四|99
03|王五|80 進行兩項處理：
- 将用于分隔的豎線替換成逗号；
-
按成績排序。
UNIX/Linux的終端環境提供的内建程式tr和sort可以分别完成這兩個任務。tr指令可以根據指定的替換表進行字元替換：
$ 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
思考管道行是如何實作的。
1.6.4 标準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():
.... 1.6.5 指令行參數
指令行參數是在程式啟動時向程式傳遞的參數，用來指定源檔案、目标檔案或控制程式的具體行為。比如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子產品的知識。
1.6.6 環境變量
環境變量是作業系統在程式運作時指定的一組環境參數。程式可以讀取這些參數的值，并據此改變自身行為。在UNIX/Linux終端中輸入env指令，可以看到系統設定的環境變量。由于環境變量很多，這裡隻列出以下幾個：
$ env
......
TMPDIR=/var/folders/j_/d0ry5sq101144mmw2nlc8w8m0000gn/T/
......
USER=zhangdi
......
LANG=zh_CN.UTF-8
...... - TMPDIR用來訓示程式建立臨時檔案的位置；
- USER是目前登入的使用者名；
- LANG指明了目前的語言環境。
程式可以通過導入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.6.7 格式化字元串
截至目前，本書的程式都是使用拼接生成包含某種可變部分的字元串，不但功能有限，而且可讀性差。格式化字元串是用模闆标記生成字元串的方法，在許多語言中都有實作。學習格式化字元串要掌握兩個關鍵點，一是在字元串模闆内指定可變部分來源的文法，二是控制顯示格式的文法。
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之類能夠精确控制格式的标記語言另行實作。各種格式标記在日常程式設計中使用頻率很低，即便記住也可能在一段時間後遺忘。富有經驗的工程師在遇到實際的格式化需求時，通常是查閱文檔或上網搜尋相關的内容。
1.6.8 小結
本節講述了程式與外部環境傳遞資訊的基本方法。在有宿主作業系統的環境下，最基本的資訊傳遞方式有I/O流、指令行參數和環境變量。I/O流，尤其是标準I/O流，通常用來進行資料傳輸。指令行參數通常用來對程式行為進行精确控制。環境變量用以向程式提供運作環境的配置資訊。利用I/O重定向或其他程序控制手段，可以很容易地将基于這些通信方式的程式內建到更大的軟體體系中。
1.7 簡 單 練 習
本節中的部分問題涉及微積分（1.7.5節）和數值計算（1.7.6節）的初步知識。如果讀者不了解這些知識，可以跳過相關小節，這并不會影響閱讀本書後面的章節。
本節是為初學程式設計的讀者準備的内容，目的在于讓讀者通過一系列示例掌握各種分支控制結構。讀者了解文法後，需要通過練習才能獲得實在的程式設計能力。出于直覺、趣味性考慮，本節中的部分例子使用了turtle繪圖庫。相關示例會引導讀者逐漸接觸這個繪圖庫。
- 熟練掌握程式設計的基礎手段；
- 能夠将實際問題轉換為程式代碼實作；
- 了解程式設計在本節所涉及學科中的應用；
- 了解turtle子產品的基本使用方法。
注意：在學習本節内容時，上策是先閱讀問題描述然後嘗試自己動手程式設計解決問題，中策是先閱讀代碼獲得思路然後動手獨立寫出，下策是抄寫代碼了解後再行獨立寫出。對于有一點程式設計基礎的讀者，建議采用上策或中策。對于完全沒有程式設計基礎的讀者來說，采用先抄寫的方法也許是必經之路。
1.7.1 示例：列印金字塔圖形
問題描述：編寫函數，列印如下金字塔圖形。該函數接收一個參數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])) - if__name__== "__main__"這行之後的代碼在程式獨立運作時被執行，在檔案以子產品導入時不執行。這是Python為函數編寫測試運作代碼的常見方式。讀者可以參考閱2.2.3節了解相關知識。
$ ./pyramid.py 7
*
* * *
* * * * *
* * * * * * *
* * * * * * * * *
* * * * * * * * * * *
* * * * * * * * * * * * * （1）使用while循環完成本例。
（2）思考如何不使用循環完成本例。①
1.7.2 示例：3X+1問題
問題描述：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()函數傳回猜想描述的計算執行步數；
- 測試代碼根據指令行參數驗證前若幹個正整數。
$ ./threex.py 10
1: 0
2: 1
3: 7
4: 2
5: 5
6: 8
7: 16
8: 3
9: 19
10: 6
【思考和擴充練習】
上述示例如果猜想不正确，程式能正常結束嗎？如何修改程式以處理這種情況？
1.7.3 示例：繪制正多邊形
問題描述：編寫程式繪制正多邊形。程式從指令行接收正多邊形的邊數及外接圓直徑。
Python标準庫的turtle子產品①提供了繪圖功能。它的工作原理是控制一個繪圖筆在平面上移動以繪制曲線。程式中反複使用如下兩條指令來繪制圖形：
- forward(size)：繪制長度為size的線段；
- left(angle)：将繪圖筆前進方向左轉angle度。
繪制正多邊形的實作，如代碼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所示的圖形。
1.7.4 示例：繪制函數曲線
問題描述：在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() - drawline()函數用于繪制直線。
- move()函數用于移動光标而不畫線。
- turtle庫的繪圖筆處于“放下”狀态時，移動繪圖筆會畫出筆迹。如果希望移動繪圖筆而不畫出筆迹，就需要先“擡起”繪圖筆再移動。這就需要反複地使用penup()和pendown()方法。為了簡潔，本例将畫直線和移動繪圖筆的組合動作設計為函數drawline()和move()。用pen()方法儲存繪圖筆的狀态，做完操作後，再用pen()方法恢複繪圖筆狀态。
- 在這裡使用range(1,400)控制循環，循環變量會取遍1～399作為自變量x計算函數值y。
$ ./sin.py 會出現畫布視窗和如圖1.38所示繪制的圖形。
（1）思考如何為坐标軸加上刻度和箭頭，編寫程式實作之。
（2）思考如何編寫通用的程式，用以繪制各種數學函數。
1.7.5 示例：蒙特卡洛方法
問題描述：編寫程式，模拟蒙特卡洛方法求如圖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。
1.7.6 示例：埃特金疊代法求方程的根
數值計算是計算機的重要應用領域。對于工科類學生而言，數值計算顯得尤為重要。
問題描述：用簡單疊代法求方程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）查閱網際網路，研究還有哪些求解非線性方程的疊代方法，程式設計實作并與埃特金方法比較。
1.7.7 小結
本節介紹的示例和習題涉及多個領域。讀者（尤其是大學低年級的學生或中學生）應當積極在其他學科的學習中充分使用Python。程式設計能力對數學、科學和工程學的學習有很大幫助。
1.8 程式執行模型
在上一節中，本書向讀者展示了程式設計的一些具體示例。通過這些示例，讀者應當已經了解到編寫代碼的初步方法。但這些示例比較初級。這種初級在于，從問題描述本身出發就容易設計并編寫程式。比如埃特金疊代法，雖然其原理涉及較複雜的數學，但從程式設計角度來說，隻需要按照算法步驟描述，就可輕易寫出程式。
本書将向讀者展示程式設計的核心思考方法。使用這些方法，可以讓工程師在面臨具體的局部問題時能夠設計出恰當的程式。本節提出的問題種類分為以下3個層次：
- 無狀态程式設計；
- 有狀态程式設計；
- 利用順序存儲結構進行程式設計。
這和在本書1.1節中提到的基本模型“圖靈機”是相吻合的。圖靈機模型的核心思想正是由狀态機配合線性存儲器完成各種各樣的計算任務。為了突出設計程式的本質方法，本節的前幾個示例将程式設計手段限制于最簡單的輸入和輸出、控制結構，以及簡單的字元和字元串處理方面。
輸入和輸出、指派、運算、條件判斷、循環和分支、順序存儲結構，學會了這些，就足以寫出解決各種問題的程式。基本上各種程式設計語言都支援這些特性。本節将帶領讀者使用這些核心程式設計手段，解決各種程式設計問題。核心能力一旦建立，就會自然得以推而廣之。
- 掌握使用狀态機進行程式設計的方法；
- 了解棧和隊列在程式設計中的應用。
1.8.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()函數将字元輸出。這段程式隻是簡單地将輸入複制到輸出，每次一個字元。接下來的例子将根據具體問題的需求在循環裡對資料進行處理。
1.8.2 無狀态程式
最簡單的程式是無狀态的，即程式在計算過程中不需要“記住”什麼。這類程式隻需根據輸入進行分類讨論即可，最常使用的就是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()都能生成轉換表，二者有何差別？
1.8.3 有狀态程式
前一節所示程式的特點是輸出僅與目前輸入有關：當輸入字母A時就輸出數字2，當輸入M時就輸出數字6。程式的核心就是循環加上查找邏輯，不需要“記住什麼”。但一般的場景是：輸出不僅取決于輸入，還取決于“狀态”。
當在鍵盤上按Enter鍵時，計算機顯然不是每次都給出一樣的結果。比如，在字處理軟體的編輯框中按Enter鍵會換行，在第一人稱的射擊遊戲中按Enter鍵則往往是開槍。這就是狀态對行為的影響。
這類程式歸納起來具有如下行為：
- 接收輸入，産生輸出；
- 擁有設計好的狀态集合；
- 使用狀态變量用以記錄狀态，在執行過程中，狀态不斷變化；
- 擁有設計好的查找邏輯；
- 使用查找邏輯，根據“目前狀态”和“目前輸入”決定“下一個狀态”和“輸出”。
具有狀态記憶特性的程式執行過程如圖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中，圓圈表示兩個狀态：
- 狀态0：當狀态為0時，表示上一個字元不是空格；
-
狀态1：當狀态為1時，表示上一個字元是空格。
帶箭頭的曲線表示狀态的轉換，各條曲線的含義分别是：
- 0->1：當狀态為0時，收到空格，此時應當把這第一個空格列印出來。同時由于收到了空格，程式需要記住這件事，狀态發生變化，變為狀态1。
- 1->1：當狀态為1時，收到空格，表明正處于連續空格中，什麼也不列印。
- 1->0：當狀态為1時，收到字元，說明結束了連續空格狀态，輸出該字元，并且轉換為0狀态。
- 0->0：當狀态為0時，收到字元，說明這是正常的字元序列，輸出該字元，并且留在1狀态。
也可以用查找表結構寫出上述模型，如圖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}') # 不會執行至此 - 最外層的分支和狀态相對應。
- 内層分支和狀态的轉移曲線相對應。
- 程式寫對的情況下，最後的else分支永遠不會執行。如果執行到這裡，說明代碼因為疏忽寫錯了，抛出異常，列印s的值以輔助排錯。
- 上述代碼特意為了和狀态轉換圖對應，加入了一些不需要的語句，如狀态向自身跳轉時對s的指派語句，以及不需要輸出時列印空字元串的語句。也許有的讀者會想用條件表達式或者将一些行為相同的print合并放到分支外面，但在接下來的擴充中會看到，規整的結構帶來的好處遠勝于在編碼初期節省一兩行文本。
将問題描述中的示例儲存至文本檔案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='') - 正規表達式r' +'的含義是“一個或多個空格”；
- re.sub(r' +', ' ', s)的含義是将字元串s（參數3）中的“一個或多個空格”模式（參數1），替換為“單個空格”（參數2）；
- 正規表達式引擎的工作原理也是根據待識别的模式生成狀态機，然後用狀态機處理字元串。
擴充問題：更加複雜的狀态。
前述例子使用了最簡單的狀态機（之是以最簡單，是因為隻有兩個狀态），現在稍微拓展一下問題：将雙引号圍繞起來的文本看做字元串，保留其中的空格數量不變，僅僅縮減雙引号外的空格。為了簡化問題，假設雙引号總是成對出現，并且不考慮在雙引号中還有轉義雙引号的情形。
輸入示例：
" 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.8.4 線性存儲器
有時候，僅僅記住有限個确定狀态是不夠的，這時就需要通過某種資料結構來存儲數量不确定的資料。基本的資料結構是線性結構，這也最符合存儲器的實體結構，如圖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.8.5 使用棧設計程式
為了示範棧這種結構在程式設計中的應用，請看如下問題：
注意：本節的示例将在異常處理（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 * - /，運算過程如下：
- 最後出現的兩個運算數3和2與最先出現的乘号進行，3*2運算得到6；
- 這個結果連同倒數第3位出現的8和第2個出現的減号進行8-6運算得到2；
- 最先出現的4最後進行計算，4/2得到結果2。
在這個過程中需要一個後進先出的存儲結構來存儲掃描到的操作數，這就是棧。
棧是一種邏輯結構，任何實作了“後進先出（LIFO：Last-in，First-out）”的結構都可以被稱為棧。在本例中以Python的清單實作棧，append()方法在清單的尾部添加資料（入棧），pop()方法在清單的尾部讀取資料并移除（出棧）。使用棧這種抽象資料類型，計算逆波蘭表達式的方法可以描述如下：
- 從左向右掃描表達式；
- 如果遇到操作數，将其入棧；
- 如果遇到運算符，将棧頂的兩個數出棧并運算，将結果再次入棧；①39
- 掃描完成後，棧頂元素就是計算結果。
這個描述很抽象，但了解抽象的算法描述也是程式員必備的能力之一。常用的方法是構造一個例子，根據算法的描述，按部就班求解一遍。以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 逆波蘭表達式算法中棧的變化
- operator子產品包含了Python的各種運算符的函數形式；
- op_dict是字典，用以将字元串辨別的運算轉換為真正的運算函數；
- 字元串的split()方法，用以将字元串按空白字元切割為單詞後傳回清單。①
>>> 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節揭示遞歸和棧的關系。
1.8.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 蜂窩狀地圖
1.8.7 小結
本節講述了程式設計的基本模型（這些基本模型并不簡單）：狀态機和線性存儲器模型，這是圖靈計算模型的核心。沒有現成工具直接解決問題時，工程師可以回退到基本模型建構解決方案。
線上性存儲模型部分，本節介紹了棧和隊列這兩種資料結構。這兩種結構的應用是普遍的，很多問題的解決手段或直接或間接地都用到了棧和隊列。
熟練掌握基本模型，而後将這些基本模型靈活運用于具體領域，是用程式設計解決實際問題的前提。