Python-近似解与两分查找

还记得我们前几天谈到过的计算一个数的平方根吗？你找到方法了吗？如果你在没有任何启发下，找到了计算一个数的平方根，那么你已经和古代的数学家们相提并论了。据记载，亚历山大利亚的希罗是第一个记录如何计算一个数的平方根的人，当然，也有说法是古巴比伦人就知道这个算法，反正什么事情都有古巴比伦的份。

小编，不老编遇到这个问题时，也是想了相当一段时间，要知道，老编小时候数学（那时候叫算数吧）很牛的，尤其是心算，在一个自然村里面相当有名。山外有山，现在已经没有那种感觉了。偶尔在自己家里还能冒充一下计算高手。

一个人终其一辈子也不一定能够发明一种算法，这个很正常。同时也不妨碍我们事业成功，因为我们可以使用大师们已经发明的算法来解决问题。这不是我先说的，是教这门课程的老美教师说的，应该相当权威。

希罗的算法（方法，解法）是这样的，随机选择一个数g, 如果g*g和数x足够接近，停止运算并宣布g是答案（平方根）；否则，取g和x/g相加后的平均值，也就是(g+x/g)/2, 使用这个新数来代替g, 然后重复上面的整个过程。当然，这是计算机版的希罗算法语言表述的。

你能把它变成python程序（代码）来计算吗？如果你是初学者，没有搞出来，没有关系。下面就是我的代码，请参考：

解释如下：

import random 如果你能help一下，那就就已经学会怎么自学了。import语句将random模块导入，random模块里面有个randint方法能够将它后面括号内的数字范围内生产一个随机整数。比如上面的（1， 25）在这个范围里生成一个随机整数，然后赋值给ans，作为猜测的答案。

x = 25，我们要求这个数的平方根。

怎样就算找到这个数了，我们定义说，接近，要量化这个接近，就用epsilon，一个小的数字，这里定义为0.01，如果猜测的数字减去25的绝对值小于0.01，那么我们就宣布找到了这个数的平方根。

while 后面就是上面说的意思的代码化，只要没有小于epsilon, 就循环做希罗的方法。

当你第一次做类似的代码运行，你一定会有一些吃惊，分明25的平方根是5，初中生都知道，怎么会是那么一个小数？这就是计算机和理论的区别，计算机是工程类的计算，不同的方法，出现的结果不同。请自行思考或者干脆记住不用思考。

到这里，我们已经了解了今天的题目--近似解。我们再看书上的例子：

解释：

和第一张图相似的不再解释。

这是使用的穷举法，就是从0开始，没个一个step大小的数字，连续寻找。比如，0，0.1,0.2，。。。1.9,2.0 就找到了4的平方根。当然上图的例子中step很小,所以步数很多。

numGuesses，是计数步数的变量名。

如果ans的平方和数x的差大于等于epsilon就继续下面的循环，直到小于就停下。加了一个ans x就不符合这个判断了。如果不是对数学太感兴趣，跳过就好。

+= 表示numGuesses = numGuesses + 1的意思。每循环一次，加1;

结果也是让你吃惊的小数。

这种穷举法，步子(step）一定要小，否则会错过答案，也要兼顾运算次数，如果步子太小，运算次数会太多。假如可能，要多多测试各种步子，看看计算速度如何，要知道计算机每秒是亿次以上的。

作者特别指出，寻找平方根的方法和你在中学里学过的并不一样，通常来说，使用计算机来解决问题的最佳方法和手工方法完全不同。这可是教授的原话，我们要充分意识到。

我们再看即熟悉又陌生的两分法算法：

凡是人都应该读过书，而查字典是免不了的，只不过查传统字典的可能越来越少了。我们仍然以使用传统英语字典为例。假如单词python我们不认识，需要查字典。你一定是先翻开字典，看字母是什么，根据情况要么向前要么向后，极少情况是本页。事实上这就相当于把字典分成了前后两部分，然后在包含P的部分继续查找，再随机翻开这一部分，再分成两部分，重复上面的做法，查到为止。

如果将上面的过程抽象，那么就是两分查找。也就是说，我们先把搜索空间分成两部分，然后继续这个过程，每次循环都是分成两部分，所以叫两分查找。至于怎么分法，目前我们还不关心。只要知道这个两分概念就行了。下图是两分查找的一个例子，请注意和前面的方法比较。特别是比较使用了多少步骤得出的平方根，要用不同的数测试。

如果一时看不懂，可能是没有理解将ans赋值给low或者high，结合图中下面的输出，一步步在纸上比划比划。慢慢琢磨，总能理解的。

好，今天就到这里。