国王与100个囚犯

国王招来100个囚犯，对他们说：你们犯的是死罪，本应该将你们统统杀掉，但我慈悲为怀，给你们一次求生的机会。15分钟以后，你们将被关进一个有100 间隔离牢房的监狱里，每人一间牢房，都与外界隔绝，什么也听不见、看不到，连时间都没法计算，更别说获得外界的任何信息。（送饭除外，但也是不规律的送）

这所监狱有一个院子，每天会随机（注意是完全随机）打开一间牢房的门，让那个囚犯到院子里来放风。院子里有一盏路灯，放风的囚犯可以控制它的开关，将它打开或是关闭。除囚犯之外，其他人都不会去碰开关。这盏灯会永远有充足的能源供应，如果灯泡坏了或是电路出了故障会马上修好，当然修理人员不会改变灯的状态（开或关）。

除了开关这盏灯，放风的囚犯放风时留下的任何其它痕迹都会在夜晚被清除干净（包括在灯上作的任何记号）。

牢房是完全封闭的，院子里的灯光在牢房里看不到。只有放风出到院子里的人才能看到。

好了现在我向你们提出一个要求，只要你们做到了，就可以全部获得释放： 若干天以后，你们中只要有任何一个人能够向我证明所有的人都曾到院子里去过，你们就全体释放。当然要有证据！因为我只会给你们一次机会，如果向我证明的那个人无法自圆其说，你们就全部砍头。所以，要珍惜这次机会。如果你们永远做不到我的要求，你们就全部关到死。

现在给你们15分钟商量你们的方案。15分钟以后，你们将被关进我刚才说的那个监狱，永远无法再交流。

---------------------------
思路:
·选被关后第一天出去的囚犯作为特殊的计数员
·计数员被放出去,第一天将灯打开,今后每次放出去的时候,如果遇见灯是熄灭的,则将灯打开,并将记数加1
·而其他囚犯为普通囚犯,普通囚犯如果被放出去,在第一次遇见灯是打开的时候将其关闭(其他情况,即遇见灯是熄灭或第2,3,4..次遇见灯是开着的时候什么也不做)

至于灯的初试状态没有什么关系，如果设成true，只需在day==0的时候加个判断就行了。。

import java.util.Date;
import java.util.Random;

public class King_100Prisoner {
	
	// 记数器(由记数员囚犯用来计数囚犯放出去的人数)
	public int count;
	
	// 记数员囚犯编号
	public int counterman; 
	
	// 用来标记1到50编号的囚犯是否被放过风且关过灯
	public long _1_50 = 0;
	
	// 用来标记51到100编号的囚犯是否被放过风且关过灯
	public long _51_100 = 0;
	
	// 标识灯是否亮着
	public boolean isLightOn = false; 
	
	// 标记经过的天数
	public int day = 0;
	
	// 返回放风囚犯记数
	public int getCount(){
		return count;
	}
	
	// 返回经历的天数
	public int getDay(){
		return day;
	}
	
	// 囚犯被放风
	public void releasePrisoner(int prisoner){

		// 放出不明生物
		if(prisoner>100 || prisoner<0){
			System.out.println("放出不明生物");
			return;
		}
		// 第一天被放风的做记数员
		if(day==0){
			counterman = prisoner;
		}
String name = (prisoner==counterman)?"记数员":"囚犯"	;
System.out.print("第"+day+"天: "+ name +prisoner + "放风...");				
		// 如果放风的是记数员
		if(prisoner == counterman){
			// 如果灯是关着的,将其打开,并且放风计数加1
			if(!isLightOn){
				isLightOn = true;
				count++;			
System.out.print("发现灯是关着的将放风计数+1");				
			}
			
		}else{ // 如果放风的是普通囚犯
			
			// 如果囚犯未被放过风且关过灯
			if((prisoner&_1_50)==0 && (prisoner&_51_100)==0){
				
				// 第一次放风遇见灯时开着时,关灯,记录该囚犯放过风且关过灯
				if(isLightOn==true){
					isLightOn = false;
					
					if(prisoner<=50){
						_1_50 = _1_50 | (0x1L<<(prisoner-1));
					}else{
						_51_100 = _51_100 | (0x1L<<(prisoner-1));
					}
System.out.print("第一次遇见灯开着,于是将灯关了,并且记住从此放风什么也不干了");					
				}else{
System.out.println("发现灯是关着的,什么也没干");				
				}
			}else{
System.out.println("已经放过风,关过灯,于是什么也没干");
			}
		}
		day++;	
	}
	
	public static void main(String[] args) {
		King_100Prisoner demo = new King_100Prisoner();
		Random r = new Random(new Date().getTime());
		int prisoner = 0;
		while(demo.getCount()<100){
			prisoner = r.nextInt(100)+1;
			demo.releasePrisoner(prisoner);
		}
	}

}

面向对象的思想有时候是很耗费资源的事情，看前面有人解决的时候将囚犯封装为一个类，100个囚犯就要构造100个对象，虽然更直观，但是总觉得不舒服
其实两个long变量（和起来有128位）就足以标记100个囚犯开灯的状态

算法难归难，有时挺好玩的。

题目是说被关进去后就不知道时间……那他们怎么知道自己是第一个被放出去的人呢？

晕，你自己想想你被关进去后，第一天释放的是你，你知不知道？
看问题不能太死哦~

请问结束的条件是什么，不明白

不知道，因为不知道时间，你不知道前面有谁被放出去了

对啊，那怎么判定每个人都已经出来过呢

while(demo.getCount()<100)

计数的囚犯第100次开灯的时候（如果初始灯是关闭的）

如果灯的初试状态未知，可以这样：

import java.util.Date;
import java.util.Random;

public class King_100Prisoner {
	
	// 记数器(由记数员囚犯用来计数囚犯放出去的人数)
	private int count;
	
	// 记数员囚犯编号
	private int counterman; 
	
	// 用来标记1到50编号的囚犯是否被放过风且关过灯
	private long _1_50 = 0;
	
	// 用来标记51到100编号的囚犯是否被放过风且关过灯
	private long _51_100 = 0;
	
	// 标识灯是否亮着
	private boolean isLightOn = false; 
	
	// 标记经过的天数
	private int day = 0;
	
	// 返回放风囚犯记数
	public int getCount(){
		return count;
	}
	
	// 返回经历的天数
	public int getDay(){
		return day;
	}
	
	// constructor
	public King_100Prisoner(boolean isLightOn){
		this.isLightOn = isLightOn;
	}
	
	// 囚犯被放风
	public void releasePrisoner(int prisoner){

		// 放出不明生物
		if(prisoner>100 || prisoner<0){
			System.out.println("放出不明生物");
			return;
		}
		
		// 第一天
		if(day==0){
			counterman = prisoner;
			if(!isLightOn){
				isLightOn = true;
			}
			count++;
			
		// 第一天以后的日子
		}else{	
			// 如果放风的是记数员
			if(prisoner == counterman){
				// 如果灯是关着的,将其打开,并且放风计数加1
				if(!isLightOn){
					isLightOn = true;
					count++;						
				}
				
			}else{ // 如果放风的是普通囚犯
				
				// 如果囚犯未关过灯
				if((prisoner&_1_50)==0 && (prisoner&_51_100)==0){
					
					// 第一次放风遇见灯开着,关灯,记录该囚犯放过风且关过灯
					if(isLightOn==true){
						isLightOn = false;
						
						if(prisoner<=50){
							_1_50 = _1_50 | (0x1L<<(prisoner-1));
						}else{
							_51_100 = _51_100 | (0x1L<<(prisoner-1));
						}
					// 遇见灯是关着的,什么也不做
					}else{
						// do nothing
					}
				// 如果囚犯已经关过灯	,什么也不做
				}else{
					// do nothing
				}
			}
		}
		day++;	
	}
	
	public static void main(String[] args) {
		King_100Prisoner demo = new King_100Prisoner(true);
		Random r = new Random(new Date().getTime());
		int prisoner = 0;
		while(demo.getCount()<100){
			prisoner = r.nextInt(100)+1;
			demo.releasePrisoner(prisoner);
		}
		System.out.println("需要"+demo.getDay()+"天");
	}

}