|
锁定老帖子 主题：国王和100个囚犯
精华帖 (0) :: 良好帖 (10) :: 新手帖 (0) :: 隐藏帖 (8)
|
|
|---|---|
| 作者 | 正文 |
|
发表时间：2010-01-19
最后修改：2010-01-20
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 + "年");
}
}
很明确的条件：
|
| 返回顶楼 | |
|
发表时间：2010-01-21
最后修改：2010-01-22
开始 2010-01-22 12:57:36 运行10次,囚犯共100人 最小的是：9162天 最大的是：11761天 结束 2010-01-22 13:08:01 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);
}
}
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();
}
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());
}
}
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;
}
}
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;
}
}
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++;
}
}
package game.bean;
/**
* 人
* @author Administrator
*
*/
public class Person {
//属于国王
private King king;
public King getKing() {
return king;
}
public void setKing(King king) {
this.king = king;
}
}
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;
}
}
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;
}
}
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;
}
}
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();
}
}
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);
}
}
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();
}
}
|
| 返回顶楼 | |
|
发表时间：2010-02-03
kingkan 写道
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 + "年");
}
}
很明确的条件：
|
| 返回顶楼 | |
|
发表时间：2010-02-04
楼上的方法还是不行，如果灯最开始是关着的，你计数到197次完全有可能其它囚房只出来过98个，每个人出来两次。
|
| 返回顶楼 | |
|
发表时间：2010-02-04
除了计算员计数到198次可以确保所有人都出来过，还有一种方法应该也行，呵呵。
我的思路是： 1、每个人第一次出来时都改变灯的状态并记住。 2、每个人以后每次出来只要看到灯的状态较上一次改变了就累加计数值1，然后改变灯的状态并记住。 3、任意一个人的计数值累加到99就可以确保每个人都出来过了。 |
| 返回顶楼 | |
|
发表时间：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);
}
}
俺也写了个，不知道对不对。 |
| 返回顶楼 | |
|
发表时间：2010-02-04
一百次。。。
max:12706 min:8010 |
| 返回顶楼 | |
|
发表时间：2010-02-04
恩。。。那代码有错误，确实随即初始化灯状态不好搞！
我认错！！！ |
| 返回顶楼 | |
|
发表时间：2010-02-05
这个问题，不知道囚犯们知道不知道灯的初始状态。 如果知道那么稍微简单点，因为第一个出去的肯定知道自己是不是技数员，有他来计数就好了。
我来说说如果不知道灯的初始状态，大家看看我想的对不对，指定一个计数员，我们叫他老A。 规则是，只有老A可以开灯，其他人只能关灯，关过一次的人不允许再关。 当老A第一次出来后，他看到灯关着，肯定会想，灯是被第一个人关掉的，还是初始状态就是关掉的。 保险起见，就必须当成没有人出来过，然后那个第一个关灯的人，就必须再关一次，这样就不会漏了他。 然后就简单了，老A开灯，其他人关灯，当老A第99次看到灯被关了，就大功告成。 |
| 返回顶楼 | |
|
发表时间：2010-02-08
国王
package com.xuz.persionbreak.gamecontrol;
import java.util.Random;
public class King {
public static int getNum(){
Random random = new Random();
return random.nextInt(100) ;
}
}
抽象类-犯人
package com.xuz.persionbreak.gamer;
public abstract class Person {
}
普通犯人
package com.xuz.persionbreak.gamer;
import com.xuz.persionbreak.lamp.Lamp;
public class Persioner extends Person{
private int count = 0;
public void controlLamp(Lamp lamp){
if (count < 1) { //如果之前没关过
if (lamp.getState() == 1) { //如果灯是开的
lamp.setState(0); //关灯
System.out.println("我关灯了，以后没我事了");
} else {
System.out.println("灯是关着的");
}
} else {
System.out.println("我之前关过灯了");
}
}
}
计数员
package com.xuz.persionbreak.gamer;
import com.xuz.persionbreak.lamp.Lamp;
public class Counter extends Person{
private int count = 0;
private boolean isOpenLamp = false;
public void controlLamp(Lamp lamp){
if (lamp.getState() == 0) {
if (isOpenLamp) {
count++;
lamp.setState(1);
System.out.println("已经出来过"+count+"个哥们了");
} else {
lamp.setState(1);
System.out.println("我第一次出来，开灯!");
isOpenLamp = true;
}
} else {
System.out.println("灯是开的");
}
}
public int getCount(){
return count;
}
}
应用场景
package com.xuz.persionbreak.main;
import com.xuz.persionbreak.gamecontrol.King;
import com.xuz.persionbreak.gamer.Counter;
import com.xuz.persionbreak.gamer.Persioner;
import com.xuz.persionbreak.gamer.Person;
import com.xuz.persionbreak.lamp.Lamp;
public class Main {
/**
* @param args
*/
public static void main(String[] args) {
int day = 0;
Lamp lamp = new Lamp();
lamp.setState(0);//一开始灯是关的
Person[] foxRiver = new Person[100];
for (int i = 0; i < foxRiver.length - 1; i++) {
foxRiver[i] = new Persioner();
}
foxRiver[99] = new Counter();
System.out.println("游戏开始");
while (true) {
day++;
int random = King.getNum();
System.out.println("放出"+random+"牢房的犯人");
Person person = foxRiver[random];
if (person instanceof Persioner) {
((Persioner) person).controlLamp(lamp);
} else {
Counter counter = (Counter)person;
counter.controlLamp(lamp);
if (counter.getCount() == 99) {
break;
}
}
}
System.out.println(day / 365);
}
}
作为一个仁主，我一开始就把灯关了。 |
| 返回顶楼 | |
