歡迎來到演算法的世界！
歡迎來到 D1 單元：決策數學 1 (Decision Mathematics 1)。我們將從演算法 (Algorithms) 開始。別被這個名字嚇倒了——演算法其實就是解決問題的一套「逐步指南」。想像它就像烤蛋糕的食譜，或是組裝樂高積木的說明書一樣。只要你嚴格按照步驟執行，每次都能得到正確的結果！
在本章中，我們將學習如何描述這些指令，並探討處理數據的特定方法，例如裝箱、排序和搜尋。這些技術在日常生活中被廣泛應用，像是 Amazon 利用它們來裝載貨車，或是 Google 用它們來篩選搜尋結果。
1. 到底什麼是演算法？
演算法是一系列有限的、精確的指令，用以導出解決方案。在考試中，演算法通常以兩種方式呈現：
1. 文字指令：帶編號的步驟清單。
2. 流程圖 (Flow charts)：步驟的視覺化圖解。
流程圖符號
要閱讀流程圖，你只需要了解圖形的含義：
• 橢圓形：開始或結束。
• 長方形：指令（例如：「將 X 加 1」）。
• 菱形：決策（例如：「X 是否大於 10？」）。這些圖形總是會分出「是」和「否」的箭頭。
快速回顧：演算法必須是有限的（必須有結束）、精確的（不准猜測！），以及有效的（必須能解決問題）。
2. 裝箱演算法 (Bin Packing Algorithms)
想像你有一堆不同重量的物品，需要將它們裝進容量有限的箱子裡。目標是盡可能使用最少的箱子。這就是所謂的裝箱問題 (Bin Packing Problem)。
方法 A：首次適應法 (First-Fit)
這是最「偷懶」的方法。按照給定的順序，將每個物品放入第一個有足夠空間的箱子中。
陷阱：你必須永遠由第 1 個箱子開始檢查，接著第 2 個、第 3 個，以此類推。千萬不要因為上一個箱子看起來滿了，就直接跳過它去找新的箱子！
方法 B：首次適應遞減法 (First-Fit Decreasing)
這種方法通常更有效率。
1. 首先，將物品按降序（從大到小）排列。
2. 然後，對這個已排序的清單執行首次適應法 (First-Fit)。
比喻：如果你在收拾行李箱，你會先放入大靴子，之後再用襪子填補縫隙！
方法 C：滿箱法 (Full-Bin)
這是「拼圖」式的方法。你需要尋找能剛好填滿箱子的物品組合。
範例：如果箱子容量為 10，你有 7、3、4 和 6 的物品，你可以配對 (7+3) 和 (6+4)，完美填滿兩個箱子。
重點總結：「首次適應法」很快但比較凌亂。「首次適應遞減法」通常較佳，但需要先對清單進行排序。「滿箱法」效果最好，但在清單很長時會變得困難。
3. 排序演算法 (Sorting Algorithms)
有時候我們會拿到一堆雜亂無章的數字，需要將它們按順序排列。這時我們就需要使用排序演算法。
氣泡排序法 (Bubble Sort)
想像氣泡在汽水中上升的過程。最大的數字會一個一個「沉」到清單的最末端。
運作方式：
1. 比較前兩個數字。如果第一個比第二個大，就交換 (swap) 它們。
2. 移動到下一組（第 2 和第 3 個），重複步驟。
3. 當你到達清單末端時，最大的數字就已經在正確的位置了。這稱為一趟 (pass)。
4. 重複進行各趟掃描，直到某次掃描過程中完全沒有交換發生為止。
快速排序法 (Quick Sort)
對於長清單來說，這種方法快得多。它使用一個基準值 (pivot) 來分割清單。
Edexcel 重要規則：考試時，基準值 (pivot) 永遠是清單的中間項。如果項目總數為偶數，則選擇中心點右側的項目。
步驟：
1. 選出基準值。
2. 建立兩個子清單：比基準值小的物品放到左邊；比基準值大的物品放到右邊。
3. 對每個子清單重複此過程，直到每個物品都曾作為基準值為止。
記憶口訣：「選取、分割、重複！」
常見錯誤：在快速排序法中，當你將物品移到基準值的左側或右側時，不要改變它們原有的相對順序。如果 '5' 在原始清單中位於 '3' 之前，且兩者都小於基準值，那麼在新的子清單中，'5' 仍應位於 '3' 之前。
4. 搜尋演算法：二分搜尋法 (Binary Search)
如果你擁有一個已排序的清單，你可以使用二分搜尋法極速找到特定項目。
比喻：如果你要在字典裡找「Mathematics」這個詞，你不會從第 1 頁開始翻。你會翻開中間，看看自己找得太前還是太後，然後直接捨棄不需要的那一半！
如何找到中間項
課程大綱要求使用特定的方法。如果一個清單有 \(n\) 個項目：
中間項的位置是 \(\frac{n+1}{2}\)。
如果這不是一個整數，請無條件進位 (round up)。
範例：在一個有 10 個項目的清單中，\(\frac{10+1}{2} = 5.5\)。無條件進位到 6。第 6 個項目就是你的中間項。
二分搜尋法步驟：
1. 找到清單的中間項。
2. 如果這正是你要找的項目，停止。
3. 如果你要找的項目比中間項小，捨棄中間項及其右側的所有項目。
4. 如果你要找的項目比中間項大，捨棄中間項及其左側的所有項目。
5. 對剩餘的「一半」重複此過程，直到找到該項目或清單變空（代表該項目不存在）。
快速回顧：
• 先決條件：清單必須先經過排序，才能使用二分搜尋法。
• 如果清單是亂的：你必須先使用氣泡排序或快速排序！
• 效率：二分搜尋法極快，因為它每次都將搜尋範圍減半。
總結檢查表
在進入下一章之前，請確保你能夠：
• 解釋什麼是演算法。
• 準確地依照流程圖或文字指令執行操作。
• 使用首次適應法 (First-Fit) 和首次適應遞減法 (First-Fit Decreasing) 進行裝箱。
• 執行氣泡排序 (Bubble Sort)（記得直到某一趟完全沒有交換才能停止）。
• 執行快速排序 (Quick Sort)（永遠選中間項作為基準值）。
• 使用二分搜尋法 (Binary Search) 在排序後的清單中搜尋（記得 \(\frac{n+1}{2}\) 規則）。
如果這些步驟一開始看起來很繁瑣，別擔心！決策數學的關鍵在於有條不紊。善用鉛筆，慢慢來，並記得反覆核對你的交換步驟！