Following and writing algorithms

歡迎來到演算法的設計與閱讀！

你好，未來的程式設計師！這一章節至關重要，因為演算法是計算機科學的靈魂。你可以把演算法想像成一套完美且萬無一失的操作說明書。無論你是要烤一片吐司，還是要開發下一款大型應用程式，清晰的步驟都是成功的關鍵。

在本節中，我們將學習如何閱讀並遵循這些說明，如何將它們轉譯為實際的程式語言，以及最重要的一點——如何手動檢查它們是否運作正確，這項技能被稱為「人工追蹤」（hand tracing）。即使編寫程式碼聽起來很艱深，只要掌握了其中的邏輯，你會發現程式設計其實簡單得多。讓我們開始吧！

1. 理解演算法 (3.3.3 內容)

在我們開始遵循指示之前，必須先確切了解這些指示是什麼。

什麼是演算法？

演算法 (Algorithm) 被定義為一系列為了完成某項任務所遵循的步驟，且該步驟必須能夠終止。

• 一系列步驟： 指令必須有邏輯順序。步驟 2 必須在步驟 1 之後執行。
• 完成任務： 它必須達到預期目標（例如：排序列表、計算稅額、烘焙蛋糕）。
• 必須終止： 這點非常關鍵！演算法必須在有限時間內完成。它不能永遠陷入無窮迴圈。

類比： 把演算法想成食譜。
如果你按照食譜一步步操作，你應該能成功完成任務（烤好蛋糕），而且當蛋糕準備好時，過程就會停止（它終止了）。如果食譜告訴你要「不停攪拌直到永遠」，那它就不算是演算法，因為它可能永遠不會終止！

2. 使用偽代碼表達演算法 (3.3.3 內容)

演算法通常使用偽代碼 (Pseudocode) 來表達。偽代碼並非真正的程式語言；它是一種非正式的、高階的程式步驟描述。

它能幫助程式設計師在設計邏輯時，不必受限於 Python 或 Java 等語言嚴格的語法規則。

考試重要提示： 你需要熟悉如何使用偽代碼表達演算法，並能讀懂用偽代碼編寫的演算法。然而，考試中不需要你自己撰寫偽代碼。這意味著你的重點應該放在準確地閱讀和解讀它們。

必須認識的關鍵偽代碼結構

要讀懂偽代碼，你必須辨識出基本的控制結構：

1. 順序結構 (Sequence)： 簡單的逐行執行。
範例：

INPUT Number1
INPUT Number2
Total = Number1 + Number2
OUTPUT Total


2. 選擇結構 (Selection/Decisions)： 根據條件選擇不同的執行路徑。
範例：

IF Score >= 50 THEN
OUTPUT "Pass"
ELSE
OUTPUT "Fail"
ENDIF


3. 重複結構 (Iteration/Loops)： 重複執行一段程式碼。

• 確定次數迴圈 (FOR Loop)： 當你知道迴圈精確執行次數時使用。
  範例： FOR Count = 1 TO 10 DO ... ENDFOR
• 不確定次數迴圈 (WHILE Loop 或 REPEAT UNTIL)： 當重複次數未知，且直到滿足某個條件才停止時使用。
  範例： WHILE UserInput <> "Stop" DO ... ENDWHILE

你知道嗎？ 許多程式語言對偽代碼的規則略有不同。重點在於，無論使用什麼關鍵字，其背後的*邏輯*始終保持清晰。

3. 將偽代碼轉換為高階程式碼 (3.3.3 內容)

接下來的重要技能是將偽代碼中抽象的邏輯，轉換為使用特定的高階語言（如 Python、Java 或 C#）編寫的具體指令。

這一步需要你理解所選程式語言的語法規則，並將偽代碼結構映射到對應的程式碼結構中。

逐步翻譯範例

讓我們將一個計算數字 $N$ 的階乘的偽代碼片段進行轉換。

偽代碼：

Factorial = 1
INPUT N
FOR Count = 1 TO N DO
    Factorial = Factorial * Count
ENDFOR
OUTPUT Factorial

轉換（以 Python 或類似語言為例）：

1. 初始化： 偽代碼設定 `Factorial = 1`。在程式碼中，我們進行變數賦值。
2. 輸入： 偽代碼獲取 `N`。在程式碼中，我們使用輸入函式並確保變數為整數。
3. 迭代： `FOR Count = 1 TO N` 迴圈。在程式碼中，這變成了 `for` 迴圈或其他構造（例如 `for i in range(1, N+1):`）。
4. 計算： 核心計算 `Factorial = Factorial * Count` 幾乎保持不變。
5. 輸出： 顯示結果。

產生的程式碼結構（以 Python 概念為例）：

Factorial = 1
N = int(input("Enter number: ")) # 獲取輸入

for Count in range(1, N + 1):
    Factorial = Factorial * Count

print(Factorial)

挑戰在於確保你所選語言的特定規則（例如 Python 的索引從 0 開始，或是 `range` 函式的運作方式）能夠準確反映偽代碼的邏輯意圖。

4. 演算法的人工追蹤 (3.3.3 內容)

人工追蹤 (Hand tracing) 是使用一組特定的輸入數據，手動模擬演算法執行步驟的過程。這對於在電腦上執行程式碼之前發現邏輯錯誤（臭蟲）至關重要。

為了有效追蹤演算法，我們使用追蹤表 (Trace table)。

追蹤表：你的偵探工具

追蹤表會記錄演算法執行過程中，每個相關變數的值以及產生的輸出。

追蹤表的結構：

• 一欄用於記錄正在執行的演算法行號/步驟。
• 每一欄對應演算法中使用到的變數。
• 一欄用於條件檢查（例如，判斷 WHILE 條件是 True 還是 False）。
• 一欄用於記錄演算法產生的輸出。

鼓勵一下： 如果剛開始覺得這很困難，別擔心！這只需要多練習。追蹤就像閱讀樂譜一樣——你正在訓練大腦完美地遵循流程。

人工追蹤範例解析

以下是輸入 N = 3 的偽代碼追蹤：

1. Factorial = 1
2. INPUT N
3. FOR Count = 1 TO N DO
4.     Factorial = Factorial * Count
5. ENDFOR
6. OUTPUT Factorial

追蹤表：

步驟	N	Count	Factorial	Output
1	-	-	1
2 (輸入 3)	3	-	1
3 (開始迴圈, Count=1)	3	1	1
4 (1 * 1)	3	1	1
3 (下一次迭代, Count=2)	3	2	1
4 (1 * 2)	3	2	2
3 (下一次迭代, Count=3)	3	3	2
4 (2 * 3)	3	3	6
3 (迴圈結束, Count > N)	3	-	6
6	3	-	6	6

追蹤的重要結論：

最終輸出為 6（即 3 的階乘：\(3 \times 2 \times 1\)）。透過仔細記錄 Factorial 變數的每一次變化，我們確認了該演算法對於輸入 N=3 時能如預期般運作。