国王与100个囚犯

继续求高 人指点结束条件

这个思路就对了。因为我觉得根据题目的条件，你无法做到天数的优化。题目只能达到一个目的就是记录全部放风过。

楼已经给出了啊，那个就对了。只要轮到计数员，计数员的工作就是看灯的状态，其他普通人员就是记录自己的灯的状态，如果出去过那不动，没出去过久关灯。所以只要计数员计够100次，那就成功了。也就意味着100个人都出去过了。

哈哈,验证了一下,果然是要几十年才能出来,这个算法不好!

package com.util;

import java.util.Collection;
import java.util.Date;
import java.util.Iterator;
import java.util.Map;
import java.util.Random;
import java.util.Set;
import java.util.TreeMap;
import java.util.TreeSet;

public class King_100Prisoner {
	
	private Set set;
	
	// 记数器(由记数员囚犯用来计数囚犯放出去的人数)
	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){

		//map=new TreeMap(); 
		// 放出不明生物
		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){
				
				// 第一次放风遇见灯时开着时,关灯,记录该囚犯放过风且关过灯
				set.add(prisoner);
				if(isLightOn==true){
					isLightOn = false;
					
					if(prisoner<=50){
						_1_50 = _1_50 &prisoner;//| (0x1L<<(prisoner-1));
					}else{
						_51_100 = _51_100 &prisoner;//| (0x1L<<(prisoner-1));
					}
//System.out.println(prinsone"第一次遇见灯开着,于是将灯关了,并且记住从此放风什么也不干了");					
				}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());
		demo.set=new TreeSet();
		int prisoner = 0;
		while(demo.getCount()<100){
			prisoner = r.nextInt(100)+1;
			demo.releasePrisoner(prisoner);
		}
		System.out.println("共经历了"+demo.day+"天后,所有囚犯"+demo.counterman+"获释!");
		Iterator iter=demo.set.iterator();
		while(iter.hasNext()){
			System.out.println(iter.next());
		}
	}

}

假定灯初始状态为off，且随机选定一个囚犯当“带头大哥”：

def day = 0, counter = 0, bigBrother = new Random().nextInt(100), prisoner, light = 'off', log = [:]
while(counter < 100) {
    prisoner = new Random().nextInt(100)
    day++
    if(light == 'off') {
        if(!log[prisoner]) {
            log[prisoner] = true
            if(prisoner != bigBrother) {
                light = 'on' // turn the light on, to tell the big brother "I was out and in"
            } else {
                counter++ // big brother gets out to see the light is off, so he counts himself
            }
        }
    } else {
        if(prisoner == bigBrother) {
            counter++ // big brother counts others
            light = 'off' // big brother turns the light off, so that next new prisoner can turn it on
        }
    }
}
println "(prisoner #${bigBrother} is the big brother) It took ${day} days(=${day/365} years)."

其中的一次输出为：

(prisoner #16 is the big brother) It took 9934 days(=27.2164383562 years).

随机事件。..

漏掉一个前提，囚犯的生命是无限长的。

最好情况，
1，2，1，3，1，4，1，5.....，1，99，1，100，1 需要199天（如果没算错的话）

选个差点的，但绝不是极端的情况
1，2，3，4，5，6，7，8....，99，100，1，2，3，4，.....99，100，1，差不多要27年。

第一次：
计数者出来（必然事件）
剩下99个囚犯
第二次:
新普通囚犯出来（之前未出来过的囚犯）概率：99/100
也就相当于新囚犯出来需要:100/99天
然后等待计数者出来：
概率：1/100
完成这次的平均天数：100天
第三次：
新普通囚犯出来（之前未出来过的囚犯）概率：98/100
也就相当于新囚犯出来需要:100/99天
然后等待计数者出来：
概率：1/100
完成这次的平均天数：100天
.
.
.
.
.
第99次：
新普通囚犯出来（之前未出来过的囚犯）概率：1/100
也就相当于新囚犯出来需要:100/1天
然后等待计数者出来：
概率：1/100
完成这次的平均天数：100天


把所有需要的时间加上：
第一次完成时间   第二次完成时间             第99次完成时间
（100/99+100）+（100/98+100）...........+(100/1+100)
=100*99+100*（1/99+1/98+......+1/1）
=9900+100*(ln99+C)  注（C=0.57722）
=9900+100*5.17233985
=10 417.234

大约需要10 417.234天。换算成年的话28.5403671年～OK

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

public class KingAndPrisoner {

	public static void main(String[] args) {
		List<Prisoner> list = new ArrayList<Prisoner>();
		for(int i = 0;i<100;i++){
			Prisoner p = new Prisoner(i);
			list.add(p);
		}
		boolean light = false;
		int index =0;
		int target = 0;
		int t = 0;
		while(index<100) {
			Random random = new Random();
			int id = random.nextInt(100);
			Prisoner p = list.get(id);
			boolean state = p.isState();
			if(index==0) {
				target = id;
				light = true;
				index++;
			}
			
			if(state==true&&id!=target&&light==true){
				System.out.println("第"+id+"个囚犯出来了");
				light = false;
				p.setState(false);
				index++;
			}
			
			if(target==id&&light==false){
				light = true;
			}
			t++;
		}
		System.out.println("总共用了 "+t+" 次完成任务");
		for(int i = 0;i<100;i++){
			Prisoner p = list.get(i);
			System.out.println("第"+p.getId() +" 个囚犯 state == "+p.isState());
		}
	}
}

class Prisoner {
	
	private int id;
	private boolean state = true;
	
	public Prisoner(int id) {
		super();
		this.id = id;
	}
	public int getId() {
		return id;
	}
	public void setId(int id) {
		this.id = id;
	}
	public boolean isState() {
		return state;
	}
	public void setState(boolean state) {
		this.state = state;
	}
}

囚犯被国王耍了

按照楼主的程序跑了几次，基本上都超过10000天，接近30年了，30年对于一个成年罪犯来说，差不多接近50岁了，如果有囚犯年长些，在狱中老去了或者病逝，全部都是无期徒刑

有意思，哈哈。。。