多线程算法题：国王、毒酒、侍卫

国王有一百桶酒，比自己的生命还重要。结果有一天其中一桶被投了慢性毒药，喝了以后半个小时以后就会死掉。
国王大怒，命令玩忽职守的侍卫去试毒。
怎么样才能用最少的侍卫、在最短的时间知道哪桶是毒酒。

侍卫可以理解为线程，即怎么样用最少"人月"来完成这个工作。

为了避免再有人走歪门邪道。。。   我改了一下   毒药发作时间不确定正好半小时，只能说半小时左右，按体质不同发作时间不定，即不一定先喝的就先死

以上限制也是为了体现多线程并发的一般情况，毕竟无阻塞并发本来就很难判断哪个线程先跑完

评论

8 楼 linliangyi2007 2011-04-21  

ppgunjack 写道

这个题目有绝对答案吗，只用一个卫士每秒一桶喝一口，最坏情况30分+100秒也能确定
kimmking方法没理解，能想到的就是10人同时喝10杯个位数相同的，过1秒然后喝10杯十位数相同的，最坏情况死两个卫士，最好情况死1个

这个算法没看明白啊，求解释为啥是过1秒后？

7 楼 linliangyi2007 2011-04-21  

kimmking 写道

bolide74 写道

国王有一百桶酒，比自己的生命还重要。结果有一天其中一桶被投了慢性毒药，喝了以后半个小时以后就会死掉。
国王大怒，命令玩忽职守的侍卫去试毒。
酒不能被混合，怎么样才能用最少的侍卫、在最短的时间知道哪桶是毒酒。

侍卫可以理解为线程，即怎么样用最少的线程用最快的速度完成这个工作。

100 < 128 = 2^7

找7个侍卫，编号1-7                             1234567

100桶酒，编号1-100
每个编号表示成2进制，不超过7位，前面补上0成7位，比如0000001
从第一位到第七位，如果是1，让序号为此位的侍卫喝此酒。

半小时后，哪几个侍卫死了，就在他所在的位置置1，活的置0
得到一个7位的二进制 0010101，转成十进制，就是有毒的酒桶序号。

这个强，哈哈，这样所有的酒可以同时喝，根据死去的多个卫士来定位酒桶号，有意思。

不过1号卫士真可怜，要喝50杯酒啊，这个死的可能性太高了，

这个算法在实际处理中有缺陷（不均衡），按楼主的设想，每个卫士理解为一个线程的话，1号线程要处理50桶酒的任务，虽然每个处理时瞬时的。

6 楼 ppgunjack 2011-04-21  

这个题目有绝对答案吗，只用一个卫士每秒一桶喝一口，最坏情况30分+100秒也能确定
kimmking方法没理解，能想到的就是10人同时喝10杯个位数相同的，过1秒然后喝10杯十位数相同的，最坏情况死两个卫士，最好情况死1个

5 楼 bolide74 2011-04-21  

侍卫是可以喝多杯酒的   我限制了说酒不能混合其实是想说“酒”这个对象是不能更改的

4 楼 ppgunjack 2011-04-21  

最少的侍卫、在最短的时间是什么意思，指总的mhr最低吗
如果1个侍卫不能同时喝多杯酒，那注定是50mhr，否则转化成查询问题，矩阵定位xy

3 楼 bolide74 2011-04-21  

果然还是难不住楼上啊   哈哈   本来我还期待会先想到用素数呢

2 楼 kimmking 2011-04-21  

bolide74 写道

国王有一百桶酒，比自己的生命还重要。结果有一天其中一桶被投了慢性毒药，喝了以后半个小时以后就会死掉。
国王大怒，命令玩忽职守的侍卫去试毒。
酒不能被混合，怎么样才能用最少的侍卫、在最短的时间知道哪桶是毒酒。

侍卫可以理解为线程，即怎么样用最少的线程用最快的速度完成这个工作。

100 < 128 = 2^7

找7个侍卫，编号1-7                             1234567

100桶酒，编号1-100
每个编号表示成2进制，不超过7位，前面补上0成7位，比如0000001
从第一位到第七位，如果是1，让序号为此位的侍卫喝此酒。

半小时后，哪几个侍卫死了，就在他所在的位置置1，活的置0
得到一个7位的二进制 0010101，转成十进制，就是有毒的酒桶序号。

1 楼 蛋呢823 2011-04-21  

引用

酒不能被混合

是指侍卫不能一下子喝好几桶的酒吗？（一桶喝一口，在肚子里混合）