论坛首页 Java企业应用论坛

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

浏览 26953 次
精华帖 (0) :: 良好帖 (0) :: 新手帖 (0) :: 隐藏帖 (0)
作者 正文
   发表时间:2011-04-22  
有点意思  
0 请登录后投票
   发表时间: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;
	}

}


随便整整,各位童鞋别拍砖啊,呵呵。
0 请登录后投票
   发表时间:2011-04-22  
511930751 写道
时间最少的方法是:100个侍卫喝。30分钟有效果。

这个认同

511930751 写道
小兵死亡最少的方法是:1个喝,30分+100秒有效果。。

这个不认同,因为前提是你假设士兵1秒喝一桶
0 请登录后投票
   发表时间: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号位的侍卫死了的话你是看不出到底是哪瓶有毒的。
0 请登录后投票
   发表时间: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)的酒有毒吗?
0 请登录后投票
   发表时间:2011-04-22   最后修改: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 这两种方案哪一个在理论上死的人最少


0 请登录后投票
   发表时间: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号侍卫实在悲催。。

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


两个二进制数相&&
0 请登录后投票
   发表时间: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)的酒有毒吗?

应该能看出,可以看那个人先死!!!
0 请登录后投票
   发表时间:2011-04-22  
我服了...犀利啊
0 请登录后投票
   发表时间:2011-04-22   最后修改:2011-04-22
组合的问题,100桶酒,n个人,一桶酒可以有0.1.2.3...n个人去喝,每桶酒对应一种情况,求n.
二项式定理,Cn0+Cn1+Cn2+...+Cnn=2^n>=100,求n的最小值


运气好了一个不死,运气不好了死n个……
0 请登录后投票
论坛首页 Java企业应用版

跳转论坛:
Global site tag (gtag.js) - Google Analytics