读书笔记---程序员的数学07------指数爆炸，如何解决复杂问题。重点：1，指数爆炸威力太大，小心指数爆炸。2，利用指数爆炸(二分查找有效的利用了指数爆炸)
@课前对话：
老师：假设现在有一张非常柔软的纸，厚度为1mm。对折多少次后厚度能达到地球到月球的距离呢？
学生：100万次左右吗？
老师：不对。
学生：还要更多？
@本章内容
1，所谓指数爆炸，其实不是真的爆炸。指数爆炸是指数字呈爆炸式增长。
如果遇到的问题中包含指数爆炸就要多加注意了。因为一旦处理不好，该问题可能会膨胀到难以收拾的地步。相反，若能巧妙利用”指数爆炸”，它将成为解决难题的有力武器。
2，什么是指数爆炸?首先来实际体验一下指数爆炸的威力吧。
思考题(折纸问题)
假设现在有一张厚度为1mm的纸，纸质非常柔软，可以对折无数次。每对折1次，厚度便翻一番。
已知地球距月球约39万公里，请问对折多少次后厚度能超过地球月球距离呢？
提示
这个问题看上去有点异想天开。即从1mm开始，反复进行厚度翻倍的”倍数游戏”，要重复多少次才能超过39万公里。
在计算前，我们先凭感觉估计一下对折多少次能到达月球，100万次会不会太多了？1万次差不多吧？你觉得对折几次合适呢？
3，程序中复选框测试引起的指数爆炸。
4，二分法查找——利用指数爆炸进行查找(二分查找有效的利用了指数爆炸)
—不明白，就看下边的实例和总结。
上面我们已经体会到了指数爆炸的厉害，这次就来思考如何借助指数爆炸的力量吧。
—注意，这里是在理想情况下，犯人都知道谁是罪犯，而且犯人说的都是实话。
—用折半查找方法，问3次话就能问出来，第一次，问中间的人。就剩下7个人，第二次，问中间的人，还剩3个人。第三次必定都得到答案。具体思路，看下边的图形：
—就像指数爆炸一样，一次能筛选掉一半的人。
版权声明：本文为feichengwulai原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。