谁毒死了酋长

出题

很久以前有一个大草原上最强的部落，其他部落的首领每年在酋长生日的一天会向他进贡。有一天进贡来了100人，每人送来了一个食物，酋长吃了其中一个食物后，口吐白沫暴毙而亡。

问题

国师希望通过最少的侍卫，最短的时间能够知道是哪一个食物有毒。

解析

每一个算法题都不是凭空来的，比如这道题的解，可以用在我们多线程处理任务的时候，用最少的线程，最短时间内得出结果。

方法

1. 最简单的是100种食物，100个侍卫，每人试一个，死亡的侍卫的食物就是有毒的食物。

但是这种基本不给分。

1. 采用分段法，将食物分层N段，M个侍卫进行实验，不断缩小分段数目，得出有毒的食物。

但这种方案在于分段数目越少，耗时越长。

1. 采用二进制方式，比如100个食物，2^7 > 100，于是我们可以找7个侍卫，标号1-7，每种食物编号用二进制表示，不足7位的位置用0代替。

7个侍卫在食物二进制中1位置的侍卫吃一口，如果能定位到最终死掉侍卫的1的位置，就可以定位食物的编号了。

比如死掉的侍卫是：5，6，7，二进制表示是：0000111，就表示食物编号为7的食物有毒。

© 著作权归作者所有