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

/*
 *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号侍卫代表2；1号侍卫代表3；2号侍卫代表5；3号侍卫代表7....等等

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

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

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

恕我愚笨，你这个思路和KK的其实差不多，不过这个时间和侍卫到底怎么分配的才是最佳的，我还是没看明白。

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


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

基本是平均的。

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