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

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

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

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

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

评论

68 楼 zk7019311 2011-05-06  

学了不少东西啊

67 楼 yangyi 2011-05-03  

import threading

class Warrior:
    def __init__(self, id, jar_count):
        self.id = id
        self.jar_count = jar_count
        self.jars = []
    def should_drink(self, jar_index):
        """Whether the warrior should drink"""
        return self.id & jar_index != 0
    def drink(self, jar_index):
        if self.should_drink(jar_index):
            self.jars.append(jar_index)
    def work(self):
        for i in xrange(1, self.jar_count):
            self.drink(i)
        print("\t".join(str(v) for v in self.jars))

if __name__ == "__main__":
    w = 100
    v = 1
    c = 1
    while (v - 1 < w):
        v <<= 1
        c += 1
    
    for n in xrange(1, c):
        warrior = Warrior(1<<(n-1), w)
        m = threading.Thread(target=warrior.work()) ;
        m.start()
        

66 楼 jhcfe 2011-05-03  

露娜·雪之溯 写道

kimmking 写道

bolide74 写道

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

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

100 < 128 = 2^7

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

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

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

有点不明白，半小时后生成的那个二进制数为什么就是毒酒的序号

因为死掉的几个喝了毒酒，酒的编号先转为二进制给对应的侍卫喝，倒回来不就是毒酒的编号了

65 楼 露娜·雪之溯 2011-04-30  

kimmking 写道

bolide74 写道

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

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

100 < 128 = 2^7

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

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

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

有点不明白，半小时后生成的那个二进制数为什么就是毒酒的序号

64 楼 java仰望|俯视 2011-04-29  

bolide74 写道

国王有一百桶酒，比自己的生命还重要。

看大家都在讨论那个二进制的解法，不知道各位有没有看到这个条件呢？
酒比命重要。
这样方法就只有一个小兵来试验了，喝一碗没事的再喝第二碗直到喝死过去

仅有一种死不了的方法，你懂得！

63 楼 zhanghongliang_cyj 2011-04-25  

com0606 写道

组合的问题，100桶酒，n个人，一桶酒可以有0.1.2.3...n个人去喝，每桶酒对应一种情况，求n.
二项式定理，Cn0+Cn1+Cn2+...+Cnn=2^n>=100,求n的最小值


运气好了一个不死，运气不好了死n个……

用排列组合。只需尝试99缸酒 便可以
设 需 n个人来尝试 毒酒
Cn1 + Cn2 + ... + Cnn>=99  即可   求   n最小
每个组合 用来 标记 一缸酒。

答案 7个士兵。半个小时。
C71 = 7
C72 = 21
C73 = 35
C74 = 35
C75 = 21

C71 + C72 + C73 + C74 + C75 = 119>=99

故：最幸运的话，一个不死。  最不幸  死 5个士兵

62 楼 bolide74 2011-04-24  

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

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

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

61 楼 yangyi 2011-04-23  

511930751 写道

小兵死亡最少的方法是：1个喝，30分+100秒有效果。。
这个不认同，因为前提是你假设士兵1秒喝一桶

前提不是1秒喝一桶，而是30分是虚指，并不精确
当然这也引出另一个问题，就是喝多少酒会死人？和个人的抗体和酒量有没有关系？如果有关系，那可能在二进制编码中少算一个1神马的，最后认出来是瓶假毒酒。

60 楼 luckyEveryOne 2011-04-23  

我有个简单想法 因为是喝完以后半小时死掉
嘿嘿
我用10个人 
计时 每人喝10桶
每人一秒喝一桶 
10秒后全部喝结束
半个小时10秒 根据死亡时间 得出 那桶酒有毒
7号假设半个小时7秒死了
那么就是第77桶

59 楼 zhangchen 2011-04-23  

kimmking 写道

bolide74 写道

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

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

100 < 128 = 2^7

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

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

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

不错，这是一桶毒酒的解法
但是，如果有两桶毒酒呢？

58 楼 susiya 2011-04-22  

很久以前的题目，都快忘光啦，

57 楼 ppgunjack 2011-04-22  

dsjt 写道

albertshaw 写道

ppgunjack 写道

其实过不一秒也无所谓，但是实际是分两轮
1个10x10矩阵，里面有个点是1（有毒），其余是0，第一轮10个人同时喝纵向的酒，第二轮过后这10个人喝所有横向，一般会先后死2个，如果毒酒在5×5这种平方位置则就一个人死
扩展开又可以分成5×5×5把100划分到125的3维矩阵，每轮5线程覆盖该平面的25个桶，最后死的顺序3个人能确定i，j，k

我觉得这个解挺好的呀,为什么没人评论一下呢?

这个方案挺不错，但三维矩阵有bug，
死一个或者死三个可以确定坐标；
死两个怎么办？
比如 2号死然后是3号死； 存在两种情况：2,2,3 或者2,3,3
除非还要计算其死亡的时间间隔和喝酒的时间间隔；否则就要再有一个人喝一次；





不知道 2^7与5×5×5 这两种方案哪一个在理论上死的人最少

因为是分轮，每轮不需要隔开30分，隔个可测量间隔就行，所以理论上实际死亡有三波，即使两个人死亡确定发生在哪一波上就行，10X10则是两波，以此区分xy或xyz的顺序，这个线程数不同可以衍生很多
同时两者最小是不可能的，本来以为追求是人数*时间最小，求总人月的问题

56 楼 jhcfe 2011-04-22  

来上6个人分成3组，去掉一桶
两人一对每人33桶，相对着喝，一分钟去喝一口
直到有人挂掉，往后数30个。。。
没人挂掉就比较悲剧，哈哈

55 楼 Simon.C 2011-04-22  

有意思,研究研究

54 楼 com0606 2011-04-22  

zhanghh321 写道

albertshaw 写道

ppgunjack 写道

其实过不一秒也无所谓，但是实际是分两轮
1个10x10矩阵，里面有个点是1（有毒），其余是0，第一轮10个人同时喝纵向的酒，第二轮过后这10个人喝所有横向，一般会先后死2个，如果毒酒在5×5这种平方位置则就一个人死
扩展开又可以分成5×5×5把100划分到125的3维矩阵，每轮5线程覆盖该平面的25个桶，最后死的顺序3个人能确定i，j，k

我觉得这个解挺好的呀,为什么没人评论一下呢?

我觉得这种算法是有点问题的，假设10个人横向喝一次，然后纵向喝一次的话，如果是1号位喝0号位的侍卫死了的话你是看不出到底是哪瓶有毒的。

这种方法其实应该这样理解：
10个人，每个人喝10桶酒，过30分钟后死一个人，余下9人去喝死的这个人喝过的10桶酒中的9桶，再过30分钟如果9人都不死证明那桶没人喝的有毒，否则，哪个人死了那他喝过的那桶有毒。

53 楼 xuey210 2011-04-22  

kimmking 的方法 可以得到一个酒桶号和侍卫编号的对应关系表，

1 => 0000001 => 7
2 => 0000010 => 6
3 => 0000011 => 6 7
4 => 0000100 => 5
5 => 0000101 => 5 7
6 => 0000110 => 5 6
7 => 0000111 => 5 6 7
8 => 0001000 => 4
9 => 0001001 => 4 7
10 => 0001010 => 4 6
11 => 0001011 => 4 6 7
12 => 0001100 => 4 5
13 => 0001101 => 4 5 7
14 => 0001110 => 4 5 6
15 => 0001111 => 4 5 6 7
16 => 0010000 => 3
17 => 0010001 => 3 7
18 => 0010010 => 3 6
19 => 0010011 => 3 6 7
20 => 0010100 => 3 5
21 => 0010101 => 3 5 7
22 => 0010110 => 3 5 6
23 => 0010111 => 3 5 6 7
24 => 0011000 => 3 4
25 => 0011001 => 3 4 7
26 => 0011010 => 3 4 6
27 => 0011011 => 3 4 6 7
28 => 0011100 => 3 4 5
29 => 0011101 => 3 4 5 7
30 => 0011110 => 3 4 5 6
31 => 0011111 => 3 4 5 6 7
32 => 0100000 => 2
33 => 0100001 => 2 7
34 => 0100010 => 2 6
35 => 0100011 => 2 6 7
36 => 0100100 => 2 5
37 => 0100101 => 2 5 7
38 => 0100110 => 2 5 6
39 => 0100111 => 2 5 6 7
40 => 0101000 => 2 4
41 => 0101001 => 2 4 7
42 => 0101010 => 2 4 6
43 => 0101011 => 2 4 6 7
44 => 0101100 => 2 4 5
45 => 0101101 => 2 4 5 7
46 => 0101110 => 2 4 5 6
47 => 0101111 => 2 4 5 6 7
48 => 0110000 => 2 3
49 => 0110001 => 2 3 7
50 => 0110010 => 2 3 6
51 => 0110011 => 2 3 6 7
52 => 0110100 => 2 3 5
53 => 0110101 => 2 3 5 7
54 => 0110110 => 2 3 5 6
55 => 0110111 => 2 3 5 6 7
56 => 0111000 => 2 3 4
57 => 0111001 => 2 3 4 7
58 => 0111010 => 2 3 4 6
59 => 0111011 => 2 3 4 6 7
60 => 0111100 => 2 3 4 5
61 => 0111101 => 2 3 4 5 7
62 => 0111110 => 2 3 4 5 6
63 => 0111111 => 2 3 4 5 6 7
64 => 1000000 => 1
65 => 1000001 => 1 7
66 => 1000010 => 1 6
67 => 1000011 => 1 6 7
68 => 1000100 => 1 5
69 => 1000101 => 1 5 7
70 => 1000110 => 1 5 6
71 => 1000111 => 1 5 6 7
72 => 1001000 => 1 4
73 => 1001001 => 1 4 7
74 => 1001010 => 1 4 6
75 => 1001011 => 1 4 6 7
76 => 1001100 => 1 4 5
77 => 1001101 => 1 4 5 7
78 => 1001110 => 1 4 5 6
79 => 1001111 => 1 4 5 6 7
80 => 1010000 => 1 3
81 => 1010001 => 1 3 7
82 => 1010010 => 1 3 6
83 => 1010011 => 1 3 6 7
84 => 1010100 => 1 3 5
85 => 1010101 => 1 3 5 7
86 => 1010110 => 1 3 5 6
87 => 1010111 => 1 3 5 6 7
88 => 1011000 => 1 3 4
89 => 1011001 => 1 3 4 7
90 => 1011010 => 1 3 4 6
91 => 1011011 => 1 3 4 6 7
92 => 1011100 => 1 3 4 5
93 => 1011101 => 1 3 4 5 7
94 => 1011110 => 1 3 4 5 6
95 => 1011111 => 1 3 4 5 6 7
96 => 1100000 => 1 2
97 => 1100001 => 1 2 7
98 => 1100010 => 1 2 6
99 => 1100011 => 1 2 6 7
100 => 1100100 => 1 2 5

哪个侍死掉了，对着表一查，找到前面的酒桶号就好了。YES！！

52 楼 p74300743 2011-04-22  

我的思路，不知道是否正确：
第一：100桶酒排列成10*10的二维矩阵；
第二：安排20个士兵来喝酒；
第三：把20个士兵分成两组，[0，1，2，3，4，5，6，7，8，9]和[1，2，3，4，5，6，7，8，9，0]；
第四：第一组的士兵喝（序号+1）行的酒，第二组士兵喝所在序号列的酒；
第五：等待30分钟后，有两个士兵死，第一组一个，第二组一个，如果第二组死的士兵的序号不是0，则第一组士兵的序号组成第二组士兵的序号就是下毒的酒；否则，第一组死的士兵的序号+1，再和0组成就是下毒的酒。
结果：20个士兵，30分钟，两个死，即可得结果！

51 楼 xuey210 2011-04-22  

linliangyi2007 写道

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桶酒的任务，虽然每个处理时瞬时的。

我觉得应该是7号侍卫可怜呢。。

50 楼 pollyduan 2011-04-22  

的确够强大

49 楼 com0606 2011-04-22  

组合的问题，100桶酒，n个人，一桶酒可以有0.1.2.3...n个人去喝，每桶酒对应一种情况，求n.
二项式定理，Cn0+Cn1+Cn2+...+Cnn=2^n>=100,求n的最小值


运气好了一个不死，运气不好了死n个……