题目标题

智力题:一个国王有10000桶酒,已知有一桶酒是有毒的,喝了之后一定会在23小时~24小时这个时间段死亡(例如0点喝,则23点到第二天0点一定死亡)。现在国王要在48小时后举办一个宴会,需要把这桶酒挑出来,可以用罪犯实验,问最少多少个罪犯?

难度:中级

算法
参考解析
  • 允许混合酒
    解释:一个人可以测试一次,区分2桶酒。也就是两桶酒(分别编号0和1),挑第0桶喝,如果毒发这桶有毒,如果没事,那么第1桶酒有毒。
    一个人喝一次,可以区分2桶酒。 那么n个人,就可以区分 2的n次方桶酒。10000桶需要14个人。 即log2(10000)向上取整。

具体如何喝呢? 要点是:把酒按规律混合起来喝。 我们可以发现这个问题实际上是2进制下一个数需要多少位来表示的问题。每位对应一个人。
把酒编号0到9999,每个酒编号都换成二进制表示,也就是14位数字(0或者1)序列。数字值为1, 那么对应的人,要取该桶酒来喝,当然实际上是把所有需要喝的酒混合起来喝。