|
锁定老帖子 主题：国王与100个囚犯
精华帖 (0) :: 良好帖 (0) :: 新手帖 (0) :: 隐藏帖 (6)
|
|
|---|---|
| 作者 | 正文 |
|
发表时间：2010-08-05
只要有任何一个人
计数员站出来就行 |
| 返回顶楼 | |
|
发表时间：2010-08-05
JavaEye4Cwy 写道 love452076852 写道 普通囚犯只有关灯的权利，且只能关一次灯！
计数囚犯只有开灯的权利，只有当灯关着的时候才能开灯。 那么当计数囚犯开满100次灯的时候，就说明一百个囚犯都曾出来过！ 这个人适合解说题目，条理很好，我终于明白了。 不过，感觉LZ提供的思路解决方案不是很好，因为有大量的冗余或时间空白浪费了，继续寻找最佳答案。 因为有这么个情况: 计数员只出来过99次，就再也没被放风出来了，而外面已经放了好几次100个了，请问怎么办？？？ 最后 引用 若干天以后，你们中只要有任何一个人能够向我证明所有的人都曾到院子里去过，你们就全体释放。
你就那么担保国王问的就是计数员？ 蹲监前的15分钟讨论，你以为囚犯们都在讨论打酱油？ 麻烦看题仔细，有点想象能力，拿起半截就跑 还有看不来代码，你何必要当程序员？ |
| 返回顶楼 | |
|
发表时间：2010-08-05
import java.io.FileNotFoundException;
import java.io.PrintStream;
import java.util.Random;
public class Test {
public static void main(String[] args) {
// 将打印结果输出到文本文件里
try {
System.setOut(new PrintStream("c:/Test.txt"));
} catch (FileNotFoundException e) {
e.printStackTrace();
}
// 定义100个犯人
Person[] persons = new Person[100];
// 给100个犯人取名字（编号）
for (int i = 0; i < persons.length; i++) {
persons[i] = new Person();
persons[i].setName("囚犯" + (i + 1) + "号");
}
// 犯人们商量选取一个计数员（随机）
int random = new Random().nextInt(100);
persons[random].setNum(true);
System.out.println("" + persons[random].getName() + "是计数员！");
// 游戏开始
int day = 0;// 记录当前是第几天
boolean light = false;// 灯，true为开，false为关
// 直到计数员记满100次游戏结束
while (persons[random].getCount() < 100) {
day++;
System.out.print("第" + day + "天：");
// 随机抽取犯人
int ran = new Random().nextInt(100);
System.out.print("" + persons[ran].getName() + "出来放风,看见灯是"
+ (light ? "开着的," : "关着的,"));
if (persons[ran].isHasOpen()) {
// 如果犯人开过灯
if (persons[ran].isNum()) {
// 如果他是计数员
if (!light) {
// 如果灯是关着的
System.out
.println("他开过灯,他是计数员,但是灯还是关着,证明计数员上次关灯后没有人新人出来过！");
} else {
// 如果灯是开着的
// 关灯，计数加1
light = false;
persons[ran].setCount(persons[ran].getCount() + 1);
System.out.println("他开过灯,他是计数员,但是灯是开的,证明有新人出来，计数加1！");
}
} else {
// 如果他不是计数员
// 就什么也不做
System.out.println("他已经开过灯,所以什么也不做！");
}
} else {
// 如果犯人没有开过灯
if (persons[ran].isNum()) {
// 如果他是计数员
if (!light) {
// 如果灯是关着的
// 自己开灯又关灯，计数加1
light = true;
light = false;
persons[ran].setHasOpen(true);
persons[ran].setCount(persons[ran].getCount() + 1);
System.out.println("他没有开过灯,他是计数员,于是他打开了灯又关掉灯,计数加1！");
} else {
// 如果灯是开着的
// 关灯，计数加2（因为加上自己的一次）
light = false;
persons[ran].setCount(persons[ran].getCount() + 2);
persons[ran].setHasOpen(true);
System.out.println("他没有开过灯,他是计数员,但是灯是开的所以加上自己的一次计数加2！");
}
} else {
// 如果他不是计数员
if (!light) {
// 如果灯是关着的
// 就打开灯
light = true;
persons[ran].setHasOpen(true);
System.out.println("他没有开过灯,于是他打开了灯！");
} else {
// 如果灯是开着的
// 就什么也不做
System.out.println("他没有开过灯,但是灯是开的所以什么也没有做！");
}
}
}
}
System.out.println("第" + day + "天,如果他们都还没有死的话,就可以向国王证明所有人都出来过！");
}
}
// 犯人类
class Person {
// 犯人的名字（用编号命名）
private String Name;
// 是否开过灯
private boolean hasOpen;
// 是否是计数员
private boolean isNum;
// 如果是计数员，他是第几次关灯
private int count;
public int getCount() {
return count;
}
public void setCount(int count) {
this.count = count;
}
public String getName() {
return Name;
}
public void setName(String name) {
Name = name;
}
public boolean isHasOpen() {
return hasOpen;
}
public void setHasOpen(boolean hasOpen) {
this.hasOpen = hasOpen;
}
public boolean isNum() {
return isNum;
}
public void setNum(boolean isNum) {
this.isNum = isNum;
}
}
重新写了一下，随机的计数员，将结果输出到文本里，控制台好像显示不了那么多.. 当然继续寻找最优算法，才行，这样下去人都死光了... |
| 返回顶楼 | |
|
发表时间：2010-08-05
IcedCoffee 写道
import java.io.FileNotFoundException;
import java.io.PrintStream;
import java.util.Random;
public class Test {
public static void main(String[] args) {
// 将打印结果输出到文本文件里
try {
System.setOut(new PrintStream("c:/Test.txt"));
} catch (FileNotFoundException e) {
e.printStackTrace();
}
// 定义100个犯人
Person[] persons = new Person[100];
// 给100个犯人取名字（编号）
for (int i = 0; i < persons.length; i++) {
persons[i] = new Person();
persons[i].setName("囚犯" + (i + 1) + "号");
}
// 犯人们商量选取一个计数员（随机）
int random = new Random().nextInt(100);
persons[random].setNum(true);
System.out.println("" + persons[random].getName() + "是计数员！");
// 游戏开始
int day = 0;// 记录当前是第几天
boolean light = false;// 灯，true为开，false为关
// 直到计数员记满100次游戏结束
while (persons[random].getCount() < 100) {
day++;
System.out.print("第" + day + "天：");
// 随机抽取犯人
int ran = new Random().nextInt(100);
System.out.print("" + persons[ran].getName() + "出来放风,看见灯是"
+ (light ? "开着的," : "关着的,"));
if (persons[ran].isHasOpen()) {
// 如果犯人开过灯
if (persons[ran].isNum()) {
// 如果他是计数员
if (!light) {
// 如果灯是关着的
System.out
.println("他开过灯,他是计数员,但是灯还是关着,证明计数员上次关灯后没有人新人出来过！");
} else {
// 如果灯是开着的
// 关灯，计数加1
light = false;
persons[ran].setCount(persons[ran].getCount() + 1);
System.out.println("他开过灯,他是计数员,但是灯是开的,证明有新人出来，计数加1！");
}
} else {
// 如果他不是计数员
// 就什么也不做
System.out.println("他已经开过灯,所以什么也不做！");
}
} else {
// 如果犯人没有开过灯
if (persons[ran].isNum()) {
// 如果他是计数员
if (!light) {
// 如果灯是关着的
// 自己开灯又关灯，计数加1
light = true;
light = false;
persons[ran].setHasOpen(true);
persons[ran].setCount(persons[ran].getCount() + 1);
System.out.println("他没有开过灯,他是计数员,于是他打开了灯又关掉灯,计数加1！");
} else {
// 如果灯是开着的
// 关灯，计数加2（因为加上自己的一次）
light = false;
persons[ran].setCount(persons[ran].getCount() + 2);
persons[ran].setHasOpen(true);
System.out.println("他没有开过灯,他是计数员,但是灯是开的所以加上自己的一次计数加2！");
}
} else {
// 如果他不是计数员
if (!light) {
// 如果灯是关着的
// 就打开灯
light = true;
persons[ran].setHasOpen(true);
System.out.println("他没有开过灯,于是他打开了灯！");
} else {
// 如果灯是开着的
// 就什么也不做
System.out.println("他没有开过灯,但是灯是开的所以什么也没有做！");
}
}
}
}
System.out.println("第" + day + "天,如果他们都还没有死的话,就可以向国王证明所有人都出来过！");
}
}
// 犯人类
class Person {
// 犯人的名字（用编号命名）
private String Name;
// 是否开过灯
private boolean hasOpen;
// 是否是计数员
private boolean isNum;
// 如果是计数员，他是第几次关灯
private int count;
public int getCount() {
return count;
}
public void setCount(int count) {
this.count = count;
}
public String getName() {
return Name;
}
public void setName(String name) {
Name = name;
}
public boolean isHasOpen() {
return hasOpen;
}
public void setHasOpen(boolean hasOpen) {
this.hasOpen = hasOpen;
}
public boolean isNum() {
return isNum;
}
public void setNum(boolean isNum) {
this.isNum = isNum;
}
}
重新写了一下，随机的计数员，将结果输出到文本里，控制台好像显示不了那么多.. 当然继续寻找最优算法，才行，这样下去人都死光了... 哈哈，经典，我运行程序，都打印了几百万天了还没完。 |
| 返回顶楼 | |
|
发表时间：2010-08-05
longxiaoyan 写道
IcedCoffee 写道
import java.io.FileNotFoundException;
import java.io.PrintStream;
import java.util.Random;
public class Test {
public static void main(String[] args) {
// 将打印结果输出到文本文件里
try {
System.setOut(new PrintStream("c:/Test.txt"));
} catch (FileNotFoundException e) {
e.printStackTrace();
}
// 定义100个犯人
Person[] persons = new Person[100];
// 给100个犯人取名字（编号）
for (int i = 0; i < persons.length; i++) {
persons[i] = new Person();
persons[i].setName("囚犯" + (i + 1) + "号");
}
// 犯人们商量选取一个计数员（随机）
int random = new Random().nextInt(100);
persons[random].setNum(true);
System.out.println("" + persons[random].getName() + "是计数员！");
// 游戏开始
int day = 0;// 记录当前是第几天
boolean light = false;// 灯，true为开，false为关
// 直到计数员记满100次游戏结束
while (persons[random].getCount() < 100) {
day++;
System.out.print("第" + day + "天：");
// 随机抽取犯人
int ran = new Random().nextInt(100);
System.out.print("" + persons[ran].getName() + "出来放风,看见灯是"
+ (light ? "开着的," : "关着的,"));
if (persons[ran].isHasOpen()) {
// 如果犯人开过灯
if (persons[ran].isNum()) {
// 如果他是计数员
if (!light) {
// 如果灯是关着的
System.out
.println("他开过灯,他是计数员,但是灯还是关着,证明计数员上次关灯后没有人新人出来过！");
} else {
// 如果灯是开着的
// 关灯，计数加1
light = false;
persons[ran].setCount(persons[ran].getCount() + 1);
System.out.println("他开过灯,他是计数员,但是灯是开的,证明有新人出来，计数加1！");
}
} else {
// 如果他不是计数员
// 就什么也不做
System.out.println("他已经开过灯,所以什么也不做！");
}
} else {
// 如果犯人没有开过灯
if (persons[ran].isNum()) {
// 如果他是计数员
if (!light) {
// 如果灯是关着的
// 自己开灯又关灯，计数加1
light = true;
light = false;
persons[ran].setHasOpen(true);
persons[ran].setCount(persons[ran].getCount() + 1);
System.out.println("他没有开过灯,他是计数员,于是他打开了灯又关掉灯,计数加1！");
} else {
// 如果灯是开着的
// 关灯，计数加2（因为加上自己的一次）
light = false;
persons[ran].setCount(persons[ran].getCount() + 2);
persons[ran].setHasOpen(true);
System.out.println("他没有开过灯,他是计数员,但是灯是开的所以加上自己的一次计数加2！");
}
} else {
// 如果他不是计数员
if (!light) {
// 如果灯是关着的
// 就打开灯
light = true;
persons[ran].setHasOpen(true);
System.out.println("他没有开过灯,于是他打开了灯！");
} else {
// 如果灯是开着的
// 就什么也不做
System.out.println("他没有开过灯,但是灯是开的所以什么也没有做！");
}
}
}
}
System.out.println("第" + day + "天,如果他们都还没有死的话,就可以向国王证明所有人都出来过！");
}
}
// 犯人类
class Person {
// 犯人的名字（用编号命名）
private String Name;
// 是否开过灯
private boolean hasOpen;
// 是否是计数员
private boolean isNum;
// 如果是计数员，他是第几次关灯
private int count;
public int getCount() {
return count;
}
public void setCount(int count) {
this.count = count;
}
public String getName() {
return Name;
}
public void setName(String name) {
Name = name;
}
public boolean isHasOpen() {
return hasOpen;
}
public void setHasOpen(boolean hasOpen) {
this.hasOpen = hasOpen;
}
public boolean isNum() {
return isNum;
}
public void setNum(boolean isNum) {
this.isNum = isNum;
}
}
重新写了一下，随机的计数员，将结果输出到文本里，控制台好像显示不了那么多.. 当然继续寻找最优算法，才行，这样下去人都死光了... 哈哈，经典，我运行程序，都打印了几百万天了还没完。
|
| 返回顶楼 | |
|
发表时间：2010-08-05
linghongli 写道 sunson468 写道 Crusader 写道 晕，你自己想想你被关进去后，第一天释放的是你，你知不知道？
看问题不能太死哦~ 这一百人需要决定一个计数者～ 只有计数者才可以开灯，其他的都只能对开着的灯进行且只能进行一次关闭操作 当计数者放出来时如果灯关闭了，则再打开，计数+1 最后也需要计数者宣布结束～～～ 所以不考虑程序的局部变量或者全局变量，现实中确实需要决定一个计数者，可以不是第一个释放的，但必须是一百个人！ 所以我觉得提问者的问题没有错～程序永远只是现实不完全的映射～ 一句话，没搞明白结束条件 结束条件就是计数者计数到100，包括自己～～～ |
| 返回顶楼 | |
|
发表时间：2010-08-05
哈哈，刚才在网上看到一个很雷人的解法...
如下： 本人认为此题与开灯或关灯并没有切实关系；（因为100个人中永远也不会有能够证明每个人都出来过的人出现，此题最重要的就是知情人和他所拥有的证据，因为他在牢里，开关灯不会出现知情人）， 大家应该注意到的是题目中所提到的修理师傅和送饭者（他们对方案带来帮助） 我认为最佳方案是： 每个人第一次出来放风都要拧下一个灯泡，并带回去。（每人只能拿一个，再次出来不再带回） 回去后把灯泡摔破，用碎片划破身体证明出去过。（这是表示自己出去过最有力的证明） 接下来把灯泡的连接处（尾部）交与送饭人，并要求其传递给下一个送饭的人，下一个人再把得到的所有灯泡，交与送饭人。。。继续传递 。。。。 。。传递中。。。。 当拿到100个灯泡尾部的人（就是知情人了，他可以证明所有人出来过） ps:此人rpg任务做多了... |
| 返回顶楼 | |
|
发表时间：2010-08-06
学习算法了。
|
| 返回顶楼 | |
|
发表时间：2010-08-06
感觉这个三十多行代码的东西，何必写得那么复杂呢？？？
|
| 返回顶楼 | |
|
发表时间：2010-08-06
leaphong 写道 感觉这个三十多行代码的东西，何必写得那么复杂呢？？？
二十行左右代码就可以了。 |
| 返回顶楼 | |
