看见个题目，据说是面试题，求大神分析分析

[aias]

10000 桶酒，其中 1 桶是毒酒； 48 小时后要举行酒会；毒酒喝下去会在之后的第 23-24 小时内毒死人；国王决定用囚犯来试酒，不介意囚犯死多少，只要求用最少的囚犯来测试出哪一桶是毒酒，问最少需要多少囚犯才能保证找出毒酒？

BTW:

1. 毒酒喝到就必死，一点点都不行，一个毒酒分子的剂量喝到了都必死好嘛。。。
2. 大家看清题啊， 2 天内必须找出来，还有 1 天的毒发周期，找不出来国王的酒会没法办了
3. 死的人是没办法继续验酒的
4. 必须验出具体是哪一桶酒，其他 9999 桶酒酒会上都会被喝掉，少一桶都不行，不然酒不够，酒会上和酒会后国王请来的贵宾不允许出任何事故
5. 方案必须能保证到最后一定能验出来，毕竟任何极端情况都有可能，绝对不能靠运气，国王的酒会输不起，只有 2 天时间

[neosfung]

构建一个 20*20*25 的三维数组这个三维数组
找 20+20 个囚犯

在第 0 小时，取前面的 20*20=400 桶酒
填在这个 20*20 的表格里
20 名囚犯负责横排， 20 名囚犯负责竖排
负责横排的囚犯就喝他所在横排的酒
负责竖排的囚犯就喝他所在竖排的酒
每一个小时试下一批
如果在某个时间段内有囚犯死了，必然是两个囚犯
这样就可以推测出之前是喝的是哪个时间段的酒，喝的是哪一桶

综上所述，需要 40 名囚犯，最后死两名囚犯

[fg607]

一个人间隔一小时喝一桶，因为毒发在 23-24 小时之后， 48 小时内要验出，所以每个人在 24 小时内最多检验 25 桶酒，总共 500 桶，需要 500/25=20 个人。

但这不一定是最少的答案，但比一楼的少^_^

[fg607]

搞错了，楼主是 10000 桶酒，不是一个题目-_-#

[fg607]

一楼的方法很牛逼，但不是最少的，在一楼的基础上可以优化，设置 20*20 人的排列，但最后一列不安排人喝，结果会出现死两个人和死一个人的情况，都可以判断哪一桶有毒，所以最少时 39 人。

[fg607]

好了，更严谨的来了， C(28,2)+28=406>400,最少 28 人。

[fg607]

标准答案应该是 C(N,1)+C(N,2)+C(N,3)+........C(N,N)>=400

[neosfung]

好吧，再给个可用的答案
同样，将 10000 桶酒分为 25 组，每组 400 桶
找 9 个囚犯，每个囚犯按照 1 ， 2 ， 4 ， 8 ， 16 ， 32 ， 64 ， 128 ， 256 编号
嗯，到了这个套路，相信程序员都很熟悉了。。。

[beijiaoff]

@fg607 是谁告诉你标准的。。。
出题人说下面的方法差不多接近标准了：
3 个人，因为 25^3>10000 
  
把酒按 25 进制编码，然后按照编码，例如 xyz 号酒 
在第 x 个小时喂给第一个奴隶 
在第 y 个小时喂给第二个奴隶 
在第 z 个小时喂给第三个奴隶 
  
然后，看啥时候病发，倒推 xyz ，转成十进制就是第几桶酒了。