# AP325-Python 第0章 教材說明與預備知識
## 教材說明

這是一份針對程式上機考試與競賽的教材，特別是APCS實作考試，325是3-to-5的意思，這份教材主要目標是協助已經具有APCS實作三級分程度的人能夠進步到5級分。AP325先有C\++版本，此為Python版本。
APCS實作考試每次出4題，每題100分，三級分是150 ~ 249分，四級分250 ~ 349分，而350分以上是五級分。由於題目的難度排列幾乎都是從簡單到難，因此，三級分程度大概是會做前兩題，而要達到五級分大概是最多只能錯半題，所以可以簡單的說，要達到四五級就是要答對第三第四題。
根據過去的考題以及官網公告的成績說明，前兩題只需要基本指令的運用，包括：輸入輸出、運算、判斷式、迴圈、以及簡單的陣列運用，而第三與第四題則涉及常見的資料結構與演算法。以往程式設計的課程大多只在大學，以一般大學程式設計教科書以及大學資訊科系的課程來看，第三四題所需要的技術大概包含程式設計課的後半段以及資料結構與演算法的一部份，這就造成學習者在尋找教材時的困難，因為要把資料結構與演算法的教科書內容都學完要花很多時間。另外一方面，APCS實作考試的形式與題型與程式競賽相似，程式競賽雖然網路上可以找到很多教材與資源，但是範圍太廣而且難度太深，而且多半是以英文撰寫的，對三級分的程式初學者來說，很難自己裁剪。
這份教材就是以具有APCS實作題三級分的人為對象，來講解說明四五級分所需要的解題技術與技巧，涵蓋基礎的資料結構與演算法，它適合想要在APCS實作考試拿到好成績的人，也適合競賽程式的初學者，以及對程式解題有興趣的人。如果你是剛開始學習程式，這份教材應該不適合，建議先找一本基礎程式設計的教科書或是教材，從頭開始一步一步紮實的學習與做練習。也可參考筆者為初學者寫的影片與講義[PythAPCS123 的YouTube撥放清單](https://youtube.com/playlist?list=PLpmg1QLbgMuSIDOgOcwf0Fbbn2ZDR7s-X) 以及 [PythAPCS123講義所在位置](https://drive.google.com/drive/folders/1mnVdO2LHq7e4vesn6pt_R0-S6YWtz4Q4?usp=sharing)。APCS相關教學資源也可以到臉書 [APCS實作題檢測社團](https://www.facebook.com/groups/359446638362710) 中尋找。

這份教材的內容與特色如下：
* 在這一章裡面，除了教材介紹外，也說明一些預備知識。下一章開始則依主題區分為：遞迴、排序與二分搜、佇列與堆疊、貪心演算法、分治、動態規劃、圖的走訪、以及樹狀圖。
* 對於每一個主題，除了介紹常用的技巧之外，著重在以例題與習題展現解題技巧。例題與習題除了包括該主題的一些經典題目，也涵蓋過去考題出現過的以及未來可能出現技巧。所有的例題與習題除了題目敘述的範例之外，都提供足夠強度的測試資料以方便學習者測試自己的程式。
* 部分章節與例題習題可能超過APCS考試的範圍，標示(\*)的部分讀者可自行略過。
* 所有的**例題與習題**都提供範例程式，有些例題會給多個不同的寫法，習題則是給予適當的提示。例題會在講義中加以說明，習題的範例程式可以在資料夾中找到。
* 例題與習題的編號方式為：P開頭為例題，Q開頭為習題。例題習題中標示(@@)符號者題目稍難，標示(\*)者可能超過APCS考試範圍，標示(APCS或其他出處者)表示該題出現於過去考試或比賽的類似題，如有標註subtask表示這一題的解法為當初考試的某一子題而非100分的解。
* 此為Python版本，教材中的範例程式都採用Python 3的版本，Python 2與Python 3有很大的差別，也不相容，講義中不會述及Python 2的寫法。Python有很多的工具，考慮本書讀者多為初學，所以範例程式以易懂易了解為主，不會為了程式精簡使用太多工具函數，目前APCS檢測環境Python 3為3.6版，因此，除了超出APCS範圍的題目之外，範例也不會採用後面版本的函數。以APCS的難度，雖然幾乎每一題都是不需要使用特殊的資料結構就可以寫得出來。
* 本教材是針對考試與競賽，所以範例程式的寫法是適合考場的寫法，而非發展軟體的好程式風格。因為時間壓力，考場的程式寫法有幾個不好的特性包括：比較簡短、變數名稱不具意義、濫用全域變數。但因為本教材是要寫給學習者看的，所以也不會刻意簡短而且會加上適當的註解，但是會教一些在考場可以偷懶的技巧。

本教材例題習題所附測資檔名的命名方式以下面的例子說明，例如檔名為
P_1_2_3.in
表示是例題 P_1_2的第3筆輸入測資，而
P_1_2_3.out
則是它對應的正確輸出結果。測資都是純文字檔，採unix格式，Unix格式與Windows文字檔的換行符號不同，但目前Win 10下的筆記本也可以開啟unix格式的文字檔。

### Python版與C\++版之差異

Python版的講義是單獨可讀的，並非依附在前C\++版本。但我希望兩者盡量一致，所以章節架構與算法知識內容都幾乎相同，但是在例題與習題上，由於語法與執行速度的限制以及C\++版本有些超過APCS程度的題目，所以無法讓兩個版本的題目完全相同，題目的部分採取以下原則：
* 題目的編號維持與C\++版本相同。
* 有些題目測資範圍縮小，執行時間限制設定在合理的數秒之內。
* 少部分題目需要特別的資料結構才能完成的，加以特別註明。

## 預備知識

這份教材假設讀者已經有了一點撰寫Python程式的基礎，包含變數的觀念、輸入與輸出、基本的運算、if分支指令、for 與while 迴圈、函數定義，這裡就不做介紹。在這一節中要提出一些預備知識，這些知識對於程式考試與比賽時撰寫程式有幫助。在本教材中的範例程式都採用與APCS相同的編譯環境。
接下來我們將說明以下主題。
* 基本輸入輸出
* 程式測試與測試資料
* 複雜度估算
* Python常用基本資料結構
* 需要留意的事

### 基本輸入輸出
APCS幾乎不會考特別的輸入與輸出，輸入只要會input()，輸出只要會print()就夠了，但必須會字串與list的使用。以下簡略回顧一下常用的輸入與輸出方式，不熟悉的讀者可以去查看PythAPCS 123講義。以下是常用輸入方式：

s = input() # input a line as a string
p = int(input()) # an integer in one line
p,q = map(int, input().split()) # two int in a line seperated by space
p,q = [int(x) for x in input().split()] # same as above
arr = [int(x) for x in input().split()] # several int in a line seperated by space, read into a list
# input an m*n 2d array
mat = []
for i in range(m):
    mat.append([int(x) for x in input().split()])

以下是常用輸出方式：

x = 5
print(x) # output a value in a line
y = 3
print(x,y) # output two values in a line, separated by (default) a space
p = [1,2,3,4]
print(*p) # output an array, elements separated by (default) a space, ended with \n
print(*p, sep=',') # elements separated by a comma
print(*p, sep='\n') # one element at a line

### 程式測試與測試資料
一個程式寫出來之後必須經過測試，除了語法沒有問題之外，更重要的是它可以計算出正確的答案而且可以在需求的執行時間之內完成計算。要測試程式就是拿資料餵給程式，看看程式的執行結果與時間是否符合要求，我們在考場寫出來的程式，繳交後也是以這個方式來進行測試。要測試程式第一步就必須有測資(測試資料)，產生適合的測資不是一件簡單的事，對某些題目來說根本就是比解答還要困難。

本教材的例題與習題都有提供測資，有些人可能未必了解測資的使用方法，所以以下做一些簡介。
所謂的測資是指一組輸入以及它對應的正確輸出答案。一支程式的標準行為就是讀入資料，進行計算，然後輸出結果。通常我們寫好一支程式在電腦上執行時，它就會等待輸入，此時我們可以鍵入測試用的輸入，等待它輸出結果，然後再比對答案。如果是在視窗環境下，我們也可以用複製貼上的方式將輸入資料拷貝過去，但這方法在資料量太大的時候就無法使用，另外有個缺點是這樣做無法量測程式的執行時間。

當我們在Python程式中下達輸入輸出指令時，系統是到預設的輸入與輸出裝置進行，其中stdin 是標準輸入裝置(standard in)，預設是鍵盤； stdout 是標準輸出裝置(standard out)，預設是螢幕。
這些裝置其實都可以改變的，這就是輸入輸出的重新導向(I/O redirection)，我們介紹兩個方法來做。
如果是Linux環境以命令列執行Python程式，則以下列方式可以將輸入輸出重導：

python3 test.py <test.in >test.out

其中 test<span/>.in 的意思就是將 test<span/>.in 這個檔案當作輸入裝置，也就是原本所有從鍵盤讀取的動作都會變成從test<span/>.in檔案中去讀取。而 \>test.out 則是將輸出重新導向至test<span/>.out檔案，原本會輸出至stdout的都會變成寫入檔案test.out中。輸入與輸出的重導可以只作其中任何一個，也可以兩者都做。

另外一個方法是在程式裡面下指令。以下是個範例：

import sys
sys.stdin = open("test.in",'r')
sys.stdout = open("test.out","w")

q = [int(x) for x in input().split()]
print(sum(q),max(q))

留意要import sys。第2行是開啟檔案將它指定給sys.stdin，如此一來，要在鍵盤讀的東西就會從檔案中讀取，第3行是改變stdout，將輸出改變到test.out檔案中。而open()中的”r”的意思是read模式。”w”的意思則是write模式。這兩個指令可以只執行其中一個，也可以兩個都做，也可以在一個程式裡面重導多次。
註：如果你在IDE裡面執行Python程式，而程式內有重導，值息完畢後可能需要自己重置，否則輸入輸出還是在重導的狀態。

在很多場合，輸出的內容很少，當我們要測試程式的時候，我們只要做輸入重導，然後看輸出的結果是否與測資的輸出內容一樣就可以了。在某些場合，輸出也很大，或者想輸出訊息除錯，那就可以利用輸出重導把輸出的內容寫到檔案。如果要將程式的輸出與測資的輸出檔做比較，在Linux下可以用diff來比較檔案內容。如果是Windows呢？可能要自己寫一支簡單的程式來比較兩個檔案。好在這份教材大部分的輸出都很小，用眼睛看就可以比較。

測試程式另一個問題是程式的執行時間是否符合題目要求。檢測考試與競賽的題目需要講求效率，每一題都有執行時限(time limit)，這是指對於每一筆測資，繳交的程式必須在此時限內完成計算。在Linux環境下我們可以用以下的指令來量測執行時間：

time python3 test.py <test.in

我們也可以在程式內呼叫系統時間函數來計算，以下是一個例子。

import sys
import time
sys.stdin = open("test.in",'r')
#sys.stdout = open("myout.out","w")
start = time.time()

q = [int(x) for x in input().split()]
total = 0
for i in range(100000):
    total += sum(q)
    
print(total)
print('running time = %s seconds' % (time.time() - start))
print('running time ='+ str(time.time() - start)+'seconds')

### 複雜度估算
要評估程式的執行效率，最準確的做法是量測時間，但是程式的執行時間牽涉的因素太多，而且不同資料量的時候會有不同表現，所以通常我們用複雜度來評估一支程式或演算法的效率。複雜度涉及一些定義與數學的計算，所以並不容易，這一節我們來講如何做簡易的複雜度估算，雖然只是講簡易的部分，但這些知識幾乎足以面對大部分常見的狀況。

**複雜度估算方式**
複雜度以$O(f(n))$來表示，念作big-O，也確實一定要大寫，小寫的o有不同的意義，其中習慣上以$n$來表示資料量，而$f(n)$是$n$的函數，複雜度代表的意義是「當資料量為$n$時，這個程式(演算法)的執行時間(執行指令數)不超過$f(n)$的某個常數倍」。對於常見的問題，資料量大小就是輸入的資料量，例如輸入整數的個數，或者輸入字串的長度，常見的複雜度有：$O(n)$、$O(n\log(n))$、$O(n^2)$、$O(2^n)$..等等。Big-O的計算與表示有下面幾個原則：
* 根據定義，不計算常數倍數，所以我們只說$O(n)$而不會說$O(3n)$或$O(5n)$。因為常數倍數不計，所以$\log(n)$不必指明底是2或10。在某些場合，有些人會故意用$O(5n)$之類的方式來表示用了5倍的時間，而非不瞭解常數不計。
* 兩個函數相加的Big-O等於比較大的函數。也就是說，若當$n$足夠大的時候$f(n)\ge c\cdot g(n)$，其中$c$為某常數，則$O(f(n)+g(n)) = O(f(n))$。如果一個程式分成兩段，一段的複雜度是$O(f(n))$，另外一段是$O(g(n))$，則整個程式的複雜度等於複雜度比較大的那一段。
* 如果某一段程式的複雜度是$O(f(n))$而這段程式執行了$g(n)$次，則複雜度為$O(f(n)\times g(n))$。最常見的是迴圈，若一個迴圈執行一次是$O(n\log n)$，而迴圈執行$n/2$次，那麼整個迴圈的時間複雜度是$O(n^2\log n)$。
* 程式的複雜度通常會因為輸入資料不同而改變，即使是相同的資料量，對某些資料需要的計算量少，對某些資料的計算量大。一般的複雜度指的是worst-case複雜度，也就是最難計算的資料所需的時間。

來看一些常見的例子。下面這段程式是一個迴圈跑$n$次，每一次作一個乘法與一個加法，所以複雜度是$O(2\times n)=O(n)$。事實上迴圈還需要歷遍range($n$)，所以應該是$n$的若干倍，反正都是$O(n)$。

for i in range(n):
    total += a[i]*i

下面這段程式在計算一個陣列中有多少的反序對，也就是有多少$(i,j)$滿足 $i<j$ 且 $a[i]>a[j]$。
程式有兩層迴圈，所以內層的if指令一共被執行$C(n,2)=n(n-1)/2$次，而if指令做一個比較與一個可能的加法，所以是$O(1)$，整個來看複雜度是
$O(n(n-1)/2)=O(n^2)$，因為只需要看最高項次。

for i in range(n):
    for j in range(i+1, n):
        if a[j] < a[i]: 
            inversion += 1
#

一般來說，迴圈的複雜度常常可以用$\Sigma$運算來計算，以上面的例子來說，其複雜度就是
$$
\begin{split}
\sum_{i=0}^{n-1} \sum_{j=i+1}^{n-1} 1 &= \sum_{i=0}^{n-1} (n-1-i) = \sum_{i=0}^{n-1}n -\sum_{i=0}^{n-1} 1 - \sum_{i=0}^{n-1}i \\
&= n^2 -n - n(n-1)/2 = O(n^2)
\end{split}
$$
接下來看一個線性搜尋的例子，在一個陣列中找到某個數字。在下面的程式中，迴圈執行的次數並不一定，如果運氣好可能第一個$a[0]$就是$x$，而運氣不好可能需要跑到$i=n$時才確定找不到。因為複雜度要以worst-case來看，所以複雜度是$O(n)$。

for i in range(n):
    if a[i] == x: break
    

程式的結構大致是迴圈或遞迴，迴圈的複雜度通常依照上面所說複雜度乘法的原則就可以計算，但遞迴複雜度也有一套分析的方法，但牽涉一些數學也比較困難。另外有的時候也需要使用均攤分析(amortized analysis)，在後面的章節中，我們會碰到一些例子，屆時會視需要說明。

**由資料量大小推估所需複雜度**

在解題時，題目會說明資料量的大小與執行時限(time limit)，我們可以根據這兩個數字來推估這一題需要的時間複雜度是多少。同樣的題目，複雜度的需求不同，就是不同的難度。在APCS與大部分高中的程式比賽中，通常採取IOI模式，也就是一個題目中會區分子題(或稱子任務)，最常見的子題區分方式就是資料量的大小不同。
對於簡單題(例如APCS的第一第二題)，通常是沒有效率的問題，所以複雜度並不重要，但是，對於比較要求計算效率的第三第四題，會估算題目所需的複雜度，對思考解答就非常的重要。在一般的考試與競賽中，執行時限的訂定方式有兩種：多筆測資的執行時間限制或者是單筆測資的執行時間限制。APCS採取IOI模式，所以大部分的時候都是指單一筆測資的執行時限。
程式的執行時間很難精確估算，因為每一秒可以執行的指令數牽涉的因素很多，例如：硬體速度、作業系統與編譯器、以及指令類型等等。當要估算複雜度時，建議可以一秒$10^6$ ~ $10^7$個指令數量來估計，所以，通常執行一筆測資的時限為1 ~ 4 秒，我們可以得到下面常見的複雜度推估：

| $n$ 的大小 | $>10^4$ | 數千 | 數百 | $\le 25$| $\le 10$|
| ---|---|-- | ---|----- | -------- |
| 題目要求的複雜度 | $O(n)$ or $O(n\log n)$ | $O(n^2)$ | $O(n^3)$| $O(2^n)$ | $O(n!)$ |

舉例來說，如果有一題的資料量上限為5萬，那麼這一題需要的複雜度就是$O(n)$或$O(n\log(n))$；如果資料上限是200，那麼需求的複雜度可能是$O(n^3)$。
那麼，可不可能發生題目敘述中說資料量上限100000，但是測資中的資料量只有1000呢？如果出題者想要的複雜度是$O(n)$或$O(n\log(n))$，那是測資出弱了，這是在高水準的考試與比賽中不應該出現的情形，因為它會不利於有能力者而造成不公平。有人或許會認為能力強的人應該要能自己判斷題目的複雜度，這麼想就錯了，因為測資大小是題目的一部份，相同題目敘述可能存在多種不同複雜度的解法，其難度就不同。
如果出題者想要的複雜度只是$O(n^2)$，那更糟糕了，出題者自己的程式都過不了宣稱的資料。實際考試與比賽中，照理說是不會出現這些狀況，但是也不能排除出題失誤的可能。

**複雜度需要留意的幾件事**
在本節最後，我們要提出幾個複雜度容易誤解與需要被注意的地方。
* 常用到的庫存函式sort複雜度可以用$O(n\log(n))$來看，雖然理論上worst-case也許不是。
* 理論上Big-O是指上限，而未必是緊實的上限(tight bound)。一個程式的複雜度如果是$O(n)$，你說它是$O(n^2)$理論上也沒有錯，但一般來說，我們會講盡可能緊實的上限，但並非每一個程式的緊實上限都能被準確計算。
* 複雜度有無限多種，但如果簡單來看，指數函數上升的速度遠遠高過多項式函數，因此一個演算法的複雜度如果是指數函數，通常能解的資料量大小就很小。在探討一個問題是否容易解時，指的是它是否有多項式複雜度的解，這裡的多項式函數只要指數是常數就可以，不一定要整數常數，例如$O(n^{2.5})$也視作多項式複雜度。
* 複雜度是輸入資料量的函數，而且評估的是當資料量趨近於無限大時的行為。輸入資料量通常是資料的個數(數字個數，字串長度)，但是如果涉及大數運算時，必須以輸入資料的二進位編碼長度當做資料量大小。例如，對於一個輸入的正整數，我們可以用下列簡單的試除法來檢驗它是否是質數：

    i = 2
    while i*i <= n:
        if n%i == 0:
            print('prime')
            break
        i += 1
    #

這個程式的複雜度是多少？$O(\sqrt{n})$是沒錯，但它是多項式複雜度嗎？非也，這裡的資料量是多少？輸入一個數，所以是1？那就算不出複雜度了。輸入一個數字必須輸入它的二進位編碼，所以資料量的大小是$\log(n)$，因此，上面的程式其實是指數函數複雜度，令$L=\log(n)$，它的複雜度是$O(2^{L/2})$。其實道理不難懂，所謂在一般情形下，指的是數字的運算可以在常數個指令完成的狀況，但電腦CPU的bit數為有限長度，當數字過大時，一個加法或乘法就必須軟體的方式來完成，也就不是常數個指令可以完成的。再舉一個例子，考慮以下問題：
Problem Q：輸入一個正整數$n$，請計算並輸出$1+2+…+n$的值。
用最直接的方法跑一個迴圈去做連加的總和，這樣的程式複雜度是$O(n)$，大家都知道等差級數的和可以用梯形公式計算，因此，我們可以寫出只要下面的程式：

    n = int(input())
    print(n*(n+1)//2)

這個程式的複雜度是多少？$O(1)$，沒錯吧？是。那麼，我們可以說：「Problem Q存在$O(1)$複雜度的解」嗎？答案卻是否，當$n$趨近無限大時，計算一個乘法或加法就不能在$O(1)$時間內完成。也就是說這個程式的複雜度是$O(1)$但它並不能完全解Q。

現實中並不存在無窮大，所有的題目都有範圍，有人也可以說，在理論上，只要界定了有限範圍，任何題目都可以在$O(1)$解決，因為即使複雜度高達$O(2^{10000})$也是常數，只是要算到地老天荒海枯石爛而已。這麼講好像複雜度理論沒有用？其實不是的，在大部分的場合，$n$在合理的範圍時就已經達到理論上的趨近無窮大，Big-O也都可以讓我們正確的估算程式的效率，理論不是沒用，只是不能亂用。我們唯一要注意的是，Big-O忽略常數，但是實際使用時，不可完全忽視常數帶來的影響，特別如果有可能是很大的常數。

### Python常用基本資料結構

這裡簡略的說明一些常用的內建資料結構，如果需要詳細的說明，請參考Python的文件或語法的基本教學。

#### 序列
常用的Python的序列包括：list、tuple與string三種。List的使用非常廣泛，最常見的是數列，例如

a = [1, 5, 3, 2] # list of integer
b = [1, 4.5, 6] # list of integer and float
# 它的每一個成員都可以是任意的物件，例如
a = [1, [4, 3, 2], [5,6]]
# a[0] is a int, a[1] is a list 
# 所以我們拿它來做二維陣列，例如
p = [[0]*5 for i in range(3)] 
# 其實是一個list of list來當作一個 3*5 的二維陣列
# 每一個元素都是0。

Tuple(元組)與list幾乎相同，只是list是mutable(可改變內容)，而tuple是immutable，亦即不可改變內容。那麼為什麼需要tuple呢？因為list不可以當作集合(set)與字典(dict)的key，而tuple可以。

a = (1, 5, 3, 2) # tuple of integer
b = (4,) # add a comma when only 1 element

字串也是immutable，可以看做一種特別的tuple，它的每個成員都是一個字元。例如

a = "qwerty"
b = 'hello world' # can use ' ' or " "
c = 'r'*3 # repeat
d = "pq"*5 + c # repeat and add

三種序列都可以做slicing，也就是切下其中一段，這是操作上非常好用的方式，例如以下範例，其中index如果是負值，則表示從後往前數。

a = list(range(10)) # [0,1,2,...,9]
print(a[2:5]) # [2,3,4]
print(a[:5]) # [0,1,2,3,4]
print(a[6:]) # [6,7,8,9]
print(a[2:9:3]) # [2,5,8]
b = a[::-1] # reverse of a
c = a[-3:] # last 3 element [7,8,9]

要修改或使用成員時，list直接用list[index]來存取成員，但tupe與string是不可變動的，所以需要改變時，只能另外建構一個新的。

a = list(range(5)) # [0,1,2,3,4]
a[2] = 9 # [0,1,9,3,4]
for i in range(1,len(a)): # prefix sum
    a[i] += a[i-1]
# [0,1,10,13,17]
b = "012345"
b = b[:3]+'G'+b[4:] # "012G45"
b[3] = '0' # error

#### 集合與字典
Python的集合與字典都是hash table的資料結構。兩者並非APCS的考試必須使用的資料結構，本講義中的例題說明都以**不使用集合與字典**的方式來說明，但因為它用起來簡單好用，在某些題目可以讓程式寫得更簡潔，如果可以學些基本的操作，是很有利的，所以有一部分題目我們會提供使用集合與字典的做法，是否需要學習它們的操作方式則取決與讀者個人狀況與決定。

### 需要留意的事

這一節中提出一些需要注意的事，程式解題講求題目與解答的完整完善，或者可以說測資往往都很刁鑽，只要符合題目敘述的各種狀況都需要考慮，此外，為了測試效率，常常需要大的測資，對於程式解題比較沒有經驗的人，需要留意一些容易犯的錯誤。

**整數Overflow**
Python的好處之一是基本上不必擔心整數overflow，不過，如果整數很大很大時，例如數千位，還是可能超出預設範圍而且計算就有可能花比較多的時間。

**浮點數的rounding error**
浮點數有它能表示的範圍以及精準度。如果把下面這段程式打進電腦執行一下，結果或許會讓你驚奇。

print(0.3, 0.1+0.2)
if 0.1+0.2 == 0.3: print('Yes')

浮點數儲存時會產生捨位誤差(rounding error)，其原因除了儲存空間有限之外，二進制的世界與十進制一樣也存在著無限循環小數。事實上，0.3在二進制之下就是個無限循環小數，因此不可能準確的儲存。
因為浮點數存在捨位誤差，不同的計算順序也可能導致不同的誤差，數學上的恆等式並不完全適用在浮點數的程式裡面。所以，一般解題程式的考試與競賽常常避免出浮點數的題目，因為在裁判系統上會比較麻煩，但有時還是可以看到浮點數的程式題目。無論如何，不管是否是競賽程式或是撰寫一般的軟體，在處理浮點數時，都必須對捨位誤差有所認識。一個必須知道的知識就是，浮點數基本上不應該使用==來判斷兩數是否相等，而應該以相減的絕對值是否小於某個允許誤差來判斷是否相等。

**判斷式的short-circuit evaluation**

下面是一個很簡單常見的程式片段，這段程式想要在一個陣列中找尋是否有個元素等於x，我們在判斷式中除了a[i]!=x之外，也寫了陣列範圍的終止條件i<5，但事實上這個程式是錯的，會導致執行錯誤，原因是條件式內的兩個條件順序寫反了！

a = [1,2,3,4,5]
i = 0; x = 6
while a[i] != x and i<5:
    i += 1
if i<5: print(i)
else: print(-1)

第3行正確的寫法是
while i<5 and a[i] != x:

這是唬弄人吧？誰不知道在邏輯上(A and B)與(B and A)是等價的呢？在程式的世界裡真的不一樣。當程式執行到一個判斷式的時候，它必須計算此判斷式的真偽，對於(A and B)這樣由兩個條件以「and」結合的判斷式，會先計算第一個A，如果A為真，再計算B是否為真；如果A為假，已知整個判斷式必然是假，所以並不會去計算B。
以上面的例子來說，當i是5的時候，對於(i<5 and a[i]!=x)，會先計算 i<5，如發現不成立就不會去計算a[i]!=x。但如果像程式裡面反過來寫，就會先計算a[i]!=x，因為i=5，就發生陣列超出範圍的問題。
程式語言的這種設計稱為short-circuit evaluation，對python來說，list的index一旦超過範圍就會造成runtime error，所以特別重要。

對於布林運算式，只有在第一個條件不足以判斷整個的真偽時，才會去計算第二個。同樣的情形發生在(A or B)的狀況，若A為true，就不會再計算B了。
除了對陣列超過範圍的保護，這樣的設計也用來避免發生計算錯誤，例如我們要檢查兩數a/b是否大於x，若無法確保b是否可能為0，我們就應該寫成
if b!=0 and a/b>x:
這樣才能保護不會發生除0的錯誤。

**當List的index為負值**
對Python的list來說，index是允許負值，負的時候表示是倒數，例如 a = [1,2,3]，則a[-1]就是最後一個3，a[-2]就是2。這是個蠻好用的語言特性，但世間事總是有好就有壞，當你想做的是由後往前跑到a[0]為止時，要留意不要跑到a[-1]去而不自知。

**第0章結束**