Learning Objectives
- 說明「計算」是依照明確的規則，把輸入轉換成輸出的過程
- 說出演算法的五個特性：輸入、輸出、明確性、有限性、有效性
- 用自然語言、流程圖、虛擬碼與程式描述同一個演算法
- 比較同一個問題的兩種演算法，說出步數的差別
「幫我買杯飲料」電腦聽得懂嗎
請朋友幫你買飲料，你可能只說一句「幫我買一杯紅茶，微糖去冰」。朋友會自己決定走哪條路、去哪家店、錢不夠怎麼辦。
如果要叫電腦（或機器人）做同一件事，這句話就不夠了：哪一家店？走哪條路？店裡沒有紅茶怎麼辦？付多少錢？電腦不會「自己想辦法」，它只會照著指令一步一步做。所以要讓電腦解決問題，得先把問題拆成每一步都明確、照做就會得到答案的步驟。
這一課要回答：
- 電腦說的「計算」是什麼意思？
- 怎樣的步驟才算一個「演算法」？
- 同一個問題，不同的做法差多少？
計算：依照規則，把輸入變成輸出
在計算機科學裡，計算（computation）不只是加減乘除，而是依照明確的規則，把輸入轉換成輸出的過程：
| 問題 | 輸入 | 輸出 |
|---|---|---|
| 算總分 | 每一科的分數 | 總分 |
| 導航 | 起點、終點、地圖 | 一條路線 |
| 排序通訊錄 | 一串姓名 | 依筆畫排好的姓名 |
| 翻譯 | 一段中文 | 一段英文 |
| 判斷密碼對不對 | 你輸入的密碼、系統存的資料 | 「正確」或「錯誤」 |
這些問題看起來完全不同，但對電腦來說都一樣：讀進一些資料，照著步驟處理，產生結果。
演算法：明確、會結束的步驟
演算法（algorithm）是解決一個問題的一連串明確步驟。這個詞來自九世紀的波斯數學家花拉子米（al-Khwarizmi）：他談印度計數法的著作在十二世紀譯成拉丁文時，書名以 Algoritmi 開頭，那是他名字的拉丁寫法，後來演變成英文的 algorithm。
常見的教科書把演算法的特性整理成五點：
| 特性 | 意思 | 違反的例子 |
|---|---|---|
| 輸入（input） | 有零個或多個輸入資料 | |
| 輸出（output） | 至少產生一個結果 | 算了半天什麼都沒告訴你 |
| 明確性（definiteness） | 每一步的意思都清楚，不會有兩種解讀 | 「加一點鹽」：一點是多少？ |
| 有限性（finiteness） | 在有限的步驟之後一定會結束 | 「從 1 開始一直數下去」 |
| 有效性（effectiveness） | 每一步都做得到 | 「列出所有的質數」：質數有無限多個，列不完 |
食譜很像演算法，但通常不夠明確（「適量」「炒到香」）。電腦需要的是連「適量」都寫成數字的步驟。
描述演算法的四種方式
同一個演算法可以用不同的方式寫下來。以「找出一串分數裡的最高分」為例：
自然語言：先把第一個分數當成目前的最高分；接著看下一個分數，比目前的最高分高就換掉；全部看完之後，手上的就是最高分。
流程圖：
開始
│
best = 第一個分數
│
┌─▶ 還有沒看過的分數？ ──否──▶ 輸出 best ──▶ 結束
│ │是
│ 這個分數 > best？ ──是──▶ best = 這個分數
│ │否 │
└───────┴────────────────────────┘
虛擬碼（pseudocode，介於自然語言與程式之間，不講究語法）：
best ← scores 的第一個
對 scores 裡其餘的每一個 s：
如果 s > best：best ← s
輸出 best
程式：下面的動畫用 Python 寫成，電腦可以直接執行。不會寫程式也沒關係，重點是看每一步做了什麼。
找最高分：一個一個比
按 ▶ 自動播放，或用「下一步」慢慢看。上方的格子是分數串列，▲ 指出正在比較的位置；注意「目前的最高分」只在遇到更高的分數時才改變。程式裡的 scores[i] 是「第 i 個分數」，從 0 開始數。
輾轉相除法：兩千多年前的演算法
求 48 和 18 的最大公因數。約西元前 300 年，古希臘數學家歐幾里得的《幾何原本》就記載了這個方法（原文用反覆相減）。現在常見的寫法是：用大的數除以小的數取餘數，再用「除數」除以「餘數」，一直重複，直到餘數是 0。% 是取餘數的運算。看 a、b 每一輪怎麼變小，數數看一共做了幾輪。
同一個問題，不同的演算法
猜數字遊戲：答案是 1 到 100 之間的整數，每猜一次會告訴你「太大」或「太小」。
| 做法 | 怎麼猜 | 最多要猜幾次 |
|---|---|---|
| 一個一個猜 | 1、2、3…依序猜 | 100 次 |
| 每次猜中間 | 先猜 50；太小就在 51～100 再猜中間，太大就在 1～49 再猜中間 | 7 次 |
第二種做法每猜一次，可能的範圍就少掉一半：100 → 50 → 25 → 12 → 6 → 3 → 1。範圍變成 1 個數以前最多只要 7 次，因為 2⁷ = 128 已經大於 100。
兩種做法都是正確的演算法，但需要的步數差很多。選對演算法，比換一台更快的電腦更有用；這是第 24 課「演算法與複雜度」的主題。
猜數字：每次猜中間
答案是 73。看 lo 和 hi 怎麼把範圍一步一步縮小。(lo + hi) // 2 是「取中間，去掉小數」。你可以在下方把 secret = 73 改成別的數字（1～100）再跑一次，看看最多猜幾次。
想一想：演算法的特性
「重複把 x 除以 2，直到 x 等於 0」，x 一開始是 5（整數除法，5 // 2 = 2）。這個步驟會結束嗎？
「把冰箱裡過期的東西丟掉」這一步，最可能違反演算法的哪一個特性？
下面的程式會印出什麼？
a = 30
b = 12
while b != 0:
r = a % b
a = b
b = r
print(a)
想一想：步數比較
用「每次猜中間」的方法猜 1 到 1000 之間的數字，最多要猜幾次？
找最高分的演算法，如果有 n 個分數，總共要做幾次「比較」？
實作：找出最低溫
模仿「找最高分」的演算法，找出一週裡的最低溫。補完 # TODO 那一段（兩行）後按「執行並檢查」。注意 Python 用縮排表示「這幾行屬於 while 迴圈或 if 判斷」。
重點整理
- 計算是依照明確的規則，把輸入轉換成輸出的過程；導航、排序、翻譯都是計算。
- 演算法是解決問題的一連串明確步驟，五個特性：輸入、輸出、明確性、有限性、有效性。
- 同一個演算法可以用自然語言、流程圖、虛擬碼或程式來描述；程式是電腦可以直接執行的版本。
- 寫演算法要想到特殊情況，例如人數為 0、資料是空的。
- 同一個問題可以有不同的演算法，步數可能差很多：猜 1～100 的數字，一個一個猜最多 100 次，每次猜中間最多 7 次。
想多練習寫程式，可以接著上 Python 軌；想深入演算法，可以上演算法軌。
下一課：電腦處理的資料，在電腦裡全部是 0 與 1。第 03 課看數字怎麼用二進位表示，以及位元、位元組是什麼。