算法

它是什么

算法 是解决问题的步骤。 步骤要清楚。 做完能停下来。 电脑才能照着跑。

食谱是算法。 上学路线是算法。 「先洗手，再打开课本，再写练习」也是算法。 关键有三条：每一步够明确、顺序对、不会永远做不完。

程序是算法的一种写法。 算法还可以先用中文、用图画出来。 中文对了，写成程序才容易对。

名字从哪来

算法的英文是 algorithm。

大约公元 9 世纪，波斯学者花拉子米（Muḥammad ibn Mūsā al-Khwārizmī）在巴格达写了算术和代数的书。 他的名字传到欧洲，拉丁文写成 Algoritmi。 后来人们用这个词称呼「按步骤算」的方法。 algebra「代数」也和他的书名有关。

所以算法不是电脑发明以后才有的。 先有人把计算写成步骤，很久以后才有机器去执行这些步骤。

电影《隐藏人物》（Hidden Figures，2016）讲三位女性在美国航天局做计算。 那时很多「计算机」其实是人。 她们用纸笔和清楚的步骤，算出飞船该走的路。 那也是算法。

它怎么工作

写算法时，注释 特别有用。 先用中文写出步骤。 再翻译成代码。

三种简单算法：

1. 枚举：把可能的情况都试一遍
2. 顺序查找：从左到右一个一个问
3. 二分查找：在有序列表里折半找

后两种详见 查找。

枚举

两数之和是 10，加数都在 1 到 9：

# 枚举所有可能的 a、b
for a in range(1, 10):
    for b in range(1, 10):
        if a + b == 10:
            print(a, b)

这用到 嵌套循环。 可能不多时，枚举很可靠。 可能很多时，会比较慢。

顺序查找：

1. 假设还没找到
2. 从左到右问每一个
3. 问到了就记下，并可以提前停

二分查找还要求列表已经排好序。 每次看中间，丢掉一半。

好算法不但要对，还要能停。 死循环不是算法，是陷阱。 见 while 循环。

找 bug 时，算法对、代码错，也很常见。 要配合 调试。 代码能跑、结果不对，则可能是算法本身想错了。

生活里在哪里

• 查字典：先翻到大概的字母，再在这一页里找。有点像先粗分再细分。
• 图书馆找书：按分类号一层层缩小范围。
• 分糖果：每人两颗，剩下的放回盒。这是整除和取余的步骤。
• 比赛淘汰：每轮去掉一半选手，有点像二分那种「缩小范围」。
• 导航软件：背后是更复杂的寻路算法。

CS Unplugged《不插电的计算机科学》专门用身体和卡片做这些步骤。 不一定要开机。

和相近概念的差别

算法是办法。 程序是办法写成某种语言。 函数 是把办法打包进一个名字。

同一个算法，可以用 Python 写，也可以用别的语言写，还可以只画流程图。 换语言，算法还在。

循环 和 分支 是零件。 算法是用零件搭起来的完整办法。

快和慢也是算法的差别。 枚举可能把所有组合都试完。 二分在有序数据上通常少问很多轮。 先对，再谈快。

常见误会

误会 1：算法等于很难的数学公式。

清楚的步骤就是算法。 食谱也算。

误会 2：程序能跑，算法就一定对。

跑得通只说明语法过关。 结果还要对照步骤检查。

误会 3：枚举范围写错，漏了边界。

range(1, 10) 不含 10。 边界要单独想清楚。

误会 4：列表还没排序，就直接二分。

前提不成立，办法会错。

误会 5：找到目标后还让循环空转很多圈。

可以 break。 能停就停，是算法的美德。

想知道更多

• 电影：《隐藏人物》（Hidden Figures）。看「人当计算机」时，步骤怎样被写清楚。这是根据真实故事改编的电影，不是编程教材，但能看见计算有多重要。
• 书：阿迪特亚·巴尔加瓦《算法图解》（Grokking Algorithms）。后面几章偏难，可以只和家长一起看前几章的图画。
• 书：潘洪波《小学生 Python 趣味编程》（用枚举、查找这类小问题练「先想步骤，再写代码」）。