什么是算法？What Is an Algorithm?

先把定义摆上桌。它读起来有点干，但每一个词都在"卡人"——我们随后会用反例逐个验证。

↑ 三种颜色对应三根"支柱"。点开下面每一根看它到底在要求什么。

记住这个判据："有限 · 无歧义 · 逐步解决问题"，三者缺一不可。下面两个例子，各自砸掉其中一根支柱——看你能不能抓到是哪一根。

出自 Ryan North 的《How to Take Over the World》。要成为超级反派，先得永生——他"贴心"地给了三步。

关键在第二步"停止衰老"。它读起来像一条指令，但今天地球上没有任何人知道该怎么做——它不是一条明确、可执行的步骤。所以整份配方违反了unambiguous。就算第一步能"见第五章"补齐细节，第二步依然让整件事停留在愿望，而不是算法。

这次每一步都清清楚楚、毫无歧义——问题出在别的地方。先玩一玩这个数字游戏。

Collatz 猜想（又叫 3n+1 猜想）：从任意正整数 n 出发，反复执行——

• 若 n 是奇数 (odd)：n ← 3n + 1
• 若 n 是偶数 (even)：n ← n / 2

猜想断言：无论从哪个正整数开始，最终都会掉回 1。 一个小学生都能看懂的规则——却是当今最顶尖数学家都无法证明的难题。先亲手试试它有多"跳"：

注意：27 只是个小数字，却要跳 111 步、冲到 9232 才落地。轨迹毫无规律——这正是它难被证明的原因。

既然数学家搞不定，那我们计算机科学家干脆写个程序：暴力搜索一个反例（一个永远回不到 1 的数）。伪代码如下——每一行你都能翻译成任意语言，完全无歧义：

// 输出：3n+1 猜想的最小反例（如果存在）
CollatzCounterexample()
  n ← 2
  while true do                        // ← 红旗：无限循环
    current ← n
    while current > 1 do
      if current % 2 == 0 then current ← current / 2
      else current ← 3 * current + 1
      if current == n then return n   // 找到反例
    n ← n + 1

祸首是外层的 while true。它的潜台词是："还没找到反例？继续找。" 但——没人知道反例是否存在。如果猜想是对的（反例不存在），这个循环就永远停不下来，违反了 finite。

留给你的练习：内层 while 其实也有隐患。如果某个 current 掉进一个不含 1 的循环，内层同样会卡死——而"这种循环不存在"恰恰是 Collatz 猜想尚未排除的另一半。

算法不是屏幕里才有的东西。它古老、日常，且无处不在。

• 加减乘除 (arithmetic) —— 你小学学的竖式，是古人发明的算法，每一步都有限、无歧义。
• 用现金找零 (making change) —— "先给大面额、再补小面额"就是一套贪心 (greedy) 流程。
• 配对袜子 (sorting socks) —— 从洗衣篮里两两配对，就是一次排序。甚至有正经论文：Defant & Kravitz, "Foot-sorting for socks", arXiv 2022，研究只用一只脚怎么排。

除了"为了毕业"这个诚实的理由之外——

• 计算是理解世界的基础：社交网络、大脑、黑洞、演化……都能用计算的视角看。
• 分析正确性与资源消耗：一个方案对不对、要花多少时间/空间。
• 衡量可行性：哪些问题能高效解决，哪些不能 —— 这就通向 NP-completeness。
• 面试：截至 2026 年 5 月，即便 AI 工具突飞猛进，大厂技术面依然在考算法。
• 纯粹好玩 🎈

学期末你会摸到人类知识的边界。所有问题大致可以分成三块——点开看每一块：

面对任何算法，我们永远按这个顺序问三个问题。顺序不能乱。

为什么顺序不能颠倒？ 打开下面的开关，假装我们先去问"复杂度"——

终于是个货真价实的算法。任务：在数组里找一个元素，返回它最后一次出现的位置。

Input：数组 A[1..n]，以及要查找的 key k。
Output：k 在 A 中最后一次出现的下标；找不到则返回 −1。

LinearSearch(A[1..n], k)
  i ← n                // 从最后一个元素开始
  while i ≥ 1 do
    if A[i] == k then
      return i         // 往回扫，第一个命中的就是"最后出现"
    i ← i − 1
  return −1           // 扫完都没找到

留意一个巧思：它从后往前扫。因为要的是"最后一次出现"，从末尾倒着走，第一个撞上的匹配就一定是最后那个。下面动手跑一遍：

无限次尝试、零压力。只是检验一下理解。