欢迎来到算法的世界！
欢迎来到 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}\) 规则）。
如果这些步骤一开始看起来很繁琐，别担心！决策数学的关键在于有条不紊。善用铅笔，慢慢来，并记得反复核对你的交换步骤！