国王和100个囚犯 -

lolopig

浏览: 7511 次
性别:
来自: 厦门

最近访客更多访客>>

博主相关

博客

微博

相册

留言

关于我

文章分类

社区版块

存档分类

国王和100个囚犯

游戏能源面试多线程 J#

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

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

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

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

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

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

public interface Demo {
	
	public void doBool(); 

}

public class Demo2 implements Demo{
	
	/**
	 * 普通囚犯
	 * 第一次见灯开着时关掉
	 * 无论出去多少回，只能关灯一次
	 */
	
	public int count = 0;
	public boolean first = true;
	public String name;
	
	@Override
	public void doBool() {
		// TODO Auto-generated method stub
		if(Test.bool && first){
			Test.bool = false;
			first = false;
		}
		count++;
	}
}

public class Demo3 implements Demo{
	
	/**
	 * 计数员
	 * 出去后就开灯
	 * 如果开着就不去动他
	 * 
	 * 直到第99次出去关灯的时候就是100个人都出去过了
	 */
	
	public int closeCount = 0;
	public String name;
	
	@Override
	public void doBool() {
		// TODO Auto-generated method stub
		if(!Test.bool){
			Test.bool = true;
			closeCount++;
			if(closeCount == 99){
				Test.ok = true;
			}
		}
	}
}

public class Test {

	public static boolean bool = false;
	public static boolean ok = false;

	public static void main(String[] args) {
		int num = 0;
		int count = 0;
		Demo[] demo = new Demo[100];
		Demo2 demo2;
		for (int i = 1; i <= 99; i++) {
			demo2 = new Demo2();
			demo2.name = "d" + i;
			demo[i - 1] = demo2;
		}
		Demo3 demo3 = new Demo3();
		demo3.name = "d100";
		demo[99] = demo3;

		while (true) {
			num = (int) (Math.random() * 100);
			demo[num].doBool();
			count++;
			if (ok)
				break;
		}

		for (int j = 0; j < demo.length - 1; j++) {
			Demo2 d2 = (Demo2) demo[j];
			System.out.println(d2.name + ":" + d2.count);
		}
		System.out.println("执行次数:" + count);
	}
}

代码写的不好。

分享到：

js浮点数的加减乘除运算函数

2010-01-13 14:53
浏览 4391
评论(105)
论坛回复 / 浏览 (105 / 36154)
分类:编程语言
查看更多

85 楼 jahcy 2010-02-04

public class Lamp {
	public enum LampStatus {
		ON,
		OFF
	};
	
	private LampStatus status = (Math.round(Math.random() * 10) % 2 == 0) ?  LampStatus.ON : LampStatus.OFF; 
	
	private int MAX = 100;
	private int dayCount = 0;
	private int personCount = 0;
	
	public boolean changeStatus(boolean isCounter, boolean isFirst) {
		dayCount++;
		
		if(isCounter) {
			if(isFirst && status == LampStatus.ON) {
				status = LampStatus.OFF;
			}
			else if(!isFirst && status == LampStatus.ON) {
				if(personCount++ == MAX) {
					return true;
				}
			}
			
			return false;
		}
		else {
			if(isFirst && status == LampStatus.ON) {
				status = LampStatus.OFF;
			}
			else if(!isFirst && status == LampStatus.OFF) {
				status = LampStatus.ON;
			}
			
			return false;
		}
	}
	
	public static class Person {
		boolean isCounter = false;
		boolean isFirst = true;
		Lamp lamp;
		
		public boolean doIt() {
			boolean sign = lamp.changeStatus(isCounter, isFirst);
			if(isFirst) isFirst = false;
			return sign;
		}
	}
	
	public static void main(String[] args) {
		Lamp lamp = new Lamp();
		
		Person[] persons = new Person[lamp.MAX];
		for (int i = 0; i < persons.length; i++) {
			persons[i] = new Person();
			persons[i].lamp = lamp;
		}
		
		
		persons[(int)Math.floor(Math.random() * lamp.MAX)].isCounter = true;
		
		while(!persons[(int)Math.floor(Math.random() * lamp.MAX)].doIt());
		System.out.println(lamp.dayCount);
		System.out.println(lamp.personCount - 1);
	}
}

俺也写了个，不知道对不对。

84 楼 liyun_1981 2010-02-04

除了计算员计数到198次可以确保所有人都出来过，还有一种方法应该也行，呵呵。
我的思路是：
1、每个人第一次出来时都改变灯的状态并记住。
2、每个人以后每次出来只要看到灯的状态较上一次改变了就累加计数值1，然后改变灯的状态并记住。
3、任意一个人的计数值累加到99就可以确保每个人都出来过了。

83 楼 liyun_1981 2010-02-04

楼上的方法还是不行，如果灯最开始是关着的，你计数到197次完全有可能其它囚房只出来过98个，每个人出来两次。

82 楼 rukyo 2010-02-03

<div class="quote_title">kingkan 写道</div>
<div class="quote_div">
<pre name="code" class="java">import java.util.ArrayList;
import java.util.List;
import java.util.Random;
public class Perisoner {
private int turnCount = 0;
private boolean isTotaller;
public Perisoner(boolean isTotaller) {
this.isTotaller = isTotaller;
}
public void totalTurnCount(){
this.turnCount++;
}
public int getTurnCount(){
return this.turnCount;
}
public boolean getIsTotaller(){
return this.isTotaller;
}

public static void main(String[] args) {
int sum = 100;// 总人数
List<Perisoner> List = new ArrayList<Perisoner>();
for(int i=0;i<(sum-1);i++){
Perisoner p = new Perisoner(false);//一般囚犯99个，false参数意思只负责关灯
List.add(p);
}
Perisoner totalPerisoner = new Perisoner(true);//记数员囚犯，true参数意思只负责开灯
List.add(totalPerisoner);//下标0~99

int day = 0;
Random random = new Random();
boolean lightStatus = random.nextBoolean(); //灯的最初状态随机
while(true){
day++;
int pid = random.nextInt(sum);//0~99
Perisoner p = List.get(pid);
if(p.getIsTotaller()){//记数员囚犯
if(!lightStatus){//如果灯是暗的
if(p.getTurnCount()<((sum-1)*2-1)){//判断他的开灯次数如果不够(100-1)*2-1=197次的话，那就开灯，否则不动
lightStatus = true;
p.totalTurnCount();
}else{//如果到达到197次开了的灯被人关灯，那么就证明全部人都出来一次了
break;
}
}//如果灯是亮的,那就不动
}else{//一般囚犯
if(lightStatus){//如果灯是亮的
if(p.getTurnCount()<2){//判断他的关灯次数如果不够2次的话，那就关灯，否则不动
lightStatus = false;
p.totalTurnCount();
}
}//如果灯是暗的,那就不动
}
}
System.out.println("需要总天数是：" + day + ",已经过去了：" + day/365 + "年");
}
}</pre>
 很明确的条件： 1、每人一间牢房，都与外界隔绝，什么也听不见、看不到，连时间都没法计算 说明：没有人知道自己是第几天出来，所以不要再讨论说哪个囚犯是第一天出来就是记数员 2、每天会随机（注意是完全随机）打开一间牢房的门，让那个囚犯到院子里来放风。 说明：随机抽取，囚犯只能知道自己出来跟回去，以及看到灯的状态 我们在这里，只是为解题而解题，不需要考虑题目本身的问题，不用管花了多少天多少年，国王是否会死掉的情况。 如果条件是每10分钟随机放一个囚犯出来，那就快很多了，所以没必要去理会命题本身的合理性，只要考虑是否有 100%的不失误的方案，不带一丝侥幸。 解题方案： 1、指定99个一般囚犯，他们的有两个行为：一是把状态是开的灯关掉，否则不动；二是统计自己关掉灯的次数，如果有两次后，就再也不去开或者关这个灯。 2、指定1个记数员囚犯，他只有两个行为：一是把状态是关的灯打开，否则不动；二是负责统计从自己第一次（注意：不是第一天）出来开始算，（如果自己第一次出来灯是亮的，那么证明自己是第一个出来，同时也证明灯开始状态是亮的；如果自己第一次出来灯是暗的，那无法确认灯开始的状态以及自己是第几个出来）灯的被关次数达到197次，那么就可以确认所有的人都曾到院子里去过。
 
</div>
 这个答案够严谨妥当。

81 楼 yanghao0 2010-01-21

<pre name="code" class="java">开始 2010-01-22 12:57:36
运行10次,囚犯共100人
最小的是：9162天
最大的是：11761天
结束 2010-01-22 13:08:01
</pre>
<pre name="code" class="java">package game;

import game.bean.King;
import game.service.Service;
import game.service.ServiceImpl;
import game.util.Logs;

import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Calendar;
import java.util.Date;

/**
* 开始
* @author Administrator
*
*/
public class Start {

public static void main(String[] args) {

Service start = new ServiceImpl();
try {
System.out.println("开始 "+getNowStr());
//测试次数
int c = 10;
int[] all = new int[c];
for(int i=0;i<all.length;i++){
all[i] = start.play(start.init());
Logs.clear();
}
//排序统计
Arrays.sort(all);
System.out.println("运行"+c+"次,囚犯共"+King.SIZE+"人");
System.out.println("最小的是："+all[0]+"天");
System.out.println("最大的是："+all[all.length-1]+"天");
System.out.println("结束 "+getNowStr());
} catch (Exception e) {
e.printStackTrace();
}
}

public static String getNowStr() {
Calendar calendar = Calendar.getInstance();
Date date = calendar.getTime();
SimpleDateFormat sdf = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
return sdf.format(date);
}

}
</pre>
 
<pre name="code" class="java">package game.service;

import game.bean.King;

public interface Service {
/**
* 初始化
*/
public King init() throws Exception;
/**
* 游戏开始
* @param king
*/
public int play(King king) throws Exception;
/**
* 结束
*/
public void end();

}</pre>
 
<pre name="code" class="java">package game.service;

import game.bean.King;
import game.bean.Light;
import game.bean.Manager;
import game.bean.Prison;
import game.bean.Prisoner;
import game.bean.Room;
import game.util.Logs;

import java.util.List;
import java.util.Map;

public class ServiceImpl implements Service {

public King init() throws Exception {
//有个国王
King king = new King();
//国王有100个囚犯
List<Prisoner> prisoners = king.getPrisoners(King.SIZE);
//把他们关到监狱的房间里
king.getPrison().custody(prisoners);
//随意指定某人为记数人
int i = (int)(Math.random() * prisoners.size());
Manager manager = new Manager(prisoners.get(i));
king.getPrison().setManager(manager);

return king;
}

public int play(King king) throws Exception {
//国王的监狱
Prison prison = king.getPrison();
//监狱所有房间
Map<String, Room> rooms = prison.getRooms();
//管理员
Manager manager = prison.getManager();
/*
* 如果记数员记录没有达到99次,继续，否则结束
*/
while(true){
if(manager.getCloseCount()<King.SIZE-1){
//记录一天
manager.addDay();
operationLight(prison,rooms,manager);
}else{
return Logs.prisoners.size();
}
Thread.sleep(5);
}
}

public void operationLight(Prison prison, Map<String, Room> rooms, Manager manager){
//每天随机打开一个房间
List<String> codes = prison.getKeys();
int i = (int)(Math.random() * codes.size());
String roomCode = codes.get(i);
Room room = rooms.get(roomCode);
//放出的犯人
Prisoner prisoner = room.getPrisoner();
//记录放出的人
Logs.calendar(prisoner);
//监狱院子的灯
Light light = prison.getYard().getLight();
/*
* 如果是管理员,且灯是开着的，
* 则关灯，并记数一次
*/
if(manager.getCode().equals(prisoner.getCode())){
if(Light.OPEN.equals(light.getStatus())){
light.close();
manager.addCount();
}
}else{
/*
* 如果囚犯没有碰过灯，且灯是关着的
* 则囚犯把灯打开
*/
if(prisoner.isOpened()==false&&Light.CLOSE.equals(light.getStatus())){
light.open();
prisoner.setOpened(true);
}
}
}

public void end() {
// System.out.println(Logs.prisoners.size());
}

}
</pre>
 
<pre name="code" class="java">package game.bean;

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

/**
* 国王
* @author Administrator
*
*/
public class King {
//犯人数
public static int SIZE = 100;
//一个监狱
private Prison prison;

public Prison getPrison() {
return prison;
}
public void setPrison(Prison prison) {
this.prison = prison;
}

public King(){
this.prison = new Prison();
}

//有100个囚犯
public List<Prisoner> getPrisoners(int count){
List<Prisoner> prisoners = new ArrayList<Prisoner>();
for(int i=0;i<count;i++){
Prisoner prisoner = new Prisoner();
String code = "p_"+i;
prisoner.setCode(code);
prisoners.add(prisoner);
}
return prisoners;
}

}
</pre>
 
<pre name="code" class="java">package game.bean;

/**
* 路灯
* @author Administrator
*
*/
public class Light {

public static String OPEN = "open";
public static String CLOSE = "close";

//开关 close关 open开
private String status;

public String getStatus() {
return status;
}

public void setStatus(String status) {
this.status = status;
}

public Light(){
//初始化-关
this.status = this.CLOSE;
}

public void open(){
this.status = this.OPEN;
}

public void close(){
this.status = this.CLOSE;
}

}
</pre>
 
<pre name="code" class="java">package game.bean;

/**
* 记数人
* @author Administrator
* 继承子囚犯
*/
public class Manager extends Prisoner {

//关灯次数记录
private Integer closeCount;
//过去的天数
private Integer days;

public Integer getCloseCount() {
return closeCount;
}

public void setCloseCount(Integer closeCount) {
this.closeCount = closeCount;
}

public Integer getDays() {
return days;
}

public void setDays(Integer days) {
this.days = days;
}

public Manager(Prisoner prisoner){
this.code = prisoner.code;
this.opened = prisoner.opened;
this.closeCount = Integer.parseInt("0");
this.days = Integer.parseInt("0");
}

public void addCount() {
closeCount++;

}

public void addDay() {
days++;
}

}
</pre>
 
<pre name="code" class="java">package game.bean;

/**
* 人
* @author Administrator
*
*/
public class Person {

//属于国王
private King king;

public King getKing() {
return king;
}

public void setKing(King king) {
this.king = king;
}

}
</pre>
 
<pre name="code" class="java">package game.bean;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;

/**
* 监狱
* @author Administrator
*
*/
public class Prison {
//监狱有个院子
private Yard yard;
//监狱有很多牢房
private Map<String,Room> rooms;
//目前有?个房间
public static int SIZE = King.SIZE;
//指定的代表
private Manager manager;
//房间钥匙
private List<String> keys;

public Manager getManager() {
return manager;
}
public void setManager(Manager manager) {
this.manager = manager;
}
public Yard getYard() {
return yard;
}
public void setYard(Yard yard) {
this.yard = yard;
}
public Map<String, Room> getRooms() {
return rooms;
}
public void setRooms(Map<String, Room> rooms) {
this.rooms = rooms;
}

public Prison(){
this.yard = new Yard();
this.rooms = new HashMap();
this.keys = new ArrayList();
//初始化房间
for(int i=0;i<this.SIZE;i++){
Room room = new Room();
//房间编号
String roomCode = "r_"+i;
room.setRoomCode(roomCode);
keys.add(roomCode);
this.rooms.put(room.getRoomCode(), room);
}
}
public void custody(List<Prisoner> prisoners) throws Exception {
int i = 0;
Iterator<Room> iterator = rooms.values().iterator();
while(iterator.hasNext()){
Room room = iterator.next();
Prisoner prisoner = prisoners.get(i);
room.setPrisoner(prisoner);
i++;
}
}
public List<String> getKeys() {
return keys;
}
public void setKeys(List<String> keys) {
this.keys = keys;
}

}
</pre>
 
<pre name="code" class="java">package game.bean;

/**
* 犯人
* @author Administrator
* extends Person
*/
public class Prisoner extends Person {

public static String OPEN = "open";
public static String CLOSE = "close";

//编号
protected String code;
//开灯记忆
protected boolean opened;
//在干嘛
protected String doing;

public String getCode() {
return code;
}
public void setCode(String code) {
this.code = code;
}
public boolean isOpened() {
return opened;
}
public void setOpened(boolean opened) {
this.opened = opened;
}
public String getDoing() {
return doing;
}
public void setDoing(String doing) {
this.doing = doing;
}

}
</pre>
 
<pre name="code" class="java">package game.bean;

/**
* 囚犯房间
* @author Administrator
*
*/
public class Room {
//房间编号
private String roomCode;
//一个房间关一个囚犯
private Prisoner prisoner;

public String getRoomCode() {
return roomCode;
}
public void setRoomCode(String roomCode) {
this.roomCode = roomCode;
}
public Prisoner getPrisoner() {
return prisoner;
}
public void setPrisoner(Prisoner prisoner) {
this.prisoner = prisoner;
}

}
</pre>
 
<pre name="code" class="java">package game.bean;

/**
* 供犯人放风的院子
*
* @author Administrator
*
*/
public class Yard {
//院子里有个灯
private Light light;

public Light getLight() {
return light;
}

public void setLight(Light light) {
this.light = light;
}

public Yard(){
this.light = new Light();
}

}
</pre>
 
<pre name="code" class="java">package game.util;

import java.text.SimpleDateFormat;
import java.util.Date;

public class Message {

private String seq;

private String message;

private Exception exception;

public Message(String str, Exception e) {
this.seq = setAutoSeq();
this.message = str;
this.exception = e;
}

public Message() {
this.seq = setAutoSeq();
}

public String getMessage() {
return message;
}

public void setMessage(String message) {
this.message = message;
}

public Exception getException() {
return exception;
}

public void setException(Exception exception) {
this.exception = exception;
}

public String getSeq() {
return seq;
}

public void setSeq(String seq) {
this.seq = seq;
}

private String setAutoSeq(){
Date date = new Date();
SimpleDateFormat sdf = new SimpleDateFormat("yyyyMMddHHmmss");
return sdf.format(date);
}

}
</pre>
 
<pre name="code" class="java">package game.util;

import game.bean.Prisoner;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Logs {

public static Map<String,Message> map = new HashMap();

public static List<Prisoner> prisoners = new ArrayList();

Logs(){

}

public static void add(Message m){
map.put(m.getSeq(), m);
}

public static void add(String str,Exception e){
Message m = new Message(str,e);
map.put(m.getSeq(), m);
}

public static void calendar(Prisoner prisoner) {
prisoners.add(prisoner);
}

public static void clear(){
map.clear();
prisoners.clear();
}
}
</pre>

80 楼 kingkan 2010-01-19

<pre name="code" class="java">import java.util.ArrayList;
import java.util.List;
import java.util.Random;
public class Perisoner {
private int turnCount = 0;
private boolean isTotaller;
public Perisoner(boolean isTotaller) {
this.isTotaller = isTotaller;
}
public void totalTurnCount(){
this.turnCount++;
}
public int getTurnCount(){
return this.turnCount;
}
public boolean getIsTotaller(){
return this.isTotaller;
}

public static void main(String[] args) {
int sum = 100;// 总人数
List<Perisoner> List = new ArrayList<Perisoner>();
for(int i=0;i<(sum-1);i++){
Perisoner p = new Perisoner(false);//一般囚犯99个，false参数意思只负责关灯
List.add(p);
}
Perisoner totalPerisoner = new Perisoner(true);//记数员囚犯，true参数意思只负责开灯
List.add(totalPerisoner);//下标0~99

int day = 0;
Random random = new Random();
boolean lightStatus = random.nextBoolean(); //灯的最初状态随机
while(true){
day++;
int pid = random.nextInt(sum);//0~99
Perisoner p = List.get(pid);
if(p.getIsTotaller()){//记数员囚犯
if(!lightStatus){//如果灯是暗的
if(p.getTurnCount()<((sum-1)*2-1)){//判断他的开灯次数如果不够(100-1)*2-1=197次的话，那就开灯，否则不动
lightStatus = true;
p.totalTurnCount();
}else{//如果到达到197次开了的灯被人关灯，那么就证明全部人都出来一次了
break;
}
}//如果灯是亮的,那就不动
}else{//一般囚犯
if(lightStatus){//如果灯是亮的
if(p.getTurnCount()<2){//判断他的关灯次数如果不够2次的话，那就关灯，否则不动
lightStatus = false;
p.totalTurnCount();
}
}//如果灯是暗的,那就不动
}
}
System.out.println("需要总天数是：" + day + ",已经过去了：" + day/365 + "年");
}
}</pre>
 很明确的条件： 1、每人一间牢房，都与外界隔绝，什么也听不见、看不到，连时间都没法计算 说明：没有人知道自己是第几天出来，所以不要再讨论说哪个囚犯是第一天出来就是记数员 2、每天会随机（注意是完全随机）打开一间牢房的门，让那个囚犯到院子里来放风。 说明：随机抽取，囚犯只能知道自己出来跟回去，以及看到灯的状态 我们在这里，只是为解题而解题，不需要考虑题目本身的问题，不用管花了多少天多少年，国王是否会死掉的情况。 如果条件是每10分钟随机放一个囚犯出来，那就快很多了，所以没必要去理会命题本身的合理性，只要考虑是否有 100%的不失误的方案，不带一丝侥幸。 解题方案： 1、指定99个一般囚犯，他们的有两个行为：一是把状态是开的灯关掉，否则不动；二是统计自己关掉灯的次数，如果有两次后，就再也不去开或者关这个灯。 2、指定1个记数员囚犯，他只有两个行为：一是把状态是关的灯打开，否则不动；二是负责统计从自己第一次（注意：不是第一天）出来开始算，（如果自己第一次出来灯是亮的，那么证明自己是第一个出来，同时也证明灯开始状态是亮的；如果自己第一次出来灯是暗的，那无法确认灯开始的状态以及自己是第几个出来）灯的被关次数达到197次，那么就可以确认所有的人都曾到院子里去过。

79 楼 dch1287 2010-01-17

bencode 写道

第一天出来的人，担当“计数者”，它把灯开起来（原来开着就不必动了）

然后每天出来一个囚犯。

如果他不是“计数者”，并且没有关过灯，并且灯开着，那么就把灯关了。

如果他是“计数者”，如果灯关了，就把他开起来（计数+1）。当然如果灯被关了99次，那么就去和国王说吧。

不需要这么久，只要 28~29年就行了。

http://bencode.iteye.com/admin/blogs/572294

题目描述里面很清楚地表达了，你无法知道你是不是第一天出来的！！

78 楼 wangxb_st 2010-01-16

day = 0
prison =  Hash.new
light_state = rand(2)
light_count = 0
puts "light initialize state #{light_state}"
while light_count < 99 do
	day += 1
	i = rand(100)   # 0 - 99
	if light_state == 0
		if i > 0 && prison[i].nil?
			light_state = 1
			prison[i] = 1
		end
	else
		if i == 0
			light_state = 0
			light_count += 1
		end
	end
end
puts day, day/365

77 楼 bencode 2010-01-16

76 楼 firefly1314 2010-01-16

dch1287 写道

yahreso 写道

我的策略是：计数囚犯开了几次就算曾出去过多少人，到100为止，其他囚犯只管关

如果灯一开始是关的，其他囚犯先出去也不会有动作，从计数囚犯开灯开始，计数囚犯开第100次灯的时候就可以确定100人都出来了（因为有99次灯被其他囚犯熄灭了，最后一个是他自己）。

如果灯一开始是亮的，
若第一个出来的是计数囚犯，就当作是自己开灯，计数+1。
若第一个出来的是其他囚犯，直接熄灭，之后就和灯初始是关的一样……

最后一句的省略号就是你的问题所在!!
“之后就和灯初始是关的一样” 就是这里不一样

C 计数囚犯
P 其他囚犯

规则：
1. P 熄灯， C 开灯
2. C 第一次出来看到灯亮计数初始为 1 ，否则计数初始为 0
3. C 每次开灯计数加 1
4. 每 P 只可熄 1 次灯
5. 计数值到 100 ，判定所有 P 都出来过了

第一个出来的 P 熄灭了灯，但是 C 出来后却不知道灯是原来就灭的，还是被别人熄灭的
1. 如果是本来就灭的，没问题，他以后还可以开 99 次灯，也就是明确有 99 人出来过
2. 如果是被别人熄灭的，他就只能开 98 次灯了，因为那个第一个出来关灯的囚犯不会再熄灭灯了，他已经熄过 1 次了，那 C 只能确定有 98 人出来过

所以每 P 只能熄 1 次灯的方法在逻辑上无法严密

---

前面有人提到每 P 熄 2 次灯，应该是可行的
计数到 198 就可以肯定所有 P 都出来过了
只不过不能肯定是不是每 P 都出来过 2 次了，有可能有一 P 只出来过 1 次。

C 计数囚犯
P 其他囚犯

灯初始状态未知的情况下，可行的规则：
1. P 熄灯， C 开灯
2. C 第一次出来看到灯亮，计数初始为 1 ，否则计数初始为 0
3. C 每次开灯计数加 1
4. 每 P 可熄 2 次灯
5. 计数值到 198 ，判定所有 P 都出来过了

btw: 如果运气一般，出来也要四五十年了。。。

这个方法可行啊，确实，计数198次就不会存在初始时灯的状态不确定带来的问题了。
不过，他们离自由的日子又延长了～～～～

75 楼 yahreso 2010-01-16

Orz 没考虑到一个囚犯只能熄一次灯……
这样若灯一开始就亮着，如果囚犯是前多少次能熄灯，在计数囚犯之前的都会少 - 口-

74 楼 lishuanglin52130 2010-01-16

呵呵，题目蛮有意思...大概理解了楼主的设计思路...主要利用计数员的开灯...跟囚犯的关灯..计算count的值.
请楼主赐教...

73 楼 dch1287 2010-01-16

yahreso 写道

72 楼 funcreal 2010-01-15

yahreso 写道

hrwhat 写道

yahreso 写道

可是你无法确定谁是第一个出来的

不管灯是明暗，其他囚犯做什么都不影响，只从计数的第一次出来开始置1，接着计数的每次出来若发现灯是暗的需要开灯时就++……

假设你是计数者，你第一次出去的时候看到灯是灭的，你会做什么？
如果灯一开始是灭的，那么没问题，开灯计数即可。
如果灯一开始是亮的，那么一定是别人熄灭的，那么你开灯计数的话岂不是少了一个熄灯的人吗？因为一开始熄灯的人已经熄过一次了，而且他再也不会熄第二次了。所以永远只能数到98个人。

不知道说得对不对。

71 楼 yahreso 2010-01-15

hrwhat 写道

yahreso 写道

可是你无法确定谁是第一个出来的

不管灯是明暗，其他囚犯做什么都不影响，只从计数的第一次出来开始置1，接着计数的每次出来若发现灯是暗的需要开灯时就++……

70 楼 hrwhat 2010-01-15

yahreso 写道

可是你无法确定谁是第一个出来的

69 楼 yahreso 2010-01-15

68 楼 jansel 2010-01-15

既然不知道第一次是不是OK的，那么就循环两次，记录198次就可以了。

如果第一次记录是对的，那么理应会有99*2=198次。

如果第一次记录是错的，那么理应会到99*2+1=199次，但是记录198次也就可以了，因为这时囚犯都已经出去过了，只不过有一个囚犯出去一次罢了。

67 楼 dsjt 2010-01-15

lolopig 写道

我的理解是记数员是不是第一个出去的没有关系，灯的初始状态也没有关系。
记数员自己第一次出去发现灯是关的，那么99次就可以了。
如果记数员第一次出去发现灯是开的，那么为了保证万无一失，多记数一次就可以了。

灯的初始状态肯定有关系

如果技术员第一发现灯是关着的，他如何知道是被别的囚犯关闭的还是本来灯就关闭？
如果被别的囚犯关闭，他最多只能打开99次，
如果灯初始状态就是关闭，他能打开100次！

66 楼 dsjt 2010-01-15

import java.util.Random;

import java.util.Random;

public class Perisoner {

private boolean lightOn;
private int sum = 100;// 总人数
private boolean[] isOut = new boolean[sum];// 记录每个囚犯是否放过风
private final int counterId = 0;// 计数人id;
private int count = 0;// 计数次数
private int days = 0;
private Random rand = new Random();
private final boolean primaryLightOn; //灯的最初是否亮着

public Perisoner() {
this.lightOn = rand.nextBoolean();// 随机生成灯的初始状态
this.primaryLightOn = lightOn;
}

public void out() {
while (true) {
int id = rand.nextInt(sum);
days++;

if (isOut[id]) {// 如果已经出去过
continue;
}

if (id == counterId) {// 如果是计数人
if (!lightOn) {
lightOn = true;
count++;
}

} else {// 如果不是计数人
if (lightOn) {
lightOn = false;
isOut[id] = true;
}
}

/*
*如果灯最初是开着的，计数 sum-1次终止 ---问题就在这里！！
*/
if (primaryLightOn && (count == sum - 1)) {
break;
}

/*
* 如果灯最初是关着的，计数sum次终止
*/
if (count == sum) {
break;
}

}
}

public int getDays() {
return days;
}

public static void main(String[] args) {
Perisoner p = new Perisoner();
System.out.println("灯最初状态：" + p.lightOn);
p.out();
System.out.println("总天数" + p.getDays());
}

}

==========

计数人只能开灯，普通囚犯只能关灯，并且只能关一次；
如果灯最初是关着的，普通囚犯必须等计数人把等打开才能操作，计数人需要开灯 1+99 次才能确定
如果灯最初是开着的，普通囚犯可以直接把他关闭，计数人只需要开灯 99 次即可，并且不可能再有第100次

这样计算，结果是10000天左右

==========

但问题出在，如果囚犯不知道最初灯是开是关，计数人就不知道要计数 99次，还是100次！！

只能按100次算，但是，如果灯最初就是亮着的，他最多计只能数到 99次，这样他们死定了！！

« 上一页 1 2 3 4 5 6 下一页 »

发表评论

您还没有登录,请您登录后再发表评论

最近访客更多访客>>

博主相关

文章分类

社区版块

存档分类

最新评论

国王和100个囚犯

评论

发表评论

相关推荐

最近访客 更多访客>>

博主相关

文章分类

社区版块

存档分类

最新评论

国王和100个囚犯

评论

发表评论

相关推荐

最近访客更多访客>>