这是一个创建于 2854 天前的主题，其中的信息可能已经有所发展或是发生改变。
10000 桶酒，其中 1 桶是毒酒； 48 小时后要举行酒会；毒酒喝下去会在之后的第 23-24 小时内毒死人；国王决定用囚犯来试酒，不介意囚犯死多少，只要求用最少的囚犯来测试出哪一桶是毒酒，问最少需要多少囚犯才能保证找出毒酒？
BTW:
- 毒酒喝到就必死，一点点都不行，一个毒酒分子的剂量喝到了都必死好嘛。。。
- 大家看清题啊， 2 天内必须找出来，还有 1 天的毒发周期，找不出来国王的酒会没法办了
- 死的人是没办法继续验酒的
- 必须验出具体是哪一桶酒，其他 9999 桶酒酒会上都会被喝掉，少一桶都不行，不然酒不够，酒会上和酒会后国王请来的贵宾不允许出任何事故
- 方案必须能保证到最后一定能验出来，毕竟任何极端情况都有可能，绝对不能靠运气，国王的酒会输不起，只有 2 天时间
 |
1
neosfung 2017-03-04 21:33:04 +08:00  1
构建一个 20*20*25 的三维数组这个三维数组
找 20+20 个囚犯 在第 0 小时，取前面的 20*20=400 桶酒 填在这个 20*20 的表格里 20 名囚犯负责横排， 20 名囚犯负责竖排 负责横排的囚犯就喝他所在横排的酒 负责竖排的囚犯就喝他所在竖排的酒 每一个小时试下一批 如果在某个时间段内有囚犯死了，必然是两个囚犯 这样就可以推测出之前是喝的是哪个时间段的酒，喝的是哪一桶 综上所述，需要 40 名囚犯，最后死两名囚犯 |
 |
2
fg607 2017-03-06 13:14:29 +08:00
一个人间隔一小时喝一桶，因为毒发在 23-24 小时之后， 48 小时内要验出，所以每个人在 24 小时内最多检验 25 桶酒，总共 500 桶，需要 500/25=20 个人。
但这不一定是最少的答案，但比一楼的少^_^ |
|
3
fg607 2017-03-06 13:22:12 +08:00
搞错了，楼主是 10000 桶酒，不是一个题目-_-#
|
|
4
fg607 2017-03-06 14:08:47 +08:00
一楼的方法很牛逼，但不是最少的，在一楼的基础上可以优化，设置 20*20 人的排列，但最后一列不安排人喝，结果会出现死两个人和死一个人的情况，都可以判断哪一桶有毒，所以最少时 39 人。
|
|
5
fg607 2017-03-06 14:42:08 +08:00
好了，更严谨的来了， C(28,2)+28=406>400,最少 28 人。
|
|
6
fg607 2017-03-06 15:49:26 +08:00
标准答案应该是 C(N,1)+C(N,2)+C(N,3)+........C(N,N)>=400
|
|
7
neosfung 2017-03-17 16:51:46 +08:00
好吧，再给个可用的答案
同样，将 10000 桶酒分为 25 组，每组 400 桶 找 9 个囚犯，每个囚犯按照 1 ， 2 ， 4 ， 8 ， 16 ， 32 ， 64 ， 128 ， 256 编号 嗯，到了这个套路，相信程序员都很熟悉了。。。 |
Select Language