程序员入伙书——初涉算法

在以后的讲解里，会陆陆续续地涉及到许多算法。所以这里先给大家心里垫个底儿。如果你没有看明白这一节，不用很担心。

在“程序在干什么？”一节的最后，我举了一个例子，来说明程序具有计算、流程控制、输入输出三个功能块。这个例子是“求”一个数字的平方根，但它不是在“算”，而是在“猜”。

如果我给它的数是3，它就先猜：1.5！然后自己验算一把：1.5 x 1.5 = 2.25，太小。于是它就再猜：2.25！（就是位于1.5和3正中间那个数）验算一下：2.25 写2.25 = 5.0625，太大。再猜：1.875！——1.5太小，2.25太大，那一定在它们之间了。1.875是1.5和2.25的平均值。1.875 x 1.875 = 3.515625，又大了些，不过大家可以注意到，数字开始接近3了。于是它再取1.875和1.5的平均值……如此反反复复地接着猜下去，可以预知，猜测的结果必然会越来越逼近3的平方根。

我们都知道，第一、计算机无法精确表达实数。第二、即使从完美的数学上说，3的平方根是一个无理数，也不可能通过有限次的有理数四则运算实现。所以我就对程序说，你也不用太自责，只要误差小于亿分之一，你就可以从循环里退出来了。这样就不会出现这种情况：由于结果的平方总是不能精确等于3，程序过于内疚而陷入无限循环的困境。

现在咱们往那个程序里加两条调试语句：

print('Please input a number: ', end = '')
n = abs(float(input()))
high = max(1, n)
low = 0
while True:
    result = (high + low) / 2
    print('What about %.10g?' % result)
    print("%.10g x %.10g = %.10g" % (result, result, result * result))
    if abs(result * result - n) < n * 1E-8:
        break
    if result * result > n:
        high = result
    else:
        low = result
print('Square root of %g is %g' % (n, result))

再来跑一下，看看每次循环的中间结果。

Please input a number: 3
What about 1.5?
1.5 x 1.5 = 2.25
What about 2.25?
2.25 x 2.25 = 5.0625
What about 1.875?
1.875 x 1.875 = 3.515625
What about 1.6875?
1.6875 x 1.6875 = 2.84765625
What about 1.78125?
1.78125 x 1.78125 = 3.172851562
What about 1.734375?
1.734375 x 1.734375 = 3.008056641
What about 1.7109375?
1.7109375 x 1.7109375 = 2.927307129
What about 1.72265625?
1.72265625 x 1.72265625 = 2.967544556
What about 1.728515625?
1.728515625 x 1.728515625 = 2.987766266
What about 1.731445312?
1.731445312 x 1.731445312 = 2.99790287
What about 1.732910156?
1.732910156 x 1.732910156 = 3.00297761
What about 1.732177734?
1.732177734 x 1.732177734 = 3.000439703
What about 1.731811523?
1.731811523 x 1.731811523 = 2.999171153
What about 1.731994629?
1.731994629 x 1.731994629 = 2.999805395
What about 1.732086182?
1.732086182 x 1.732086182 = 3.000122541
What about 1.732040405?
1.732040405 x 1.732040405 = 2.999963965
What about 1.732063293?
1.732063293 x 1.732063293 = 3.000043253
What about 1.732051849?
1.732051849 x 1.732051849 = 3.000003609
What about 1.732046127?
1.732046127 x 1.732046127 = 2.999983787
What about 1.732048988?
1.732048988 x 1.732048988 = 2.999993698
What about 1.732050419?
1.732050419 x 1.732050419 = 2.999998653
What about 1.732051134?
1.732051134 x 1.732051134 = 3.000001131
What about 1.732050776?
1.732050776 x 1.732050776 = 2.999999892
What about 1.732050955?
1.732050955 x 1.732050955 = 3.000000512
What about 1.732050866?
1.732050866 x 1.732050866 = 3.000000202
What about 1.732050821?
1.732050821 x 1.732050821 = 3.000000047
What about 1.732050799?
1.732050799 x 1.732050799 = 2.99999997
What about 1.73205081?
1.73205081 x 1.73205081 = 3.000000008
Square root of 3 is 1.73205

这样，计算机的掰着手指头猜的过程就昭然若揭了。我们可以看到，它猜了28次，最后总算是找到了一个误差小于亿分之一的值。这个结果和根号3的实际值（1.73205080756887……）已经十分接近了。

如果在高考试卷里让求根号3，我们在答题纸上密密麻麻地写下了上面的28次猜测，那肯定是要吃鸭蛋的。可在程序员的世界里，这种事情十分稀松平常。只要是能得到结果的方法，不管是正着算还是倒着推，都是正确的方法。任何能够对于特定问题得到预期结果的计算机方法，都叫做“算法”（英文叫做Algorithm）。各种算法所不同者，是它们解决问题的效率。以这个平方根的程序为例，只循环28次，把误差限制在亿分之一以内，效率还算不错（这个算法叫做“二分查找”）。比这样猜一辆汽车的价钱好：一块？低？两块？还低？三块？……都猜了34179次了，还嫌低？喵了个咪的，不猜了！

注：平方根的标准算法是用泰勒级数展开，并非像我这样，二分查找反复验算。我在这里只是演示一下算法的奇妙：只需要求二十几次平均数就能算出平方根，还是很有趣的。

一个关于高斯的传说，老师罚全班同学做一道题：从1加到100，不做完不要回家。许多学生立刻开始埋头猛算，他们的算法是：

total = 0
for i in range(1, 101):
	total = total + i
print('1+2+3+...+100 = %d' % total)

运行结果：

1+2+3+...+100 = 5050

高斯思考之后认为，1+100等于101，2+99等于101，3+98等于101，……，50+51等于101，总共50个101，总和等于5050，当场秒杀老师。高斯总结的是等差数列总和的通项公式：(first + last) x n / 2。能用一个公式搞定的算法，运行速度和数据量的大小无关，是最佳算法。我写的这个二分查找平方根的，效率和所要求的精度成对数增长关系：万分之一的精度需要循环15遍，亿分之一的精度需要循环28遍，也堪称上品。

随着数据量的增长，耗时线性增长的，使人略感疲惫，但也算合理的。像高斯的同学们用的就是这个算法。

九九乘法表的算法，随着行数的增长，需要花费的时间呈平方量级飙升，就不能说是个好算法，不过这道题目真没有改善方案。最恐怖的算法是耗时呈指数增长的，例如下棋程序，每走一步棋，假设对手有5种回应可能，而针对对手的每种回应，自己又有5种回应。这样，一来一往就有25种可能的下法。如果想赢得棋局，需要多预测几个回合，穷举种种可能，到古今棋谱里猛翻，选最终赢面最大的。如果想预测五个回合，就需要翻5的10次方，即9765625个棋谱。更何况“每步棋有5种应对方案”，真是往少里说了。