算法設計(一)

算法是為了解決某一個問題而設計的一連串清晰、可執行、按次序排列的步驟。它重點在於「思路與流程」，而不是某一種程式語言的語法。

• 輸入（Input）：程式需要讀取的資料，例如數字、文字、選項。
• 處理（Process）：對輸入資料進行運算、判斷、重複等操作。
• 輸出（Output）：運算後要呈現的結果，例如答案、提示訊息、統計值。

一般而言，一個可取的算法應具備以下特徵：

• 明確性（Unambiguous）：每一步都寫得清楚，沒有「大概」「適量」等含糊字眼。
• 有限性（Finite）：步驟數目有限，最終一定能停止（不會無窮迴圈）。
• 可行性（Effective）：每一步都是「人或電腦可以做到」的基本操作。
• 正確性（Correctness）：對所有合理輸入都能產生正確輸出。
• 一般性（Generality）：能處理一整類問題，而不只是某一個特定例子。

1. 讀懂題意：把題目改寫成「要做甚麼、要輸入甚麼、要輸出甚麼」。
2. 列出例子：用一兩組簡單輸入，手動算出正確輸出，作為日後測試基準。
3. 定義變量：需要記錄哪些中間結果？例如 sum、count、max。
4. 選擇控制結構：純順序？需要選擇（if）？需要重複（loop）？
5. 寫成偽代碼／流程圖：把每一步寫清楚，加入縮排與關鍵字，讓人一眼看出結構。
6. 以空運行驗證：用追蹤表檢查每一步的變量值是否符合預期。

空運行是不真正執行程式，而是以紙筆或心算逐行模擬程式運行，記錄每一步後各變量的值。其作用包括：

• 找出邏輯錯誤（例如次序錯、條件寫錯、漏了更新變量）。
• 理解程式實際做了甚麼，避免只「看得懂」但不會「追得出」。
• 在不能使用電腦的情況下（例如筆試），仍可驗證答案是否合理。

做追蹤表時，可以用「每一行執行後」作為一個步驟，並在表格內更新變量：

• 欄位：通常包括「行號／語句」以及每個變量（例如 i、sum）。
• 更新規則：只要某變量在該行被賦值，該欄就更新；沒有被改動就沿用上一行的值。
• 先算右邊：遇到 x ← x + 1，先用舊的 x 計算右邊，再把結果放回 x。
• 遇到條件：先判斷條件真假，再決定是否執行縮排內的語句。

偽代碼（例：n = 3）：

輸入 n
sum ← 0
i ← 1
當 i ≤ n
    sum ← sum + i
    i ← i + 1
輸出 sum

追蹤（只示意關鍵行）：

偽代碼（Pseudocode）是一種介乎自然語言與程式語言之間的描述方法。它的目的不是讓電腦直接執行，而是讓人清楚理解算法流程。

• 不依賴語言：同一份偽代碼可以轉寫成 Python、Java、C 等。
• 重視結構：用縮排表示「屬於哪一個 if／迴圈」。
• 重視步驟：每一句通常只做一件事（輸入、運算、賦值、輸出）。

不同教材用詞可能略有差異，但常見關鍵字與概念大致如下：

• 輸入／輸出：輸入 x、輸出 result
• 賦值：x ← 5（把右邊結果放入左邊變量）
• 選擇：如果 條件 … 否則 …（雙向）
• 迴圈：當 條件 …、對 i 由 a 到 b …、重複 … 直到 條件

流程圖（Flowchart）用圖形表示控制流程，常見符號包括：

• 開始／結束：橢圓形（Terminator）。
• 處理：長方形（Process），例如計算、賦值。
• 輸入／輸出：平行四邊形（I/O），例如讀取資料、顯示結果。
• 判斷：菱形（Decision），有「是／否」兩個分支。
• 箭嘴：表示執行方向（一般由上而下、由左至右）。

• 一張流程圖應有單一開始點，並能走到結束點。
• 每個判斷（菱形）應標示兩個出口，例如「是／否」或「True／False」。
• 迴圈通常表現為「判斷 →（是）→ 處理 → 回到判斷」。
• 避免線條交叉；需要時可用連接符號（Connector）或重新排版。

互換的核心是辨認三種基本結構：

• 順序（Sequence）：一步接一步 → 流程圖用箭嘴串起多個處理框。
• 選擇（Selection）：if／if…else → 流程圖用菱形分支。
• 重複（Iteration）：while／for／repeat…until → 流程圖用回圈箭嘴回到判斷框。

• 縮排不一致：會令分支或迴圈的範圍變得含糊。
• 把「=」當作賦值：偽代碼通常用 ← 表示賦值；= 多用於比較。
• 漏寫更新：例如 while 迴圈內忘記 i ← i + 1，容易造成無窮迴圈。
• 流程圖判斷出口未標示：令讀者無法確定 True 走哪邊。

變量可以理解為記憶體中的一個儲存位置，我們用名稱去代表它，並在程式運行期間讀取或改變其值。

• 名稱（Name）：例如 score、total_mark。
• 值（Value）：目前儲存在變量內的資料，例如 80、"Hello"、True。
• 狀態會改變：變量值會隨著賦值語句而更新，因此需要空運行追蹤。

在偽代碼中常用箭嘴 ← 表示賦值：先計算右邊，再把結果放入左邊變量。

x ← 5
x ← x + 1    # 先用舊的 x (5) 計算右邊，得到 6，再放回 x

• x ← x + 1 在數學上看似矛盾，但在程式中代表「把 x 增加 1」。
• 賦值會覆蓋原本的值，因此順序非常重要。

很多變量在使用前需要先給定初值（初始化），否則變量可能是「未定義／不確定」狀態。

• 初始化：例如把 sum ← 0、count ← 0。
• 更新：在迴圈內不斷改變，例如 sum ← sum + x。
• 輸入：如果變量來自輸入，先 輸入 x 再使用 x。

常數是程式中不希望被更改的固定值，例如圓周率。實務上常用全大寫表示：

PI ← 3.14159

良好命名能令算法更易讀：

• 以用途命名：total、maxScore、studentName。
• 避免只用 a、b（除非題目本身如此定義）。
• 保持一致：全程用同一種命名風格（例如 snake_case 或 camelCase）。

例子：

a ← 4
b ← a + 3
a ← b - 2

• 覆蓋造成資料遺失：例如互換 x、y 時，如果沒有臨時變量，原本的值可能被覆蓋。
• 未初始化：使用 sum 前忘記設為 0。
• 混淆變量：題目有多個變量時，容易看錯名稱（例如 total vs totals）。

算術表達式（Arithmetic expression）是由數字、變量、常數及運算符組合而成的式子，重點是它計算後會得到一個值，可用於賦值或輸出。

total ← price * qty
輸出 total

• + 加法、- 減法、* 乘法、/ 除法（可得到小數）
• // 整數除法（只取整數部分，例如 9 // 2 = 4）
• % 或 MOD 取餘數（例如 9 % 2 = 1）
• 括號 ( ) 用來改變運算次序

當一個表達式包含多個運算符時，需要依優先次序計算。常見次序如下（由高到低）：

1. 括號 ( )
2. 乘法／除法／整除／取餘（*、/、//、%）
3. 加法／減法（+、-）

同一層級通常由左至右計算。

以 total = 17、n = 5 為例：

• total // n = 17 // 5 = 3（只取整數部分）
• total % n = 17 % 5 = 2（因為 17 = 5 × 3 + 2）

例：已知 a = 10、b = 3，計算 result ← a + b * 2

1. 先算乘法：b * 2 = 3 * 2 = 6
2. 再算加法：a + 6 = 10 + 6 = 16
3. 因此 result = 16

a ← 10
b ← 3
result ← a + b * 2

• 忽略優先次序：把 a + b * 2 錯算成 (a + b) * 2。
• 除以 0：若除數可能為 0，需先用 if 檢查。
• 整數／實數混用：例如某些語言中 5 / 2 會得到 2.5，而 5 // 2 才是 2。
• MOD 只適用整數：一般不會對小數取餘數（視語言而定）。

題目會給出 x、y 的初始值，以及一段包含運算與賦值的偽代碼。你需要計算程式執行完後 x、y 的最終值。

1. 先把題目給的初始值寫下（或在草稿畫一個小追蹤表）。
2. 由上而下讀偽代碼：每遇到 ←，先計算右邊，再把結果放入左邊。
3. 完成所有行後，才寫出最終 x、y。

如果右邊表達式較長，建議分步計算：

• 先處理括號，再處理乘除／整除／取餘，最後才加減。
• 必要時把中間結果寫在旁邊，例如先算出 t = y * 2 再代回。

• 檢查每一步是否用了最新的變量值（不是初始值）。
• 如果答案看起來不合理（例如突然變得極大或極小），回到上一行重算。
• 遇到整除 // 或餘數 %，可用「被除數 = 除數 × 商 + 餘數」檢查。

電腦在記憶體中儲存資料時，需要知道資料屬於哪一種數據類型，原因包括：

• 佔用空間不同：整數、實數、字串在記憶體中所需空間不同。
• 可做的運算不同：數字可加減乘除；字串可串接、取長度；布爾值可做邏輯運算。
• 避免錯誤：把「文字」當作「數字」運算會導致錯誤或不合預期結果。

• 整數（Integer）：沒有小數部分，例如 -5、0、27。
• 實數（Real / Float）：有小數部分，例如 3.14、-0.5。

在很多教材／偽代碼表示法中：

• 字元（Character）：單一字元，常用單引號，例如 'A'、'7'。
• 字串（String）：多個字元組成，常用雙引號，例如 "Hello"、"123"。

布爾值只有兩個可能：True 或 False。它經常來自比較或邏輯運算：

isAdult ← (age ≥ 18)
如果 isAdult
    輸出 "可以購票"

• 比較運算（例如 >、≤、=）的結果是布爾值。
• AND、OR、NOT 也是針對布爾值運算。

有時資料的外觀與需要的類型不一致，例如輸入通常是文字，需要轉成數字才能計算。

• 把字串轉整數：age ← INT(inputAge)
• 把整數轉字串：msg ← STRING(score)（方便輸出拼接文字）

• 串接 vs 加法："12" + "3" 可能得到 "123"，而不是 15。
• 比較錯誤：字串比較與數值比較的規則不同，例如 "9" > "10" 可能為 True（視語言字典序）。
• 引號遺漏：想表示字串卻忘了加引號，會被當作變量名稱或出現錯誤。

系統會顯示一個資料（可能是數字、文字、True/False 等），你需要判斷它屬於哪一種數據類型。

1. 有引號嗎？ 有引號多數是字串或字元（單引號常代表字元，雙引號常代表字串）。
2. 有小數點嗎？ 有小數點通常是實數（Real）。
3. 是否 True/False？ 是的話就是布爾值（Boolean）。

• "0"、"123"：有引號 → 字串（不是整數）。
• '7'：單一字元且有單引號 → 字元（不是整數 7）。
• 3.0：即使小數部分是 0，有小數點 → 實數。

選完類型後，可以反問自己一句：

• 「我能對它做四則運算嗎？」若不能，可能不是數值類型。
• 「它需要引號才能表示嗎？」若需要，通常是字串／字元。

交換兩個變量的值（swap）是很多算法的基礎操作，例如：

• 排序（Sorting）：若 a 大於 b，就交換它們的位置。
• 重新安排資料：例如把最大值移到最後、把最小值移到最前。

最標準、最易懂的交換方法：

temp ← x
x ← y
y ← temp

1. 先把 x 的舊值存入 temp（備份）。
2. 再把 y 放入 x。
3. 最後把備份的舊 x（temp）放回 y。

若寫成：

x ← y
y ← x

第二行的 x 已經是「新的 x」（即原本的 y），原本的 x 已經遺失，因此最後會變成：

• x 與 y 變成相同值（都是原本的 y）。

有些語言/情況會介紹不用臨時變量的技巧，例如：

x ← x + y
y ← x - y
x ← x - y

但這種做法有風險：

• 可能出現溢位（overflow）（數值太大超過可表示範圍）。
• 可讀性較差，容易寫錯。

• 先寫下初始：x、y、temp。
• 逐行執行，每行之後立即更新表格。
• 特別留意：temp ← x 後，temp 保存的是「舊 x」。

選擇結構（Selection）令程式可以根據條件，決定是否執行某些語句。最基本的是 if 單向選擇：

• 條件為 True → 執行 if 內的語句。
• 條件為 False → 跳過 if 內的語句，直接往下。

if 的條件是一個布爾算式，結果只能是 True 或 False。常見比較運算符：

• >、<、>=、<=
• =（相等）、≠ 或 !=（不相等）

典型偽代碼寫法：

如果 條件
    （條件為 True 才會執行的語句）
（if 結束後繼續往下）

• 縮排用來表示「哪些語句屬於 if 內」。
• 條件為 False 時，if 內語句完全不會執行，變量值亦不會改變。

實際問題常需要多個條件同時判斷，可用邏輯運算符：

• AND：兩個條件都 True 才 True。
• OR：任一條件 True 就 True。
• NOT：把 True 變 False、False 變 True。

• 把賦值當比較：在程式語言中常見錯誤是把 = 寫成賦值；在偽代碼中建議用 ← 表示賦值以避免混淆。
• 忽略邊界：例如 x > 10 不包括 10；要包括 10 應寫 x ≥ 10。
• 未更新變量：在 if 內更新後，後續語句要用更新後的值。

例：消費滿 500 元可打九折（把 pay 更新）：

輸入 amount
pay ← amount
如果 amount ≥ 500
    pay ← amount * 0.9
輸出 pay

解釋：

• 先把 pay 設成原價，確保「不符合條件」時也有正確輸出。
• 只有滿足 amount ≥ 500 才會把 pay 改為九折價。

這類題目通常給出初始 x、y，以及一段 if 偽代碼。解題時：

1. 先代入初始值，計算 if 的條件是 True 還是 False。
2. 若條件為 True，才逐行執行 if 內的語句；若為 False，直接跳到 if 後面。
3. 最後寫出程式結束時的 x、y。

• 在草稿畫一個小追蹤表（欄：x、y），每行執行後更新一次。
• 若 if 條件為 False，if 內所有賦值都不會發生，變量保持原值。
• 看到 x ← x + 1，先用舊 x 計算右邊，再放回 x。

• > 與 >=、< 與 <= 很容易混淆。
• 題目常用「至少」「不多於」「介乎…之間」等字眼，需要轉成正確比較式。

例：初始 x = 10，偽代碼：

如果 x > 10
    x ← x + 5
輸出 x

因為 10 > 10 為 False，所以 if 內不執行，最後輸出仍是 10。

if…else 用於「二選一」情況：

• 條件為 True → 執行 if 分支。
• 條件為 False → 執行 else 分支。

如果 條件
    （True 時執行）
否則
    （False 時執行）
（結束後繼續往下）

• 如果 與 否則 應在同一縮排層。
• 各自分支內的語句向右縮排一層，表示「屬於該分支」。

當有多於兩個情況時，常用「else if」串成多分支（不同教材寫法略有差異）：

如果 score ≥ 80
    grade ← "A"
否則如果 score ≥ 60
    grade ← "B"
否則
    grade ← "C"

• 判斷是由上而下進行，一旦某條件成立，就執行該分支並跳出整個選擇結構。
• 因此條件次序要由「最嚴格／最高門檻」到「較寬鬆」較常見。

若條件寫得不恰當，可能出現「重疊」或「永遠到不了」的分支：

• 例：先寫 score ≥ 60，再寫 score ≥ 80，後者就永遠不會被執行。
• 建議：由高到低排列，或用不重疊範圍（例如 60 ≤ score < 80）。

例：輸入分數，輸出結果字串：

輸入 mark
如果 mark ≥ 50
    result ← "及格"
否則
    result ← "不及格"
輸出 result

無論條件真或假，最後都會得到 result 的值，因此通常不需要在 if 之外再額外處理。

• 只寫 if 不寫 else：但題目需要「兩種情況都要處理」，就必須寫 else。
• 在兩邊都更新同一變量：要確保每邊更新的內容符合該情況。
• 忘記輸出或忘記初始化：例如只在 if 分支賦值，else 分支忘了，會造成未定義。

解題時記住：if…else 只有一邊會被執行。

1. 代入初始值，計算條件真假。
2. 條件 True → 執行 if 分支；條件 False → 執行 else 分支。
3. 把被執行分支內的賦值逐行計算，更新變量。
4. 寫出最終 x、y。

建議在草稿上把不會執行的一邊劃掉（或在心中標記），避免混入計算。

• 看清楚比較符號（> vs >=）。
• 遇到「至少」「不多於」等字眼，要轉成正確的包含關係。

例：初始 x = 4：

如果 x % 2 = 0
    y ← 100
否則
    y ← 200

因為 4 % 2 = 0，條件 True，所以 y = 100。

本練習只包含順序結構：程式由上而下逐行執行，沒有 if（分支）和 loop（重複）。

• 每一行的賦值都會直接生效，下一行會用到更新後的變量值。
• 因此追蹤表的重點是「逐行更新」而不是判斷走哪條路。

1. 先快速掃描整段偽代碼，列出會出現的變量名稱。
2. 找出它們的初始值（最先被賦值的一行）。
3. 如果某變量在開始時未被賦值，就先標記為「未定」，直到它第一次被賦值。

• 以「每一行執行後」作為一列。
• 該行有賦值的變量要更新；其餘變量沿用上一行的值。
• 若該行只是輸出或註解，通常不會改變變量。

遇到較長算式時，可以分步：

• 先做括號，再做乘除／整除／取餘，最後做加減。
• 把中間結果寫在旁邊（或在追蹤表「備註」欄），方便核對。

• 忘記沿用舊值：某行只改了 x，你卻把 y 也改了。
• 把新舊值混用：同一行右邊應使用「該行執行前」的舊值計算。
• 符號錯誤：減法順序、負數、整除與除法混淆。

迴圈用於重複執行一段語句，直到達成某個停止條件。設計迴圈時，通常要同時想清楚三件事：

• 初始化：迴圈開始前，變量的初始值是甚麼？
• 條件：甚麼情況下繼續重複？甚麼情況下停止？
• 更新：每次重複後，哪個變量會改變以推動迴圈走向停止？

for 迴圈通常用於「重複次數已知」或「由某範圍逐步掃描」的情況。

sum ← 0
對 i 由 1 到 5
    sum ← sum + i
輸出 sum

• i 會自動由 1 變到 5（是否包含終點視題目寫法）。
• 做空運行時，可把每次 i 的值列出，再逐次更新 sum。

while 迴圈會先檢查條件，只有在條件為 True 時才進入迴圈。

i ← 1
當 i ≤ 5
    輸出 i
    i ← i + 1

• 若一開始條件已經是 False，迴圈內語句會一次也不執行。
• 空運行時要先判斷「能否進入」，再追蹤迴圈內更新。

do…while 的特點是：先執行一次迴圈內容，再檢查條件是否繼續。

do
    x ← x + 1
while x < 10

• 即使起初 x 已經不小於 10，也會先執行一次 x ← x + 1。

repeat…until 常見寫法是：

重複
    （迴圈內容）
直到 條件

• 與 do…while 類似：迴圈內容至少執行一次。
• until 的條件是「停止條件」：條件為 True 就停；為 False 就繼續重複。

1. 先寫下迴圈開始前的初始值（尤其是計數器和累加器）。
2. 每次迴圈開始時，先判斷是否會進入（for 直接按範圍；while 先判斷；do/repeat 先執行）。
3. 把每一次迴圈後「會變的變量」記錄下來（例如 i、sum）。
4. 重複直到停止條件成立，最後寫出題目要求的變量最終值。

• Off-by-one（差一）：例如 i 由 1 到 5，究竟做 5 次還是 4 次？要看題目寫法是否包含終點。
• 條件方向寫反：while 應寫「繼續條件」，until 應寫「停止條件」。
• 更新位置錯：例如 i ← i + 1 放錯位置，會影響執行次數或導致無窮迴圈。