波仔
🧮 第4章 学习算法基础
📄 一句话概括

交换两个变量要借第三个盒子：先存一个，再覆盖，最后放回来。 不借盒子也有两种技巧（加减、异或），但都有代价，日常还是借盒子最清楚。 最大公约数用辗转相除：除数变被除数，余数变除数，直到余数为 0。

📝 本章和前面几章的关系

这一篇两个题都很小，但各带一个重要的道理：交换讲的是「覆盖会丢数据」， 辗转相除讲的是「算法为什么一定会停」。 后者正好回扣第 1 章的好算法两个条件之一：有穷性。 这一篇收尾，第 4 章就齐了。下一章开始讲排序——那些算法全都是这一章套路的组合。

一、交换：为什么非要借一个盒子

a = 3、b = 5，要换成 a = 5、b = 3。 直觉写法是 a = b 然后 b = a。 跑一遍就知道错了：a = b 之后 a 变成 5，原来的 3 已经被盖掉了，再 b = a 就是 b = 5。 两个都成了 5。 所以必须先把 3 存到别处：t = a、a = b、b = t。借一个盒子，三个动作。

这三行的顺序不能换。 这和 3.3 链表的「先接上再断开」是同一个道理：覆盖之前，先把要丢的东西存起来。 教材讲的就是这一种。它是唯一一种不需要额外条件、不会出意外的写法，所以日常就该用它。

二、两种不借盒子的技巧

面试里常问「不用第三个变量怎么交换」。有两种：加减法和异或法。

写法 要不要第三个盒子 代价
借盒子 要 没有代价，最清楚
加减法 不要 两个大数相加可能超出范围
异或法 不要 对同一个变量做会清零

加减法是 a = a+b、b = a-b、a = a-b。原理是「和减一个得另一个」。 它的毛病在溢出：两个很大的整数加一下就装不下了。 Python 里不会溢出（大整数自动变长），但在 C 和 Java 里会。 异或法是 a ^= b、b ^= a、a ^= b。原理是异或两次能还原。 它的毛病是如果 a 和 b 是同一个变量，第一句就把它清零了。

所以这两种都是「技巧」，不是「做法」。省一个变量换不来可读性，也换不来安全。

三、辗转相除：除数变被除数，余数变除数

求 1071 和 462 的最大公约数：1071 除 462 余 147；462 除 147 余 21；147 除 21 余 0。 余数到 0 就停，最后那个除数 21 就是答案。 每一轮只做一件事：把「除数变被除数、余数变除数」，然后重算余数。三行代码就够了。

为什么这样能得到最大公约数？ 因为 a 和 b 的公约数， 和 b 与 a 除以 b 的余数 的公约数完全一样——公约数集合在缩小，但没丢东西。 这句话是欧几里得两千多年前给出的证明。它也是「算法」这个词最古老的样本之一。

四、为什么它一定停得下来

演示里那句观察很关键：每一步的余数一定比除数小。462 到 147 到 21 到 0，数字严格变小。 严格变小、又不可能是负数，所以最多走到 0。它一定会停。 这就是第 1 章「有穷性」的实例：不是靠数次数保证停，是靠每一步都在向终点靠近。

对照一下第 7 章会讲的递归：没有终止条件的递归也会「一直算下去」，但那不是有穷性， 那是死循环——最后靠内存耗尽才被迫停下。 所以判断一个算法靠不靠得住，先问这一句：它每一步是不是都在靠近终点？

五、换个用法：约分与最小公倍数

1071 和 462 同除 21，得 51 和 22。这就是约分。 分数化简、比例化简，本质都是求最大公约数再同除。 最小公倍数也能从它算出来：两数相乘除以最大公约数。1071 乘 462 再除 21，就是它们的最小公倍数。

为什么？因为两数相乘等于「最大公约数乘最小公倍数」。这条关系在数论里是定理，在这里直接当工具用。 所以这一个算法能解决三类问题：约分、化简、最小公倍数。 算法复用率高，往往是因为它抓住了一个更本质的量。

六、动手 Demo：三种交换写法，加一个辗转相除

先用借盒子的办法交换 3 和 5，再试加减法和异或法，三种结果应该一样。 然后用辗转相除求 1071 和 462 的最大公约数，把每一轮打印出来。 最后拿结果去约分。

a, b = 3, 5
t = a; a = b; b = t
print('借盒子', a, b)

a, b = 3, 5
a = a + b; b = a - b; a = a - b
print('加减法', a, b)

a, b = 3, 5
a ^= b; b ^= a; a ^= b
print('异或法', a, b)

x, y = 1071, 462
while y:
    print(x, y, x % y)
    x, y = y, x % y
print('最大公约数', x)
print('约分', 1071 // x, '/', 462 // x)

实跑输出：

--------------------------------------------------------------------
交换变量与最大公约数
--------------------------------------------------------------------


  ① 交换：三种写法
  --------------------------------------------------------------------
  初始：a = 3，b = 5
  借盒子：t = a; a = b; b = t  ->  a = 5，b = 3
  加减法：a = a+b; b = a-b; a = a-b  ->  a = 5，b = 3
  异或法：a ^= b; b ^= a; a ^= b  ->  a = 5，b = 3

| 写法 | 要不要第三个盒子 | 会不会溢出 |
|---|---|---|
| 借盒子 | 要 | 不会 |
| 加减法 | 不要 | 会（两个大数相加超范围） |
| 异或法 | 不要 | 不会，但对同一个变量做会清零 |

  教材讲的是第一种。
  后两种是「不用第三个盒子」的技巧，面试常问，实际写代码还是第一种最清楚——省一个变量换不来可读性。

  ② 最大公约数：辗转相除
  --------------------------------------------------------------------
  求 1071 和 462 的最大公约数：

| 被除数 | 除数 | 余数 | 下一步 |
|---:|---:|---:|---|
| 1071 | 462 | 147 | 继续 |
| 462 | 147 | 21 | 继续 |
| 147 | 21 | 0 | 停，除数就是答案 |

  结果：21
  每一轮把「除数变被除数、余数变除数」，直到余数是 0。最后那个除数就是答案。

  ③ 为什么它停得下来
  --------------------------------------------------------------------
  每一步的余数一定比除数小：462 -> 147 -> 21 -> 0
  数字严格变小，而且不会变成负数，所以最多走到 0。
  这是「有穷性」的一个实例：不是靠数次数，是靠每一步都在向终点靠近。
  第 1 章讲的那两个条件，在这里变成了能验证的东西。

  ④ 换个用法：约分
  --------------------------------------------------------------------
  1071 / 462 同除 21 -> 51 / 22
  分数约分、比例化简、求最小公倍数（两数相乘除以最大公约数），都靠这一步。

①三种交换写法最后都输出 5 和 3。结果一样，过程的风险完全不同。 ②加减法那行用分号把三句写在一行，只是为了省篇幅。 a = a + b 之后 a 已经不是 3 了，b = a - b 才是 3。 ③辗转相除的循环条件 while y 就是「余数不为 0」。 x, y = y, x % y 这一行同时完成了「除数变被除数、余数变除数」。 ④打印出来的三行是每一轮的 (被除数, 除数, 余数)：1071 462 147；462 147 21；147 21 0。 最后 x 停在 21。

30 秒实验

  1. 用辗转相除求 12 和 18 的最大公约数，手算一遍再跑一遍。
  2. 把 while y 换成 while y != 1，会出什么问题？
  3. 求 1071 和 462 的最小公倍数（相乘除以最大公约数），再用另一个办法验一遍。

常见误区

  1. 「交换写 a = b; b = a 就行。」第一个赋值就把 a 的原值盖掉了，结果两个都成了 b。
  2. 「异或法更好，因为不用第三个变量。」对同一个变量做会清零，还不易读。
  3. 「辗转相除会算很多轮。」每轮余数严格变小，最多几十轮就到底。
自测三问（点开对答案） 1. 交换为什么必须借第三个变量？ —— 第一个赋值就覆盖了原值。不先存起来，那个值就找不回来了。 2. 辗转相除每一步在做什么？ —— 除数变被除数、余数变除数，直到余数为 0。最后的除数就是答案。 3. 为什么它一定停得下来？ —— 每一步的余数严格比除数小。数字一直变小、不会为负，最多走到 0。

第 4 章到此结束。 下一章换一个题目：让一堆数据按大小站好队。从最简单的桶排序开始，一路到最快的快速排序。

相关笔记