论坛首页 Java企业应用论坛

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

浏览 26952 次
精华帖 (0) :: 良好帖 (0) :: 新手帖 (0) :: 隐藏帖 (0)
作者 正文
   发表时间:2011-04-21   最后修改:2011-04-21
/*
 *Man.java 该类表示侍卫
 * 
 */
public class Man {
	
	private int id;//表示第几个侍卫
	private boolean alive = true;//表示侍卫是否活着
	
	
	public Man(int id){
		this.id = id;
	}

	public boolean isAlive() {
		return alive;
	}
	public void drank(Barrel barrel){
		if(!barrel.isSafed())
		{		
			this.alive = false;
			System.out.println("第"+id+"个士兵被毒死了");
		}
	}

}
/*
 * Barrel.java表示酒桶
 * 
 */
public class Barrel {
	
	private int id;//表示第几个酒桶
	private boolean safed = true;//表示酒桶是否被投毒,true表示没有被投毒,false表示被投毒
	
	public Barrel(int id){
		this.id = id;
	}
	
	public boolean isSafed() {
		return safed;
	}
	
	public void poisoned() {
		this.safed = false;
		System.out.println("向第"+id+"桶酒下毒");
	}

}
/*
 * king.java 主程序包含一个线程Dranker类和一个main函数类king
 */
import java.util.Random;

class Dranker extends Thread{
	
	private Man m;//一个侍卫
    private Barrel[]b;//100个酒桶
	private int index;//侍卫的编号
	
	
	public Dranker(Man m, int index,Barrel[]b)
	{
		this.m = m;
		this.index = index;
		this.b = b;
	}
	
	public void run(){
		for(int j=1;j<=100;j++)
		{
		  if(((int)Math.pow(2, index-1)&j) != 0 )
		  {
			  m.drank(b[j]);//执行喝酒的程序
		  }
		
		}
	}
}


public class King {
	
	public Barrel[]waters = new Barrel[101];//初始化容量为101,从1开始用,为了让数组下标和实际表示第几个酒桶一致
	public Man[]man = new Man[8];
	
	public King(){
		
		for(int s=1;s<=7;s++){
		   man[s] = new Man(s);
		}
		for(int t=1; t<=100;t++){
		   waters[t]= new Barrel(t);
		}
	}

	public static void main(String[]args) throws InterruptedException{
		
		int i = new Random().nextInt(100);	//取随机数,对该酒桶下毒
		King k = new King();
		k.waters[i].poisoned();
		
	
		Dranker t2=  new Dranker(k.man[1],1,k.waters);
		Dranker t3=  new Dranker(k.man[2],2,k.waters);
		Dranker t4=  new Dranker(k.man[3],3,k.waters);
		Dranker t5=  new Dranker(k.man[4],4,k.waters);
		Dranker t6=  new Dranker(k.man[5],5,k.waters);
		Dranker t7=  new Dranker(k.man[6],6,k.waters);
		Dranker t1=  new Dranker(k.man[7],7,k.waters);
		t1.start();//启动线程
		t1.join();//该线程执行完,主线程才能继续执行,为了保证sum的值计算正确
		t2.start();
		t2.join();
		t3.start(); 
		t3.join();
		t4.start();
		t4.join();
		t5.start();
		t5.join();
		t6.start();
		t6.join();
		t7.start();  
	    t7.join();
	    
	    
		int sum =0;
		for(int j=1;j<=7;j++){
			if(!k.man[j].isAlive())//判断哪些侍卫死了
			{
				sum +=Math.pow(2, j-1);
			}
		}
		
		System.out.println("经过计算,第"+sum+"桶酒被下毒了");//输出结果
	}

}
0 请登录后投票
   发表时间:2011-04-21  
别贴代码了,这个代码实现又不困难,看着蛋疼
0 请登录后投票
   发表时间: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号侍卫实在悲催。。

还是没看懂……哪位能讲下。。。
0 请登录后投票
   发表时间:2011-04-21  
虽然使用的士兵最少,但是牺牲的士兵倒是不少。。
0 请登录后投票
   发表时间: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,转成十进制,就是有毒的酒桶序号。

这个要顶。不过是不是最优解呢,看不懂。侍卫和时间怎么权重的?
0 请登录后投票
   发表时间:2011-04-21   最后修改:2011-04-21
各位不用贴代码了,这题就是考一下算法,只要解释一下自己的思路就足够了。


我原本的方法是利用素数
比如0号侍卫代表2;1号侍卫代表3;2号侍卫代表5;3号侍卫代表7....等等

然后每一桶酒都被不同的唯一组合的侍卫喝过  比如:2*3、3*5、2*3*7等等

最后如果是1、2、3号侍卫死了   那就用他们代表的素数相成,就得出是3*5*7这桶酒是有毒的

这在一定数量范围内的计算,线程资源的分配比较平均一点,不像之前用二进制算的那个一号侍卫那么悲催。。。
0 请登录后投票
   发表时间:2011-04-21  
bolide74 写道
各位不用贴代码了,这题就是考一下算法,只要解释一下自己的思路就足够了。


我原本的方法是利用素数
比如0号侍卫代表2;1号侍卫代表3;2号侍卫代表5;3号侍卫代表7....等等

然后每一桶酒都被不同的唯一组合的侍卫喝过  比如:2*3、3*5、2*3*7等等

最后如果是1、2、3号侍卫死了   那就用他们代表的素数相成,就得出是3*5*7这桶酒是有毒的

这在一定数量范围内的计算,线程资源的分配比较平均一点,不像之前用二进制算的那个一号侍卫那么悲催。。。

恕我愚笨,你这个思路和KK的其实差不多,不过这个时间和侍卫到底怎么分配的才是最佳的,我还是没看明白。
0 请登录后投票
   发表时间:2011-04-21  
那就直接一点吧   在正好半小时时间的的前提下,怎么样用最少的侍卫找出毒酒,最好还能让每个侍卫试的次数尽量均衡,也就是让各线程的负载尽量均衡
假设侍卫能瞬间同时试喝N桶的酒。。。。


考的是算法,我想连这个题目想表达哪种多线程状况都还没搞明白的同学,就别再去钻题目文字层面上的牛角尖了吧....
0 请登录后投票
   发表时间:2011-04-21  
yangyi 写道
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 考虑压缩编码


基本是平均的。
0 请登录后投票
   发表时间:2011-04-21  
bolide74 写道
那就直接一点吧   在正好半小时时间的的前提下,怎么样用最少的侍卫找出毒酒,最好还能让每个侍卫试的次数尽量均衡,也就是让各线程的负载尽量均衡
假设侍卫能瞬间同时试喝N桶的酒。。。。


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

你这么一说我就懂了,线程可以由自己定,没有最优解,最多是个统计的问题。
0 请登录后投票
论坛首页 Java企业应用版

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