AS Level 電腦科學 (9618) 學習筆記

第九章：算法設計與問題解決

哈囉！歡迎來到電腦科學的核心領域。這一章主要探討電腦如何思考——或者更準確地說，我們如何「教」它們思考。算法設計（Algorithm design）是一項關鍵技能，能將現實世界的問題轉化為機器可以執行的逐步解決方案。

只要掌握了這裡的邏輯技巧，編程就會變得輕鬆許多。如果這些概念起初看起來很抽象也不用擔心，我們會用生活中的例子為大家拆解！

9.1 運算思維技巧

運算思維 (Computational Thinking) 是我們利用電腦科學的方法來高效解決問題時所運用的一套思維工具。其中最重要的兩項技巧就是抽象化（Abstraction）與分解（Decomposition）。

A. 抽象化 (Abstraction)

抽象化意味著專注於問題的本質特徵，同時忽略或隱藏不相關的細節。

當你為一個系統建立抽象模型時，只需納入解決當前問題所需的必要細節。

類比：使用地圖

想像一下你正在用導航 App 開車回家：

  • 地圖顯示了必要的細節：道路、路口和你目前的位置。
  • 它忽略了不相關的細節：每一輛車的顏色、樹上有多少片葉子，或是每家商店的名字。

這種過濾後的視圖就是一個抽象模型。如果地圖包含了一切資訊，它就會變得過於複雜，無法用於導航。

為什麼要使用抽象化？

  • 它能簡化複雜的系統，使其更容易管理和理解。
  • 它讓開發者能專注於核心功能，而不被實作細節所困擾。
  • 它有助於明確定義所需的數據與處理過程。

快速複習：抽象化的精髓就是濾掉噪音（非必要細節），以看清訊號（必要細節）。

B. 分解 (Decomposition)

分解是指將一個龐大且複雜的問題拆解成較小、較易處理的子問題（或任務）的過程。這些子問題隨後可以個別解決。

類比：焗製蛋糕

製作一個複雜的生日蛋糕是一項艱巨的任務，但你可以將它分解：

  1. 製作海綿蛋糕體（子問題 1）。
  2. 準備糖霜（子問題 2）。
  3. 裝飾蛋糕（子問題 3）。

每個子問題都更容易解決，且可以分派給不同人或分開完成。在編程中，這些子問題通常會變成程式模組，例如程序 (Procedures) 或函數 (Functions)。

分解的好處：

  • 使問題更容易解決及偵錯（Debug）。
  • 允許不同的程式部分由不同團隊同時開發（或透過編寫獨立模組）。
  • 模組通常可以在其他專案中重複使用。

重點總結：運算思維給了我們一套框架：分解將任務拆開，而抽象化簡化了拆分後的部件。

9.2 算法 (Algorithms)

A. 定義算法

算法就是一系列定義明確、有序的步驟或指令；只要遵循這些步驟，就能保證得出問題的解決方案。

把算法想像成食譜：它精確地告訴你該採取什麼步驟、以什麼順序進行，並使用特定的原料（數據）來獲得預期的結果（解決問題）。

B. 表示算法

在撰寫真正的程式碼之前，我們需要記錄算法的方法。課程大綱要求你熟悉三種主要的表示形式：

1. 結構化英語 (Structured English / Narrative Description)

使用淺顯易懂的英語，結合保留關鍵字（如 IF、THEN、ELSE、WHILE）來清晰描述邏輯。適合用於高階描述。

範例：IF 分數大於 90 THEN 輸出 "優異"。

2. 流程圖 (Flowcharts)

流程圖使用圖形符號來顯示步驟順序、控制流和算法邏輯。

你必須熟記標準符號：

  • 橢圓形：開始/結束 (Terminator)
  • 平行四邊形：輸入/輸出 (Input/Output)
  • 矩形：處理/計算 (Process/Calculation)
  • 菱形：決策/選擇 (Decision/Selection，通常詢問是/否問題)
  • 箭頭：流程線 (Flow lines，顯示控制方向)
3. 虛擬碼 (Pseudocode)

虛擬碼是一種人工的、非正式的語言，旨在幫助程式設計師開發算法。它不綁定於任何特定的編程語言，但使用通用的結構慣例（如 IF、WHILE、FOR）。

重要性：虛擬碼是你考試時編寫算法的主要方式。它足夠詳細，能輕易轉換為真正的程式碼，同時又夠易讀，讓人類能理解其中的邏輯。（務必參考 Cambridge 官方的虛擬碼指南以確認具體關鍵字！）

C. 使用識別碼 (Identifiers)

解決問題時，我們需要為所使用的數據命名（變數、常數、陣列）。這些名稱稱為識別碼。

規則：務必使用合適的識別碼名稱。名稱應具備意義，並準確反映數據的內容。

不要寫： x = y * 5
建議寫： TotalCost = ItemPrice * Quantity

在考試中，你可能需要使用識別碼表 (Identifier table) 來記錄問題中使用的數據：

識別碼 數據類型 描述
NumItems INTEGER 儲存購買物品的數量（必須為正數）。
ItemPrice REAL 儲存單件物品的價格。

你知道嗎？使用良好的識別碼對於維護至關重要。如果五年後有人需要修復你的程式碼，他們會感謝你選擇了具描述性的名稱！

9.2 算法結構：構建塊

無論複雜程度如何，所有算法都由三種基本結構組成：序列 (Sequence)、選擇 (Selection) 和迭代 (Iteration)。

A. 序列 (Sequence)

序列是指按照指令出現的順序，逐一執行。

範例 (虛擬碼)：
INPUT Name
OUTPUT "Welcome"

B. 選擇 (Selection / Decision Making)

選擇允許算法根據條件（通常為布林值：TRUE 或 FALSE）來決定執行哪條路徑。

1. IF...THEN...ELSE

用於在兩條或多條路徑之間進行選擇。

範例 (虛擬碼)：
IF Temperature > 30 THEN
    OUTPUT "天氣很熱"
ELSE
    OUTPUT "天氣舒適"
ENDIF

2. CASE OF / OTHERWISE (SWITCH)

當你根據單一變數的值有多個固定的選擇時，這非常有用。

範例 (虛擬碼)：
CASE OF DayNumber
    1: OUTPUT "星期一"
    5: OUTPUT "星期五"
    OTHERWISE: OUTPUT "週末"
ENDCASE

C. 迭代 (Iteration / Repetition / Loops)

迭代允許一組指令重複執行。

1. 計數迴圈 (Count-Controlled Loop / FOR Loop)

重複固定的次數。

範例 (虛擬碼)：
FOR Counter = 1 TO 10
    OUTPUT Counter
NEXT Counter

2. 前置條件迴圈 (Pre-Condition Loop / WHILE Loop)

在執行迴圈體之前檢查條件。如果條件初始為 FALSE，迴圈一次也不會執行。

範例 (虛擬碼)：
WHILE Total < 100 DO
    INPUT Number
    Total = Total + Number
ENDWHILE

3. 後置條件迴圈 (Post-Condition Loop / REPEAT UNTIL Loop)

在執行迴圈體之後檢查條件。這保證了迴圈至少會執行一次。

範例 (虛擬碼)：
REPEAT
    INPUT Password
UNTIL Password = "secret"

常見錯誤警示：學生經常混淆 WHILE 和 REPEAT UNTIL。記住：WHILE 先檢查（可能執行 0 次）。REPEAT UNTIL 最後檢查（至少執行 1 次）。

重點總結：所有的軟體邏輯都僅由這三種結構組成：序列、選擇和迭代。

9.2 算法技術

D. 逐步求精 (Stepwise Refinement / Top-Down Design)

逐步求精是將算法分解為越來越細緻層次的過程。你從一個非常籠統的描述開始，不斷細化每一步，直到它足夠詳細，可以輕鬆地寫成程式碼。這是由上而下設計 (Top-Down Design) 的核心部分。

流程範例：庫存管理

層次 1 (高階)：
1. 啟動庫存系統。
2. 處理交易。
3. 生成報告。
4. 結束系統。

層次 2 (細化第 2 步)：
2. 處理交易：
    2.1 WHILE 未到當日結束 DO
    2.2     獲取交易類型。
    2.3     IF 類型 = 銷售 THEN 更新庫存。
    2.4     IF 類型 = 入貨 THEN 增加庫存。
    2.5     ENDWHILE

當達到層次 3 或 4 時，步驟已經足夠詳細，可以直接轉換為虛擬碼（或程式語言）。

E. 邏輯語句 (Logic Statements)

邏輯語句使用布林運算子 (AND, OR, NOT) 來定義算法的部件。這對於複雜的選擇和迭代條件至關重要。

範例：如果學生成績超過 50 分且 (AND) 出席率超過 80%，則該學生及格。
IF Score > 50 AND Attendance > 80 THEN
    Pass = TRUE
ENDIF

標準算法（線性搜尋與冒泡排序）

你必須能夠針對兩種標準算法編寫並追蹤其虛擬碼：線性搜尋（Linear Search）和冒泡排序（Bubble Sort）。這些是處理陣列（第 10 章涵蓋）時必備的技能。

A. 線性搜尋 (Linear Search / Sequential Search)

搜尋陣列或列表最簡單的方法。它從開頭開始，按順序（一個接一個）檢查每一項，直到找到目標項目或到達列表末端。

流程：

  1. 從第一個元素開始（索引 0）。
  2. 將當前元素與目標值進行比較。
  3. 如果匹配，停止並返回索引。
  4. 如果沒有匹配，移至下一個元素。
  5. 如果到達列表末端，表示該項目不在列表中。

效能：對於大型數據集，這種方法較慢，因為在最壞的情況下，必須檢查每一項。

線性搜尋的虛擬碼範例：
FUNCTION LinearSearch(DataArray, Target)
    Found = FALSE
    Index = 0
    WHILE Found = FALSE AND Index < ArrayLength DO
        IF DataArray[Index] = Target THEN
            Found = TRUE
        ENDIF
        Index = Index + 1
    ENDWHILE
    IF Found = TRUE THEN
        RETURN Index - 1
    ELSE
        RETURN -1 // 表示未找到
    ENDIF
ENDFUNCTION

B. 冒泡排序 (Bubble Sort)

一種簡單的排序算法，它重複走訪列表，比較相鄰元素，若順序錯誤則交換位置。重複此過程直到列表完全排序。

類比：氣泡上升

想像一杯碳酸飲料。最大、最重的氣泡（最大的值）會緩慢地「冒」到頂部，而較小的則留在底部。

流程：

  1. 從列表開頭開始。
  2. 比較第一個元素與第二個元素。
  3. 如果順序錯誤，交換它們。
  4. 移動到下一對（第二和第三個元素）並重複。
  5. 一直持續到列表末端（完成一次遍歷）。最大且未排序的項目現在已處於正確的最終位置。
  6. 重複整個過程，每次將比較範圍縮小一個項目，直到在完整的一次遍歷中不再發生交換為止。

效能：冒泡排序對於大型數據集來說效率極低，特別是數據初始順序完全隨機時。然而，其簡潔性使其非常容易理解與實作。

冒泡排序的虛擬碼範例（將大小為 N 的陣列 A 按升序排序）：
PROCEDURE BubbleSort(A, N)
    SwapMade = TRUE
    Upper = N - 1
    WHILE SwapMade = TRUE DO
        SwapMade = FALSE
        FOR Index = 0 TO Upper - 1
            IF A[Index] > A[Index + 1] THEN
                Temp = A[Index]
                A[Index] = A[Index + 1]
                A[Index + 1] = Temp
                SwapMade = TRUE
            ENDIF
        NEXT Index
        Upper = Upper - 1
    ENDWHILE
ENDPROCEDURE

快速複習：算法設計基礎
  • 運算思維：運用抽象化（簡化）與分解（拆解）。
  • 算法：解決問題的一系列定義明確的步驟。
  • 表示法：流程圖（圖表）、結構化英語（敘述）、虛擬碼（結構化文字）。
  • 結構：序列、選擇 (IF/CASE)、迭代 (FOR, WHILE, REPEAT UNTIL)。
  • 技術：逐步求精（逐漸增加細節）。