锁定老帖子 主题:多线程算法题:国王、毒酒、侍卫
精华帖 (0) :: 良好帖 (0) :: 新手帖 (0) :: 隐藏帖 (0)
|
|
---|---|
作者 | 正文 |
发表时间:2011-04-22
有点意思
|
|
返回顶楼 | |
发表时间: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; } } 随便整整,各位童鞋别拍砖啊,呵呵。 |
|
返回顶楼 | |
发表时间:2011-04-22
511930751 写道 时间最少的方法是:100个侍卫喝。30分钟有效果。
这个认同 511930751 写道 小兵死亡最少的方法是:1个喝,30分+100秒有效果。。
这个不认同,因为前提是你假设士兵1秒喝一桶 |
|
返回顶楼 | |
发表时间: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号位的侍卫死了的话你是看不出到底是哪瓶有毒的。 |
|
返回顶楼 | |
发表时间: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)的酒有毒吗? |
|
返回顶楼 | |
发表时间: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 这两种方案哪一个在理论上死的人最少 |
|
返回顶楼 | |
发表时间: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号侍卫实在悲催。。 还是没看懂……哪位能讲下。。。 两个二进制数相&& |
|
返回顶楼 | |
发表时间: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)的酒有毒吗? 应该能看出,可以看那个人先死!!! |
|
返回顶楼 | |
发表时间:2011-04-22
我服了...犀利啊
|
|
返回顶楼 | |
发表时间:2011-04-22
最后修改:2011-04-22
组合的问题,100桶酒,n个人,一桶酒可以有0.1.2.3...n个人去喝,每桶酒对应一种情况,求n.
二项式定理,Cn0+Cn1+Cn2+...+Cnn=2^n>=100,求n的最小值 运气好了一个不死,运气不好了死n个…… |
|
返回顶楼 | |