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

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

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

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

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

评论

48 楼 xbcoil 2011-04-22  

我服了...犀利啊

47 楼 heisedeyueya 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

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

这个算法是有问题的，比如处于1号位和2号位的侍卫死了的话 你知道是（1,0）还是（0，1）的酒有毒吗？

应该能看出，可以看那个人先死！！！

46 楼 johnnyking 2011-04-22  

mahonet 写道

lyy3323 写道

kimmking 写道

bolide74 写道

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

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

100 < 128 = 2^7

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

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

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

这个算法有点意思啊。学术名叫什么？
1号侍卫实在悲催。。

还是没看懂……哪位能讲下。。。

两个二进制数相&&

45 楼 dsjt 2011-04-22  

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 这两种方案哪一个在理论上死的人最少

44 楼 zhanghh321 2011-04-22  

albertshaw 写道

ppgunjack 写道

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

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

这个算法是有问题的，比如处于1号位和2号位的侍卫死了的话 你知道是（1,0）还是（0，1）的酒有毒吗？

43 楼 zhanghh321 2011-04-22  

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号位的侍卫死了的话你是看不出到底是哪瓶有毒的。

42 楼 Bruce.Sun 2011-04-22  

511930751 写道

时间最少的方法是：100个侍卫喝。30分钟有效果。

这个认同

511930751 写道

小兵死亡最少的方法是：1个喝，30分+100秒有效果。。

这个不认同，因为前提是你假设士兵1秒喝一桶

41 楼 kingkan 2011-04-22  

kimmking 写道

bolide74 写道

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

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

100 < 128 = 2^7

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

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

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

public class Client {

	public static void main(String[] args) {
		HashMap<Integer,Boolean> jiuMap = getJiuMap(100);
		HashMap<Integer,Boolean> shiMap = getShiMap(7);
		for (Map.Entry<Integer,Boolean> entryShi : shiMap.entrySet()) {
			for (Map.Entry<Integer,Boolean> entryJiu : jiuMap.entrySet()) {
				if((entryShi.getKey() & entryJiu.getKey()) == entryShi.getKey()){
					if(!entryJiu.getValue().booleanValue()){
						entryShi.setValue(false);
					}
				}
			}
		}
		//try { Thread.sleep(30*60*1000); } catch (InterruptedException e) {}
		int dujiu = 0;
		for (Map.Entry<Integer,Boolean> entryShi : shiMap.entrySet()) {
			if(!entryShi.getValue()){
				dujiu = dujiu | entryShi.getKey();
			}
		}
		System.out.println("毒酒二进制："+Integer.toBinaryString(dujiu));
	}
	
	private static HashMap<Integer,Boolean> getShiMap(int shiNumber) {
		System.out.println("侍卫数："+shiNumber);
		HashMap<Integer,Boolean> shiMap = new HashMap<Integer,Boolean>();
		for (int i = 0; i < shiNumber; i++) {
			int shi = 1 << i;
			shiMap.put(shi, true);
		}
		return shiMap;
	}
	private static HashMap<Integer,Boolean> getJiuMap(int jiuNumber) {
		HashMap<Integer,Boolean> jiuMap = new HashMap<Integer,Boolean>();
		int dujiu = (int) (1 + Math.random() * jiuNumber);
		System.out.println("酒数量："+jiuNumber);
		System.out.println("毒酒号："+dujiu);
		for (int i = 1; i <= jiuNumber; i++) {
			if(i == dujiu){
				jiuMap.put(i, false);
			}else{
				jiuMap.put(i, true);
			}
		}
		return jiuMap;
	}

}

随便整整，各位童鞋别拍砖啊，呵呵。

40 楼 mcqueen 2011-04-22  

有点意思  

39 楼 albertshaw 2011-04-22  

ppgunjack 写道

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

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

38 楼 jtyb 2011-04-22  

学习一下思想

37 楼 kingkan 2011-04-22  

kimmking 写道

bolide74 写道

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

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

100 < 128 = 2^7

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

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

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

这种方式比较符合计算机编程。

36 楼 liuyupy 2011-04-22  

kimmking 写道

bolide74 写道

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

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

100 < 128 = 2^7

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

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

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

前段日子出过小白鼠实验题。。。也是一样解法。

35 楼 semmy 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，转成十进制，就是有毒的酒桶序号。

起初没看明白，现在总算看明白了

34 楼 orcl_zhang 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，转成十进制，就是有毒的酒桶序号。

33 楼 evanzzy 2011-04-21  

学习一下算法

32 楼 kxys422834 2011-04-21  

新手学习了！

31 楼 rongsantang 2011-04-21  

提供一个跟程序员相关的思路：二分查找法

30 楼 fellatioyzx 2011-04-21  

又见月经贴，1000桶酒10个小白鼠试毒的面试题网上早就传遍了好吧。

29 楼 许文强 2011-04-21  

bolide74 写道

那就直接一点吧   在正好半小时时间的的前提下，怎么样用最少的侍卫找出毒酒，最好还能让每个侍卫试的次数尽量均衡，也就是让各线程的负载尽量均衡
假设侍卫能瞬间同时试喝N桶的酒。。。。


考的是算法，我想连这个题目想表达哪种多线程状况都还没搞明白的同学，就别再去钻题目文字层面上的牛角尖了吧....

你这么一说我就懂了，线程可以由自己定，没有最优解，最多是个统计的问题。