从小白鼠到彩票的算法

两篇文章，主要向大家展示了算法对于计算机来说有多重要，多神奇，性能提升效果显著。那二进制算法的思路是如何形成的呢？

我们先从一道有趣的题目开始。

有100瓶药水，其中一瓶是毒药，只要一小滴，就足以让小白鼠24小时内死亡。请问怎么在1天内用最少的老鼠找出这瓶毒药？

先从暴力破解的方法来看，100瓶，每一瓶对应一只小白鼠，即使用100只小白鼠可以找到那一瓶毒药。这种解法，可以看做是将100瓶毒药放到了一条直线的维度，因此，想要减少小白鼠的个数，很简单，提升维度即可。

第二种方法，就是将100瓶毒药，按照横向10，竖向10排列成一个正方形，即二维，此时只需要使用10+10只小白鼠，就可以定位出哪一个位置的是毒药。

按照上述逻辑，想要再减少小白鼠的个数，就需要继续升高维度，我们下面写一下维度与个数的关系表。

由上面的表可以看出，并不是一直提升维度就可以减少小白鼠个数，这是因为每增加一个维度，这个维度上至少需要两只小白鼠，否则没有意义，过量的维度反而会导致小白鼠个数的增加。

那接下来该如何思考呢？

我们换一种思路来思考这个问题，上面我们是通过对100瓶的位置进行升维来实现减少小白鼠的个数，我们再从小白鼠这一边来进行分析。

每一只小白鼠在喝了瓶内液体并经过24小时后，都只有两种状态，死或生。n只小白鼠，状态会有2^n种。从信息论的观点来看，确定毒药所需要的信息量H(d) = -(p1 log p1+p2 log p2+.....p100 log p100)，p1=p2=....=p100=1/100，小白鼠生死的信息量H(s) = -(p1 log p1+p2 log p2+.....p2^n log p2^n)，p1=p2=....=p2^n=1/2^n，H(s) > H(d)，即2^n > 100，n>6.64，所以至少需要7只小白鼠，才可以将那1瓶毒药找出来。

具体方法就是将瓶子的编号1~100，用二进制来表示，二进制的每一位对应一只老鼠，第一只老鼠喝二进制编号的第一位为1的瓶子内的液体；第二只老师喝二进制编号的第二位为1的瓶子内的液体；依次类推。第二天看死掉老鼠在哪一位，将所有位置1，即可查到毒药的位置。

由此可以看出，信息论的思考方法有多么神奇。我们回到之前分析100W注彩票的问题，彩票选号码，实际每一个数也是只有两种状态，选中和未选中。我们从小白鼠的题目推演过来，1-33中选6个数，就可以用二进制来表示，而计算机存储就是用二进制，所以这样计算的效率非常高。