算法入门：第一步

给从没学过算法的人准备的六节短课：手动追踪一个过程，数它的步骤，读懂大 O，写一个递归函数，论证一个循环是正确的，再用归纳法证明一个命题。所有例子都是 Python，在页面上就能运行。

开始前需要什么

不需要安装任何东西。所有例子都是 Python，直接在本页运行：点代码下方的“运行”。你也可以改动代码再运行一次。
学校里学过的算术：加、减、乘、除，会比较两个整数的大小，知道 2 × 2 × 2 等于 8。
不需要会编程。每个 Python 词第一次出现时都会解释，第 1 课从一个很小的程序开始。
一支笔和一张纸。手动追踪是这里要练的主要本领，写下来才学得会。

什么是算法，以及手动追踪一个算法

学完你能 学完后你能说出什么是算法，并能在纸上照着它一步步做，每一步之后写下每个变量的值。

算法是一串精确的步骤，把输入变成输出。菜谱和它有点像，但菜谱会写“盐适量”，算法不留这样的余地。每一步都必须清楚到一台机器，或者一个不知道目标的人，也能照着做。

谈论一个算法，要说清三件事。输入是放进去的东西，输出是必须得到的结果，步骤是中间发生的事。输入和输出合在一起叫规格说明。它规定算法必须做什么，不规定怎么做。这里的规格说明是：输入是一个至少含有一个数的整数列表，输出是列表中最大的数。

下面是一个解法。先看第一个数，把它叫作“目前最大的数”。然后逐个查看其余的数：如果某个数比“目前最大的数”大，它就成为新的“目前最大的数”。数用完以后，“目前最大的数”就是答案。

追踪的意思是用手扮演计算机。你严格照着步骤做，每做完一步，就写下每个变量此刻的值。变量是贴在一个值上的名字。这里名字 largest 贴在一个数上，而这个数可以改变。追踪通常写成表格，每一步一行。后面的每一课都要用到追踪。只要会追踪，你不必相信任何人，就能弄清算法做了什么。

下面的例子用 Python 写出了同一个算法。Python 是这份指南使用的编程语言。点“运行”看它工作，再从上到下读代码。逐步讲解会解释每一行。

新词

算法: 把输入变成输出的一串精确步骤。
规格说明: 允许的输入和要求的输出。它说明做什么，不说明怎么做。
变量: 贴在一个值上的名字。名字不变，值可以改变。
追踪: 用手一步步执行算法，并在每一步之后写下每个变量的值。
列表: 方括号里排成一行的值，例如 [3, 8, 2]。第一项的位置是 0。
循环: 重复执行的步骤。这里对列表中的每一项各执行一次。

完整例子

Python 3

numbers = [3, 8, 2, 9, 4]
largest = numbers[0]
for n in numbers:
    if n > largest:
        largest = n
    print("looked at", n, "- largest so far is", largest)
print("answer:", largest)

先预测输出，再看结果

预期输出

looked at 3 - largest so far is 3
looked at 8 - largest so far is 8
looked at 2 - largest so far is 8
looked at 9 - largest so far is 9
looked at 4 - largest so far is 9
answer: 9

逐步讲解

numbers = [3, 8, 2, 9, 4] 建立一个含五个数的列表，并给它取名 numbers。单个等号 = 不是数学课上的“相等”，它的意思是“把右边的值放到左边的名字下”。
numbers[0] 是位置 0 上的项，也就是第一项。Python 从 0 开始数位置，所以五项中的最后一项在位置 4。largest = numbers[0] 让 largest 等于 3。
for n in numbers: 把它下面缩进的几行对每一项各执行一次，n 就是当前这一项。向右缩进四个空格的行是循环的主体。Python 靠缩进知道哪些行属于循环。
if n > largest: 提出一个问题。如果 n 比 largest 大，就执行下一行缩进的 largest = n，给 largest 一个新值。如果不大，这一行就跳过。
print(...) 把值显示在屏幕上。它和 if 缩进在同一层，所以每一项都执行一次。最后一个 print 没有缩进，所以只在循环结束之后执行一次。
追踪：largest 起初是 3。3 不比自己大，largest 仍是 3。8 更大，largest 变成 8。2：仍是 8。9：变成 9。4：仍是 9。答案是 9。

常见错误

错误写法

if n = largest:

单个 = 是把值放到名字下，不能用来提问，所以 Python 会以 SyntaxError 停止。要问“两者相等吗？”要写两个等号；要问“n 更大吗？”就写 >。

正确写法

if n == largest:

错误写法

largest = 0
for n in numbers:
    if n > largest:
        largest = n

当所有的数都是负数时，这样写就错了。numbers = [-5, -2, -9] 时，没有哪个数比 0 大，答案一直是 0，而 0 根本不在列表里。应当从列表中真实存在的一项开始。

正确写法

largest = numbers[0]

错误写法

largest = numbers[5]

这个列表有五项，位置是 0 到 4。位置 5 不存在，所以 Python 以 IndexError: list index out of range 停止。最常见的原因是从 1 数起，而不是从 0 数起。

正确写法

largest = numbers[4]

错误写法

for n in numbers:
    largest = n
    if n > largest:
        print("new largest")

先赋值再检验，意味着检验时 n 已经等于 largest，检验永远不会为真。最后 largest 只是最后一项 4，而不是 9。手动追踪一下马上就能看出来。步骤的顺序很重要。

正确写法

for n in numbers:
    if n > largest:
        largest = n

检查自己

在 [5, 1, 7] 上手动追踪这个算法。三项处理完之后，largest 各是多少？
先自己做，再看答案
处理 5 之后：5。处理 1 之后：仍是 5，因为 1 不更大。处理 7 之后：7。答案是 7。
改动算法，让它找出最小的数。最小的改动是什么？
先自己做，再看答案
把 > 改成 <，这样某个数更小时才替换当前的数。再把 largest 改名为 smallest，代码读起来才不会误导人。在 [3, 8, 2, 9, 4] 上答案是 2。
如果 numbers 是空列表 []，会出什么问题？这对规格说明意味着什么？
先自己做，再看答案
numbers[0] 会以 IndexError: list index out of range 失败，因为没有第一项。规格说明必须写明列表至少有一个数。对输入的限制也是规格说明的一部分。

数步骤

学完你能 学完后你能数出算法在某个输入上执行的步骤数，并能说明为什么数步骤而不是数秒。

一个算法有多快？用秒来回答并不好。同一个程序在手机、笔记本和服务器上花的秒数不同，别的程序在运行时花的秒数又不同。所以我们数步骤。一个步骤是一个小动作，例如比较两个数或把两个数相加。步骤数不依赖机器。

数什么由你来选，而且要说明你选了什么。找最大的数时，可以数比较的次数；把列表加起来时，可以数加法的次数。选真正干活的那个动作，并且每次都用同样的方式去数。

步骤数取决于输入规模，也就是数据的多少。对列表来说，输入规模记作 n，即项数。5 项的列表和 5000 项的列表步骤数不同。所以步骤数是一条规则：给它 n，它给出步骤的个数。

步骤数还可能取决于你拿到的是哪一个规模为 n 的输入。以在列表中查找某个值为例。如果这个值是第一项，查找 1 步就停。如果它是最后一项，或者根本不在列表里，查找就要看遍每一项。最好情况是所有规模为 n 的输入中步骤最少的那个。最坏情况是步骤最多的那个。我们通常说最坏情况，因为它是一个保证：算法绝不会比这更慢。

例子用到两个 Python 工具。函数是一组有名字的步骤，用 def 来创建。它的参数是它接收的输入。return 这个词交回一个答案，并立刻结束函数，即使正处在循环中间。计数器是一个变量，从 0 开始，每当你要数的事情发生一次，就给它加 1。

新词

步骤: 你选来计数的一个小动作，例如一次比较。
输入规模（n）: 数据有多少。对列表来说，n 是项数。
最好情况: 所有规模为 n 的输入中，步骤最少的情况。
最坏情况: 所有规模为 n 的输入中，步骤最多的情况。它是“绝不会更多”的保证。
计数器: 从 0 开始的变量，每当被数的事件发生一次就加 1。
函数: 一组有名字的步骤。参数是它的输入，return 交回它的答案。

完整例子

Python 3

def search_steps(items, target):
    steps = 0
    for item in items:
        steps += 1
        if item == target:
            return steps
    return steps

print("size first last missing")
for size in [5, 10, 20]:
    items = list(range(1, size + 1))
    print(size, search_steps(items, 1), search_steps(items, size), search_steps(items, 0))

先预测输出，再看结果

预期输出

size first last missing
5 1 5 5
10 1 10 10
20 1 20 20

逐步讲解

def search_steps(items, target): 开始定义一个函数，它有两个参数：要搜索的列表，和要找的值。下面缩进的行是它的主体。
steps = 0 建立计数器。steps += 1 的意思是 steps = steps + 1，也就是给计数器加一。每看一项就执行一次。
如果这一项等于目标，return steps 交回计数并立刻结束函数。如果循环走完都没有找到目标，最后一行 return steps 交回计数，此时它等于列表的长度。
range(1, size + 1) 给出从 1 到 size 的整数。list(...) 把它变成列表。size 为 5 时，列表是 [1, 2, 3, 4, 5]。
每一行调用函数三次。目标 1 是第一项。目标 size 是最后一项。目标 0 根本不在列表里。
读一读表格。第一列步骤数永远是 1，与规模无关。另外两列永远等于规模。所以最好情况是 1 步，最坏情况是 n 步。

常见错误

错误写法

for item in items:
    steps = 0
    steps += 1

计数器每一轮都被重置为 0，所以最后总是 1。计数器要在循环开始之前设置一次，在循环里面只做加法。

正确写法

steps = 0
for item in items:
    steps += 1

错误写法

if item == target:
    steps += 1

这样数的是有多少项匹配，而不是看了多少项。问题问的是查找要多少步，所以每一个被检查的项都要计数，不管匹配不匹配。

正确写法

steps += 1
if item == target:
    return steps

错误写法

search_steps([7, 2, 9], 7)   # gives 1, so "a search always takes 1 step"

一个输入只显示一种情况，这里是最好情况。要说最坏情况，就得用最坏的输入：目标在最后，或者根本不在。最好、最坏和中间的情况都要试一试。

正确写法

search_steps([7, 2, 9], 9)   # gives 3: try the last item and a missing value too

错误写法

for item in items:
    steps += 1
    if item == target:
        return steps
    return steps

第二个 return 和 if 缩进一样深，所以在循环里面。无论发生什么，函数在第一项之后就结束，每次查找都报告 1 步。最后的 return 应该放在循环之后，和 for 那一行缩进相同。

正确写法

for item in items:
    steps += 1
    if item == target:
        return steps
return steps

检查自己

search_steps([4, 4, 4, 4], 4) 要几步？为什么？
先自己做，再看答案
1 步。第一项已经等于目标，所以 return 立刻执行。其余三项根本没有看。
一个列表有 1000 项。最坏情况下查找要几步？2000 项的列表呢？
先自己做，再看答案
1000 步和 2000 步。最坏情况是 n 步，所以列表加倍，最坏情况的步骤数也加倍。
写一个计数器，数出 [3, 8, 2, 9, 4] 中有多少个数大于 5。你预期结果是多少？
先自己做，再看答案
count = 0，然后 for n in numbers: if n > 5: count += 1。预期结果是 2，对应 8 和 9。这一次加法放在 if 里面，因为这回我们要数的正是满足条件的项。

增长与大 O

学完你能 学完后你能按增长的快慢比较两个步骤数，并能把 O(n) 和 O(n²) 读成关于增长的陈述。

第 2 课给出了 n、2n + 5 这样的步骤数。重要的问题不是某一个 n 的步骤数，而是输入变大时步骤数会怎样。增长指的是 n 上升时，步骤数上升得有多快。

取两个算法。算法 A 每项用 100 步，所以一共 100n 步。算法 B 对 n 项中的每一项用 n 步，所以一共 n 乘 n 步，写作 n²。10 项时，A 要 1000 步，B 只要 100 步，B 看起来更好。100 项时两者打平，都是 10,000。1000 项时，A 要 100,000，B 要 1,000,000。这时 B 已经差了十倍，而且差距还在继续拉大。不管你在 n 前面放多大的固定数，n² 的算法最终都会输给 n 的算法。

所以我们忽略固定的倍数和较小的附加项，只保留增长最快的那一部分。步骤数 3n + 10 的增长像 n，步骤数 n² + 5n + 7 的增长像 n²。大 O 就是用来记这个的记号。写 O(n) 的意思是：只要 n 足够大，步骤数至多是 n 的某个固定倍数。例如，只要 n 不小于 10，3n + 10 就不超过 4n。n = 10 时两者都是 40，之后 4n 更大。这里固定倍数是 4，“足够大”指不小于 10。

要读懂增长，加倍是最快的办法。如果算法是 O(n)，n 加倍，步骤数大约加倍。如果是 O(n²)，n 加倍，步骤数大约变成四倍，因为 2 乘 2 是 4。如果是 O(1)，步骤数完全不变，比如读取列表的第一项。

再认识几个名字。O(log n) 增长得非常慢。可以把它想成：n 可以对半分多少次才降到 1。n = 1,000,000 时只有大约 20 次，因为 20 个 2 相乘大约是一百万。O(n log n) 比 n 稍大一点。O(2ⁿ) 每多一项就翻一倍。1000 个 2 相乘已经有 302 位数字。增长从慢到快：O(1)、O(log n)、O(n)、O(n log n)、O(n²)、O(2ⁿ)。

大 O 描述的是增长，不是秒数，也不是小的输入。n 很小时，增长更差的算法也可能更快。大 O 告诉你的是 n 很大时谁会赢。

新词

增长: n 上升时，步骤数上升得有多快。
大 O，O(...): O(n) 表示只要 n 足够大，步骤数至多是 n 的某个固定倍数。
n 的平方（n²）: n 乘 n。n 加倍，它变成四倍。
O(1): 步骤数固定，与 n 无关。
对半分: 一次次除以 2。降到 1 之前对半分的次数约为 log n。

完整例子

Python 3

print("n A=100*n B=n*n fewer-steps")
for n in [10, 50, 100, 200, 1000]:
    a = 100 * n
    b = n * n
    if a < b:
        winner = "A"
    elif a > b:
        winner = "B"
    else:
        winner = "tie"
    print(n, a, b, winner)

print("doubling n from 1000 to 2000:")
print("A grows by a factor of", (100 * 2000) // (100 * 1000))
print("B grows by a factor of", (2000 * 2000) // (1000 * 1000))

先预测输出，再看结果

预期输出

n A=100*n B=n*n fewer-steps
10 1000 100 B
50 5000 2500 B
100 10000 10000 tie
200 20000 40000 A
1000 100000 1000000 A
doubling n from 1000 to 2000:
A grows by a factor of 2
B grows by a factor of 4

逐步讲解

a = 100 * n 和 b = n * n 算出当前 n 下算法 A 和算法 B 的步骤数。星号 * 表示乘。
if、elif 和 else 组成一串问题。Python 按顺序问，只执行第一个为真的分支。elif 的意思是“否则如果”。这里这串问题用来选出步骤数更少的一个。
看表：n = 10 和 n = 50 时，B 的步骤更少。n = 100 时打平。从 n = 200 起，A 的步骤更少，而且差距越来越大。B 只在输入很小时才占优。
符号 // 做除法并舍去小数部分，结果是整数。用新的步骤数除以旧的步骤数，就得到增长的倍数。
n 从 1000 加倍到 2000 时，A 的步骤数变成 2 倍，B 的步骤数变成 4 倍。这就是 O(n) 与 O(n²) 的区别。

常见错误

错误写法

# steps = 3n + 10, so the algorithm is O(3n + 10)

在 O( ) 里，我们只保留增长最快的部分，并去掉它的固定倍数。步骤数 3n + 10 写成 O(n)。像 3 这样的固定倍数和像 10 这样较小的附加项，都不改变步骤数的增长方式。

正确写法

# steps = 3n + 10, so the algorithm is O(n)

错误写法

print(10 ^ 2)   # prints 8

在 Python 里，^ 不是“乘方”。它按二进制位组合两个数，10 和 2 的结果是 8。乘方要用两个星号。每当你在代码里写 n 的平方时，这一点都很重要。

正确写法

print(10 ** 2)  # prints 100

错误写法

print(10 * 9 / 2)   # prints 45.0

单个 / 总是给出小数，即使答案是整数。步骤数是整数，所以输出 45.0 看上去不对，还可能让后面需要整数的代码出错。整数除法用 //。

正确写法

print(10 * 9 // 2)  # prints 45

错误写法

# at n = 10: n*n is 100 and 100*n is 1000, so "n*n is the faster one"

一个很小的 n 说明不了增长。要在很大的 n 上比较，或者把 n 加倍看倍数。n = 1000 时，n*n 是 1,000,000，而 100*n 只有 100,000。大 O 说的是 n 很大时的情况。

正确写法

# at n = 1000: n*n is 1000000 and 100*n is 100000, so 100*n wins for large n

检查自己

把下面每个步骤数写成最简的大 O 形式：(a) 5n + 20，(b) n² + 50n，(c) 7。
先自己做，再看答案
(a) O(n)。(b) O(n²)，因为 n 很大时 n² 超过 50n。(c) O(1)：固定的步骤数，与 n 无关。
一个算法用 n² 步。在 300 项的列表上用了 90,000 步。在 600 项上大约要多少步？
先自己做，再看答案
n 加倍，n² 变成四倍，所以是 4 乘 90,000，即 360,000。验证：600 乘 600 等于 360,000。
用 Python 在 n = 99 和 n = 101 时分别算出 100*n 和 n*n。每次谁的步骤更少？
先自己做，再看答案
n = 99 时：100*n 是 9900，n*n 是 9801，B 更少。n = 101 时：100*n 是 10100，n*n 是 10201，A 更少。胜者恰好在 n = 100 之后换了人。

从零开始学递归

学完你能 学完后你能读懂并写出简短的递归函数，并能说明它为什么会停下来。

递归的意思是：函数通过对同一个问题的更小版本调用自己来解决问题。会调用自己的函数叫递归函数。

想想数一数队伍里排在你后面的人。你不会自己一个个数。你问身后的人：“你后面有几个人？”那个人再问他身后的人，如此下去。队伍最后的那个人说“没有”，也就是 0。然后每个人对前面的人回答“我的答案加 1”。答案一路传回队伍前面，直到你得到自己的答案。

每个递归函数都需要两部分。基本情形是你能直接回答的最小问题，不需要再调用。递归情形是用函数去解决一个更小的问题，再用那个答案解决较大的问题。如果没有基本情形，或者调用的问题没有变小，调用就永远不会停。

我们的问题是把 1 到 n 的数加起来。把答案叫作 sum_to(n)。基本情形：sum_to(0) 是 0，因为没有东西可加。递归情形：sum_to(n) 等于 n 加 sum_to(n - 1)。例如 sum_to(3) 是 3 + sum_to(2)，也就是 3 + (2 + sum_to(1))，也就是 3 + (2 + (1 + sum_to(0)))。这就是 3 + (2 + (1 + 0))，等于 6。

怎么相信它是对的呢？相信更小的那次调用。写递归情形时，假设 sum_to(n - 1) 已经给出正确答案，再检查你的这一行能不能把它变成 n 的正确答案。然后检查基本情形。第 6 课会把这个习惯变成一个证明。

Python 会记住每一个还在等待答案的调用。例子里每次调用在开始和结束时都会打印，所以你能看到等待中的调用一层层堆起来，再按相反的顺序结束。Python 允许大约一千个调用同时等待，超过就会以 RecursionError 停止。sum_to(n) 的调用次数是 n + 1，所以递归也有步骤数：这个函数是 O(n)。

新词

递归: 函数通过对更小版本的同一问题调用自己来解决问题。
基本情形: 最小的问题，直接回答，不再调用。
递归情形: 对更小的问题调用函数并使用其答案的那一部分。
调用: 函数的一次使用。每次调用都有自己那一份参数。

完整例子

Python 3

def sum_to(n):
    print("start", n)
    if n == 0:
        print("base case, return 0")
        return 0
    answer = n + sum_to(n - 1)
    print("finish", n, "answer", answer)
    return answer

print(sum_to(3))

先预测输出，再看结果

预期输出

start 3
start 2
start 1
start 0
base case, return 0
finish 1 answer 1
finish 2 answer 3
finish 3 answer 6
6

逐步讲解

def sum_to(n): 定义函数。主体的第一行打印“start”和 n 的值，让每次调用都报上自己的名号。
if n == 0: 是基本情形。它打印一条消息，立刻返回 0。不再有后续调用，所以调用链到此为止。
answer = n + sum_to(n - 1) 是递归情形。函数用更小的数调用自己，当前这次调用停在这一行等待，直到那次更小的调用返回。
然后这次调用打印“finish”，return answer 把结果交给调用它的地方。每次调用都有自己的 n，所以各次调用不会混淆各自的值。
从上到下读输出。四行“start”依次是 3、2、1、0：调用一层层堆起来。然后基本情形返回 0。1 的调用以 1 + 0 = 1 结束，2 的调用以 2 + 1 = 3 结束，3 的调用以 3 + 3 = 6 结束。
最后一行 6 来自函数外面的 print：print(sum_to(3)) 显示的是最外层调用返回的结果。

常见错误

错误写法

def sum_to(n):
    return n + sum_to(n - 1)

没有基本情形，所以没有任何东西能让调用停下。Python 等到第一千次调用，然后以 RecursionError: maximum recursion depth exceeded 停止。每个递归函数都需要一种不再调用自己就能返回的情形。

正确写法

def sum_to(n):
    if n == 0:
        return 0
    return n + sum_to(n - 1)

错误写法

return n + sum_to(n)

这次调用用的是同一个 n，问题从未变小。基本情形永远到不了，结果还是同样的 RecursionError。递归调用必须朝基本情形靠近。

正确写法

return n + sum_to(n - 1)

错误写法

def sum_to(n):
    if n == 0:
        return 0
    n + sum_to(n - 1)

最后一行算出了一个数却把它丢掉了，因为没有 return。没有 return 的函数交回 None。所以 sum_to(1) 得到 None 而不是 1，sum_to(2) 则以 TypeError 停止，因为 2 + None 是不允许的。

正确写法

def sum_to(n):
    if n == 0:
        return 0
    return n + sum_to(n - 1)

错误写法

if n == 0:
    return 1

基本情形必须对最小的问题给出正确答案。没有数可加时和是 0，不是 1。有了这一行，每个答案都多了 1：sum_to(3) 得到 7，而不是 6。基本情形一错，建立在它之上的所有答案都会出错。

正确写法

if n == 0:
    return 0

检查自己

手动追踪 sum_to(2)。发生了哪些调用，每个调用返回什么？
先自己做，再看答案
sum_to(2) 调用 sum_to(1)，sum_to(1) 调用 sum_to(0)。sum_to(0) 返回 0。sum_to(1) 返回 1 + 0 = 1。sum_to(2) 返回 2 + 1 = 3。
写一个递归函数 factorial(n)，计算 1 * 2 * ... * n，并且 factorial(0) 等于 1。factorial(5) 是多少？
先自己做，再看答案
def factorial(n): 先写 if n == 0: return 1，然后 return n * factorial(n - 1)。factorial(5) 的答案是 120。基本情形返回 1 而不是 0，因为乘以 0 会让所有答案都变成 0。
调用 sum_to(-1) 会怎样？为什么？
先自己做，再看答案
调用会变成 -2、-3，如此下去，n 永远不等于 0。调用不会停，所以 Python 以 RecursionError 结束。这个函数只适用于 n 不小于 0 的情况，规格说明应当写明这一点。

用不变量说明循环是对的

学完你能 学完后你能用文字写出循环不变量，并用三个问题论证一个循环给出正确答案。

在几个输入上运行算法并看到答案正确，这是测试。测试能证明错误存在，却永远证明不了没有错误，因为可能的输入太多了。要确信一个算法对每个输入都正确，你需要一个论证。对循环来说，标准的论证用的是循环不变量。

循环不变量是关于变量的一句话，在循环每一轮开始时都为真。“不变量”的意思是“不会变的东西”：变量在变，这句话始终为真。对找最大数来说，不变量是：largest 是已经看过的前 i 个数中最大的。

三个问题把不变量变成论证。开始：在第一轮之前，这句话为真吗？保持：如果某一轮之前它为真，这一轮之后它还为真吗？结束：循环停下时，这句话给出了我们想要的答案吗？如果三个回答都是“是”，循环就是正确的。这像一段楼梯：第一级是实的（开始），每一级通向下一级（保持），到了顶上就读出答案（结束）。

还有第四个很容易忘记的问题：循环到底会不会停？永不停止的循环没有答案，不管它的不变量多漂亮。对列表的循环会停，因为每一轮都前进一项，而列表是有限的。

例子把不变量写成了 assert。assert 这一行检查一个断言。断言为真时什么也不发生；为假时，Python 以 AssertionError 停止。在一个输入上检查 assert 仍然是测试，不是证明。证明是用文字回答的那三个问题。assert 的好处是能及早发现错误的不变量。关于代码的两点说明：numbers[:i] 表示列表的前 i 项，max(...) 表示其中最大的一项。这里用 max 只是为了检验我们自己写的步骤。

新词

循环不变量: 关于变量的一句话，在循环每一轮开始时都为真。
assert（断言）: 检查一个断言的语句；断言为假时以 AssertionError 停止。
while 循环: 只要条件为真就重复的循环。
正确: 对每一个允许的输入都给出符合规格说明的答案，而不只是对试过的输入。

完整例子

Python 3

numbers = [3, 8, 2, 9, 4]
largest = numbers[0]
i = 1
while i < len(numbers):
    assert largest == max(numbers[:i])
    if numbers[i] > largest:
        largest = numbers[i]
    i = i + 1
    print("after pass: i =", i, "largest =", largest)
assert largest == max(numbers[:i])
print("answer:", largest)

先预测输出，再看结果

预期输出

after pass: i = 2 largest = 8
after pass: i = 3 largest = 8
after pass: i = 4 largest = 9
after pass: i = 5 largest = 9
answer: 9

逐步讲解

i = 1 表示已经看过一个数，即 numbers[0]。while i < len(numbers): 只要条件为真就重复主体。len(numbers) 是项数，这里是 5。
不变量写成了 assert：largest 是 numbers[:i]，即前 i 项中最大的。这个 assert 位于主体的开头，所以每一轮开始时都会检查不变量。
开始：第一轮之前 i 是 1，largest 是 numbers[0]，它是只有一个数的列表里最大的。这句话为真。
保持：if 这一行把下一个数 numbers[i] 与 largest 比较，于是 largest 成为前 i + 1 个数中最大的。然后 i = i + 1 让 i 加一，对新的 i 这句话又为真。
结束：i 每轮加 1，所以会到 5，循环就停了。i = 5 时这句话说 largest 是全部五个数中最大的，这正是答案。循环之后的 assert 检查了这一点。
输出显示变量在变化的同时，这句话始终为真：例如第一轮之后 i 是 2，largest 是 8，即 3 和 8 中较大的。

常见错误

错误写法

# invariant: largest is one of the numbers in the list

这句话始终为真，但太弱了。循环结束时，它只说明 largest 是列表里的某个数，并没有说它是最大的。有用的不变量必须在结束时给出答案。

正确写法

# invariant: largest is the biggest of the first i numbers

错误写法

while i < len(numbers):
    if numbers[i] > largest:
        largest = numbers[i]

没有任何语句改变 i，所以条件一直为真，循环永远不会停。在这个页面上，运行 8 秒后会被强行停止。对一个不结束的循环，不变量什么也证明不了，所以一定要检查有东西把循环推向结束。

正确写法

while i < len(numbers):
    if numbers[i] > largest:
        largest = numbers[i]
    i = i + 1

错误写法

    if numbers[i] > largest:
        largest = numbers[i]
    assert largest == max(numbers[:i])
    i = i + 1

不变量只保证在一轮开始时和最后一轮之后成立。在一轮的中间，它可能为假。这里 largest 已经看过 numbers[i]，但 i 还没有前进，所以对 [3, 8, ...]，assert 拿 8 去比 max([3])，于是以 AssertionError 停止。

正确写法

    assert largest == max(numbers[:i])
    if numbers[i] > largest:
        largest = numbers[i]
    i = i + 1

错误写法

largest = 0
i = 1

这通不过“开始”这个问题。对 numbers = [-5, -2, -9]，这句话说 largest 是前 1 个数中最大的，也就是 -5，但 largest 是 0。第一个 assert 就以 AssertionError 停止。应当从 numbers[0] 开始，这样第一轮之前这句话就为真。

正确写法

largest = numbers[0]
i = 1

检查自己

用文字写出下面这段代码的不变量：total = 0，然后 for x in numbers: total = total + x。请用“k 轮之后”开头。
先自己做，再看答案
k 轮之后，total 等于前 k 个数的和。开始：0 轮之后 total 是 0，即没有数的和。保持：加上下一个数，就得到前 k + 1 个数的和。结束：所有轮结束后，total 是全部数的和。
一个循环从 i = 0、total = 0 开始，当 i < 4 时重复：total = total + i，然后 i = i + 1。写出一个不变量，并说出循环停止时 total 是多少。
先自己做，再看答案
不变量：total 等于 0 + 1 + ... + (i - 1)，即小于 i 的所有整数之和。i 等于 4 时循环停止，此时 total 是 0 + 1 + 2 + 3 = 6。
朋友说：“我在 100 个列表上运行过，答案全对，所以它是正确的。”为什么这还不够？
先自己做，再看答案
测试只检查你试过的输入，而论证覆盖每一个输入。错误可能藏在没人试过的列表里，比如只有负数的列表，而这正是从 largest = 0 开始会出错的地方。

从零开始学数学归纳法

学完你能 学完后你能通过验证基本情形和归纳步骤，证明关于每一个整数 n 的命题。

有些命题是关于每一个整数的：0、1、2、3，永远数下去。测试只能检查其中一部分。归纳法用两次检查就能证明全部。可以想象一长排多米诺骨牌。如果你能说明第一块会倒，并且每一块倒下时都会推倒下一块，那么每一块都会倒。

用 P(n) 表示关于数 n 的命题。例如 P(n) 可以是“1 + 2 + ... + n 等于 n(n + 1)/2”。归纳法有两部分。基本情形：说明 P(0) 成立，或者说明你关心的最小 n 对应的 P 成立。归纳步骤：任取一个整数 k，假设 P(k) 成立，再说明 P(k + 1) 成立。“P(k) 成立”这个假设叫作归纳假设。

不必担心你假设的东西看起来像要证明的东西。你只对一个数 k 假设命题成立，再用它推到下一个数 k + 1。这又是多米诺：一块骨牌只有在前一块倒下之后才会倒。

下面是例子。命题：1 + 2 + ... + n = n(n + 1)/2。基本情形，n = 0：左边是 0，因为什么也没加；右边是 0 乘 1 再除以 2，也是 0。两边一致。归纳步骤：假设 1 + ... + k = k(k + 1)/2。那么 1 + ... + k + (k + 1) = k(k + 1)/2 + (k + 1)。提出公因数 k + 1，得到 (k + 1)(k/2 + 1)，也就是 (k + 1)(k + 2)/2。这正是 k + 1 对应的公式。所以命题对每一个 n 都成立。

递归和归纳的结构相同。第 4 课的函数 sum_to 有一个基本情形，和一个用到更小答案的步骤。归纳法就是证明这样的函数给出正确答案的方法。证明里的基本情形对应函数的基本情形，归纳假设就是“相信更小的那次调用”这个习惯。

Python 例子用暴力检查的办法验证了基本情形和 100 个归纳步骤，暴力检查就是把一个小范围里的情形全试一遍。这是合理性检查，不是证明。证明是上面的代数，它一次覆盖了所有的 k。

新词

数学归纳法: 用基本情形和归纳步骤，证明命题对每一个整数都成立的方法。
基本情形: 证明命题对最小的数成立，通常是 0 或 1。
归纳步骤: 证明如果命题对 k 成立，则对 k + 1 也成立。
归纳假设: 在归纳步骤中假设命题对 k 成立。
暴力检查: 把一个小范围里的情形全部试一遍。它能找到反例，却不能证明对所有 n 成立。

完整例子

Python 3

def sum_to(n):
    if n == 0:
        return 0
    return n + sum_to(n - 1)

for n in range(5):
    print(n, sum_to(n), n * (n + 1) // 2)

# Base case: n = 0
assert sum_to(0) == 0 * (0 + 1) // 2

# Step: if the formula holds for k, it holds for k + 1.
for k in range(100):
    formula_k = k * (k + 1) // 2
    assert formula_k + (k + 1) == (k + 1) * (k + 2) // 2
print("base case and 100 steps checked")

先预测输出，再看结果

预期输出

0 0 0
1 1 1
2 3 3
3 6 6
4 10 10
base case and 100 steps checked

逐步讲解

sum_to 就是第 4 课的递归函数。第一个循环打印 n、sum_to(n) 算出的值，以及公式 n(n + 1)/2 的值。range(5) 给出 0、1、2、3、4。后两列在每一行都一致。
以 # 开头的行是注释。Python 会忽略它们，它们是写给人看的。“# Base case”下面的 assert 检查命题在 n = 0 时成立，两边都是 0。
第二个循环用具体的数做归纳步骤。对 0 到 99 的每个 k，它取 k 对应的公式值，加上下一个数 k + 1，再检查结果是否等于 k + 1 对应的公式值。
如果有任何一个 assert 失败，Python 会以 AssertionError 停止。因为没有失败，程序打印了最后一行。
注意它没有做什么：它只检查了 100 个 k 的值。而讲解里的代数一次覆盖了所有的 k，这个差别正是证明的意义所在。

常见错误

错误写法

# Claim: n*n + n is odd for every n.
# Step: if k*k + k is odd, then adding 2*(k+1) keeps it odd.   (true)
# So the claim holds for every n.

步骤本身是对的，但基本情形从来没有检查。n = 0 时值是 0，是偶数，所以命题是假的。实际上 n*n + n 对每个 n 都是偶数。只有步骤没有基本情形，就像一排多米诺骨牌，却没有人推第一块。

正确写法

print(0 * 0 + 0)   # 0 is even, so the claim fails at n = 0

错误写法

# n*n + n + 41 is prime for n = 0, 1, 2, ..., 39
# so it is prime for every n

许多次检查成功并不是证明。这个公式对 0 到 39 的每个 n 确实都给出质数，然后就失败了：n = 40 时得到 1681，等于 41 乘 41。只有归纳步骤的论证才覆盖每一个 n。测试能推翻一个命题，却不能证明一个命题。

正确写法

print(40 * 40 + 40 + 41, 41 * 41)   # 1681 1681

错误写法

Assume P(k + 1). Then P(k + 1) is true.

这里假设了归纳步骤本该证明的东西，所以什么也没证明。归纳假设说的是前一个数 k。归纳步骤必须从 P(k) 出发，通过真正的推理（比如上面的代数）到达 P(k + 1)。

正确写法

Assume P(k). Show P(k + 1), using the assumption.

检查自己

用归纳法证明：对 n = 1, 2, 3, ...，1 + 3 + 5 + ... + (2n - 1) = n²。
先自己做，再看答案
基本情形 n = 1：左边是 1，右边是 1²。归纳步骤：假设前 k 个奇数之和是 k²。下一个奇数是 2(k + 1) - 1 = 2k + 1。于是 k² + 2k + 1 = (k + 1)²，这就是 k + 1 对应的命题。所以对每个 n 都成立。
在多米诺骨牌的比喻里，基本情形和归纳步骤分别对应什么？
先自己做，再看答案
基本情形是第一块骨牌倒下。归纳步骤是“一块骨牌倒下，就会推倒下一块”。两者缺一不可：没有第一下推动，什么也不会倒；没有步骤，倒下的过程会中断。
朋友用 Python 循环检查了 n = 1 到 1,000,000，命题每次都成立，他说“这就是归纳法证明”。错在哪里？
先自己做，再看答案
那是暴力检查，也就是测试。归纳法需要基本情形，以及一个对任意 k 都有效的归纳步骤论证。上面“常见错误”里那个看起来总是质数的公式通过了 40 次检查后就失败了，所以一长串成功并不能说明下一个情形也成立。

接下来

接着阅读《算法设计与分析》（COMP2123）课程笔记。它从这里讲的几个想法开始，再讲到列表、树、排序、散列和图。 →

独立整理的学习笔记，不是官方课程材料。