|
锁定老帖子 主题：多线程算法题：国王、毒酒、侍卫
精华帖 (0) :: 良好帖 (0) :: 新手帖 (0) :: 隐藏帖 (0)
|
|
|---|---|
| 作者 | 正文 |
|
发表时间：2011-04-21
其实过不一秒也无所谓，但是实际是分两轮
1个10x10矩阵，里面有个点是1（有毒），其余是0，第一轮10个人同时喝纵向的酒，第二轮过后这10个人喝所有横向，一般会先后死2个，如果毒酒在5×5这种平方位置则就一个人死 扩展开又可以分成5×5×5把100划分到125的3维矩阵，每轮5线程覆盖该平面的25个桶，最后死的顺序3个人能确定i，j，k |
| 返回顶楼 | |
|
发表时间：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号侍卫实在悲催。。 |
| 返回顶楼 | |
|
发表时间：2011-04-21
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号侍卫实在悲催。。 就是个二进制表示。 其实延伸一点，N种A物和M种B物，找最优的混合比例什么的、在统计里有个比较科学的方法： 正交拉丁方 |
| 返回顶楼 | |
|
发表时间：2011-04-21
bolide74 写道 国王有一百桶酒，比自己的生命还重要。结果有一天其中一桶被投了慢性毒药，喝了以后半个小时以后就会死掉。
国王大怒，命令玩忽职守的侍卫去试毒。 怎么样才能用最少的侍卫、在最短的时间知道哪桶是毒酒。 侍卫可以理解为线程，即怎么样用最少的线程用最快的速度完成这个工作。 怎么样才能用最少的侍卫?这句话理解，是用最少的侍卫人数，还是最少的侍卫死亡人数。 这个是有本质区别的，把问题要说清楚滴。。。。。。 |
| 返回顶楼 | |
|
发表时间：2011-04-21
学习了.不错
|
| 返回顶楼 | |
|
发表时间：2011-04-21
时间最少的方法是：100个侍卫喝。30分钟有效果。
小兵死亡最少的方法是：1个喝，30分+100秒有效果。。 |
| 返回顶楼 | |
|
发表时间：2011-04-21
最后修改：2011-04-21
package jdk.src;
import java.util.Random;
/**
* Create on：Apr 21, 2011 3:59:19 PM
* @author Y.Guo
* @version 1.0
*
*
*
*/
public class DrinkPoison {
public static void main(String[] args) throws InterruptedException {
new DrinkPoison(100).startDrink();
}
}
有什么了不起的，不贴就不贴。洒家自己开一贴不就完了。 |
| 返回顶楼 | |
|
发表时间：2011-04-21
kimmking 写道 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号侍卫实在悲催。。 就是个二进制表示。 其实延伸一点，N种A物和M种B物，找最优的混合比例什么的、在统计里有个比较科学的方法： 正交拉丁方 不错，之前也是这样想，不过还在想另外一个问题，就是： 1 保证侍卫之间的公平性 2 不浪费额外的28个名额 3 考虑压缩编码 |
| 返回顶楼 | |
|
发表时间：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，转成十进制，就是有毒的酒桶序号。 强，学习了 |
| 返回顶楼 | |
|
发表时间：2011-04-21
确实学习了，不过第一个士兵太悲剧了，如果能保证所有士兵的公平性就完美了
|
| 返回顶楼 | |
