问题描述

国王有一百桶酒，比自己的生命还重要。结果有一天其中一桶被投了慢性毒药，喝了以后半个小时以后就会死掉。国王大怒，命令玩忽职守的侍卫去试毒。酒不能被混合，一个侍卫可以喝多桶酒，一桶酒也可以由多个侍卫喝，怎么样才能用最少的侍卫、在最短的时间知道哪桶是毒酒。侍卫可以理解为线程，即怎么样用最少的线程用最快的速度完成这个工作。

方案

最简单的方案肯定是找100个人，每个人试一桶酒，那么用时30分钟，就可以判断出哪一桶就有毒。
再进一步的，可以使用分段法，把酒分成n(n>=2)份，先找n个侍卫试酒，可以定位出哪一段的酒有毒，再接着分段试酒。但这种方案，分段数目越少，试出毒酒的平均耗时就越长。每次分成两份，时间最久。
如果用计算机的思维来分析这个问题，那么首先考虑如何存储这100桶酒。100桶酒可以用二进制7个bit来表示（2^7>100）。对酒进行编号1-100，对侍卫编号1-7。对于每一桶酒的二进制表示，不足七位前面用0表示，从第一位到第七位，如果对应的二进制位表示为1，则相应编号的侍卫喝此桶酒。30分钟后，侍卫按照编号1-7，死掉的置为1，活着的置为0，假如死了编号为1 5 6的侍卫，那么有毒的酒为0110001就表示第49桶酒为毒酒。
侍卫死的最少的情况是毒酒恰好位于2的幂时，比如第64桶 第16桶的情形。当是第63或者95桶时此时要死6个侍卫。
这道题主要从计算机二进制的思想去解决特定情形下的问题，能否脱离10进制转换问题到二进制表示，是解决该问题的关键点。