囚犯点灯 - 辕门射虎 - 轩辕春秋文化论坛 20周年


	沈沉沦

组别	百姓
级别	破贼校尉
功绩	1
帖子	99
编号	45224
注册	2005-8-9

#1

发表于 2007-6-27 16:36 资料短消息只看该作者

囚犯点灯

有100个无期徒刑囚，被关在100个独立的小房间，互相无法通信。每天会有一个囚徒被随机地抽出来放风，随机就是说可能被抽到多次。放风的地方有一盏灯，囚徒可以打开或者关上，除囚徒外，没有别人会去动这个灯。每个人除非出来放风，是看不到这个灯的。一天，全体囚徒大会，国王大赦，给大家一个机会：如果某一天，某个囚徒能够明确表示，所有的囚徒都已经被放过风了，而且的确如此，那么所有囚徒放；如果仍有囚徒未被放过风，那么所有的囚徒一起处死！囚徒大会后给大家20分钟时间讨论，囚徒们能找到方法么？
提示:用计算机的语言来解题.

[广告] 真诚支持说岳，携手共创辉煌


	天宫公主 (司徒家的颖颖)


	虞国公主 ★

组别	限制发言用户
级别	大将军
好贴	6
功绩	517
帖子	11552
编号	1037
注册	2004-10-25
来自	天津
家族	司徒实业

#2

发表于 2007-6-28 01:54 资料主页短消息只看该作者

给每个犯人编号，1-100，然后让大家用二进位模式显示自己的号。例如，25 = 11001 = 开开关关开。等到每个号都进去过了，大家也就都知道了。

[广告] 安装Alexa工具条，提高轩辕排名，支持轩辕发展！


	asky (春意思)

组别	羽林都尉
级别	骠骑将军
功绩	94
帖子	8938
编号	16632
注册	2004-8-29

#3

发表于 2007-6-28 05:06 资料个人空间短消息只看该作者

好像只有在外面放风的囚犯可以看到灯啊，像公主提议的这样开开关关的不是消遣自己么......

[广告] 安装Alexa工具条，提高轩辕排名，支持轩辕发展！


	asky (春意思)

组别	羽林都尉
级别	骠骑将军
功绩	94
帖子	8938
编号	16632
注册	2004-8-29

#4

发表于 2007-6-28 05:18 资料个人空间短消息只看该作者

我有个方法，不过运气不好应该需要几百年时间吧，哈哈哈

假定初始灯是关的。

指定一名囚犯A，负责关灯：

如果他放风时，if 看见灯是亮的，then 关掉;并且计数加1；

其他人出来放风，if 以前没有开过灯&灯是关闭的 then 开灯 else 不做任何动作。

当A计数到99时，肯定所有人都放过风。

[ 本帖最后由 asky 于 2007-6-28 05:33 编辑 ]

本帖最近评分记录

青木风亮

2008-1-11 23:25

+500

积极参加讨论

[广告] 《精忠报国岳飞传完整版》火热发布


	sunnybill

组别	士兵
级别	偏将军
功绩	5
帖子	379
编号	91349
注册	2006-11-14

#5

发表于 2007-6-28 09:09 资料短消息只看该作者

那不如每人都负责关灯。
也就是每个人第一次见到灯的时候保持灯打开，以后每次都保持灯熄灭。
那么当某个人看到99－100次灯开着的时候，就全放过风了。（之所以有100是因为有可能他的第一次放风和第二次放风挨着，如果这种情况不出现就是99次）
不过我没算出来所需要时间的数学期望。最少应该是198天，最大就无穷大了。

[广告] 真诚支持说岳，携手共创辉煌


	asky (春意思)

组别	羽林都尉
级别	骠骑将军
功绩	94
帖子	8938
编号	16632
注册	2004-8-29

#6

发表于 2007-6-28 11:16 资料个人空间短消息只看该作者

你那个方法有漏洞，有可能这个人看到的某次开着的灯是被开了又关了又开过又关了.....又开了的，中间夹杂的次数不一定，这样就无法准确计数到99。

[广告] 真诚支持说岳，携手共创辉煌


	沈沉沦

组别	百姓
级别	破贼校尉
功绩	1
帖子	99
编号	45224
注册	2005-8-9

#7

发表于 2007-6-28 12:06 资料短消息只看该作者

QUOTE:

原帖由 天宫公主 于 2007-6-28 01:54 发表
给每个犯人编号，1-100，然后让大家用二进位模式显示自己的号。例如，25 = 11001 = 开开关关开。等到每个号都进去过了，大家也就都知道了。

注意:囚犯间不能联系
囚房内看不见灯!

别人怎么能知道操作灯的人是几号呢?

所以对此答案表示怀疑!

[广告] 安装Alexa工具条，提高轩辕排名，支持轩辕发展！


	edyswghe

组别	校尉
级别	奋威校尉
好贴	2
功绩	14
帖子	117
编号	57921
注册	2006-1-19

#8

发表于 2007-6-30 03:47 资料文集短消息只看该作者

asky的方法我觉得可行，但效率太低了。sunnybill的方法不对吧，从1号到100号这样放，没人能够看到100次亮灯啊，前100天每人看到1次，以后大家都看不到了

[广告] 《精忠报国岳飞传完整版》火热发布


	妖狐


	仁信伯武信军节度使

组别	节度使
级别	左将军
功绩	199
帖子	1229
编号	5143
注册	2004-2-9
来自	涿州
家族	轩辕狼党

#9

发表于 2007-6-30 09:21 资料主页个人空间短消息只看该作者

每天会有一个囚徒被随机地抽出来放风，随机就是说可能被抽到多次。

我觉得这句话有问题，是不是说有的人很可能一直没有机会被抽中

[广告] 真诚支持说岳，携手共创辉煌


	沈沉沦

组别	百姓
级别	破贼校尉
功绩	1
帖子	99
编号	45224
注册	2005-8-9

#10

发表于 2007-6-30 16:33 资料短消息只看该作者

再次重申:用计算机语言思考问题.这是关键!!!!!!!

我们所求的是最优解,当然是要考虑概率的,但是某些极端的情况可不用考虑的.
比如有的人出去了10次以上,而有的人1次也没出去过.
如果总是这样想,那么这题就没有意义了.

[广告] 《精忠报国岳飞传完整版》火热发布


	reynolds_wwy

组别	百姓
级别	奋威校尉
功绩	1
帖子	104
编号	10546
注册	2004-7-9

#11

发表于 2007-6-30 17:33 资料短消息只看该作者

四楼的答案难道不对？

[广告] 真诚支持说岳，携手共创辉煌


	沈沉沦

组别	百姓
级别	破贼校尉
功绩	1
帖子	99
编号	45224
注册	2005-8-9

#12

发表于 2007-7-1 17:20 资料短消息只看该作者

四楼自己也说了,运气不好的话要几百年时间啊!

这肯定不是最优解!

[广告] 真诚支持说岳，携手共创辉煌


	sunnybill

组别	士兵
级别	偏将军
功绩	5
帖子	379
编号	91349
注册	2006-11-14

#13

发表于 2007-7-1 17:34 资料短消息只看该作者

如果运气不好的话什么解都白搭。
想想真正运气不好了，最后一个人就是不叫了，怎么都在前99个中叫，你的解再好他们都是永远出不来。

[广告] 真诚支持说岳，携手共创辉煌


	沈沉沦

组别	百姓
级别	破贼校尉
功绩	1
帖子	99
编号	45224
注册	2005-8-9

#14

发表于 2007-7-2 20:38 资料短消息只看该作者

QUOTE:

原帖由 sunnybill 于 2007-7-1 17:34 发表
如果运气不好的话什么解都白搭。
想想真正运气不好了，最后一个人就是不叫了，怎么都在前99个中叫，你的解再好他们都是永远出不来。

再次重申,这是一个概率问题!
叫囚犯出去是随即的,不可能点名不让谁出去!

[广告] 安装Alexa工具条，提高轩辕排名，支持轩辕发展！


	爪子龙 (想当明星吗？加入本书屋你的 ...)


	★

组别	校尉
级别	安国将军
好贴	1
功绩	39
帖子	898
编号	57630
注册	2006-1-15
家族	肉肉门

#15

发表于 2007-7-3 00:53 资料文集短消息只看该作者

杀死所有没有摸过灯的囚徒

[广告] 《精忠报国岳飞传完整版》火热发布


	llloveee

组别	士兵
级别	忠义校尉
功绩	2
帖子	211
编号	15661
注册	2004-8-16
家族	轩辕狼党

#16

发表于 2007-7-3 22:37 资料短消息只看该作者

似乎4楼的答案是唯一的，期盼中......

[广告] 《精忠报国岳飞传完整版》火热发布


	沈沉沦

组别	百姓
级别	破贼校尉
功绩	1
帖子	99
编号	45224
注册	2005-8-9

#17

发表于 2007-7-4 10:29 资料短消息只看该作者

看来要公布答案了!

先将天数分段,每100天分一段,即每100天的囚犯负责记数.
假设最开始时灯是开的.
在第1个100天内,如果每个囚犯是第一次被叫出去,那么他不对灯进行操作,如果他是第2次被叫出去,那么他就操作灯,如果他是2次以上被叫出去,那么他也不操作灯.
则如果第100个囚犯发现灯是亮的,则表示每个囚犯都出去了.当然更大的可能性是他看到灯是灭的.
然后再以100天为1段区间,此时灯是灭的.
在第2个100天内,如果每个囚犯是第一次被叫出去,那么他不对灯进行操作,如果他是第2次被叫出去,那么他就操作灯,如果他是2次以上被叫出去,那么他也不操作灯.
则如果第100个囚犯发现灯是灭的,则表示每个囚犯都出去了.当然更大的可能性是他看到灯是亮的.
此后的过程是上述过程的循环.

解题思路:计算机语言中的循环和归零.

[广告] 《精忠报国岳飞传完整版》火热发布


	葉洛幻靈

组别	百姓
级别	在野武将
功绩	0
帖子	26
编号	91980
注册	2006-11-18

#18

发表于 2007-7-4 17:11 资料短消息只看该作者

没看懂~~你这么弄还是没得出答案来~~

[广告] 安装Alexa工具条，提高轩辕排名，支持轩辕发展！


	zuziwuming

组别	士兵
级别	忠义校尉
功绩	3
帖子	282
编号	57980
注册	2006-1-20
家族	轩辕丐帮

#19

发表于 2007-7-4 20:32 资料短消息只看该作者

QUOTE:

原帖由 沈沉沦 于 2007-7-4 10:29 发表
在第1个100天内,如果每个囚犯是第一次被叫出去,那么他不对灯进行操作,如果他是第2次被叫出去,那么他就操作灯,如果他是2次以上被叫出去,那么他也不操作灯.
则如果第100个囚犯发现灯是亮的,则表示每个囚犯都出去了

不对啊，假设前99天有2个人被叫2次，另外95人叫一次，那么灯是不是亮的？

[广告] 《精忠报国岳飞传完整版》火热发布


	llloveee

组别	士兵
级别	忠义校尉
功绩	2
帖子	211
编号	15661
注册	2004-8-16
家族	轩辕狼党

#20

发表于 2007-7-4 21:03 资料短消息只看该作者

QUOTE:

原帖由 沈沉沦 于 2007-7-4 10:29 发表
看来要公布答案了!

先将天数分段,每100天分一段,即每100天的囚犯负责记数.
假设最开始时灯是开的.
在第1个100天内,如果每个囚犯是第一次被叫出去,那么他不对灯进行操作,如果他是第2次被叫出去,那么他就操作 ...

晕倒，那来的小毛孩糊弄咱大爷？

[广告] 安装Alexa工具条，提高轩辕排名，支持轩辕发展！


	llloveee

组别	士兵
级别	忠义校尉
功绩	2
帖子	211
编号	15661
注册	2004-8-16
家族	轩辕狼党

#21

发表于 2007-7-4 21:07 资料短消息只看该作者

我觉得4楼已经是天才。至少是个具备了计算机思维的人。期待更伟大的天才出现。

[广告] 真诚支持说岳，携手共创辉煌


	edyswghe

组别	校尉
级别	奋威校尉
好贴	2
功绩	14
帖子	117
编号	57921
注册	2006-1-19

#22

发表于 2007-7-5 01:18 资料文集短消息只看该作者

楼主的答案明显错了啊，前100天内如果只出去过2个人，一个奇数天出，一个偶数天出，灯也是亮的，可是只有两个囚犯出去过

[广告] 安装Alexa工具条，提高轩辕排名，支持轩辕发展！


	沈沉沦

组别	百姓
级别	破贼校尉
功绩	1
帖子	99
编号	45224
注册	2005-8-9

#23

发表于 2007-7-24 12:10 资料短消息只看该作者

我晕，出差了一端时间，就被误解成这样啊！
可能是我前面的表述有问题，现在从新解释一下：
前面大家争论的关键是偶数个人被重复叫出去放风并且对灯进行操作就会导致错误，那么我们可以锁定一下，在每100天中第一个被重复叫出的人（既第一个被叫出2次的人）才进行操作，其余的人都不对灯操作（包括被叫出去2+次的人和第N个被叫出去2次的人）。
接下来就是要判断每100天中谁是第一个被叫出去2次的人了：
假设第N个100天开始灯是灭的（囚犯可以通过计算判断第N个100天开始灯的状态），第M个人被叫出去，如果他看见灯是亮的，显然他可以知道在他之前有1个人被叫出去2次了，那他旧可以不对灯进行操作，如果他看见等是灭的，那么他就知道自己是第一个被叫出2次的人，他就可以对灯进行操作。
此解法的弊端在于：第N个100天结束时的囚犯运气是否够好，能看到他期望看到的灯的状态。这就需要他拼人品了。。。。

[广告] 《精忠报国岳飞传完整版》火热发布


	01091022

组别	百姓
级别	破贼校尉
功绩	1
帖子	56
编号	121803
注册	2007-3-16

#24

发表于 2007-7-24 12:34 资料短消息只看该作者

囚犯之间又不能联系，谁告诉他们这么统一的操作和不操作呢？

[广告] 安装Alexa工具条，提高轩辕排名，支持轩辕发展！


	zuziwuming

组别	士兵
级别	忠义校尉
功绩	3
帖子	282
编号	57980
注册	2006-1-20
家族	轩辕丐帮

#25

发表于 2007-7-24 17:33 资料短消息只看该作者

回复 #26 沈沉沦的帖子

按楼主的解法,哪个囚犯去报告每个人都出去过?他要看到怎样的灯的状态?

希望楼主回答

[广告] 《精忠报国岳飞传完整版》火热发布


	墨叶


	★★★★ 节度留后虎豹骑

组别	虎豹骑
级别	大将军
功绩	359
帖子	23258
编号	97330
注册	2006-12-26
家族	轩辕少林寺

#26

发表于 2007-7-24 18:38 资料个人空间短消息只看该作者

我认为楼主可以把人数减少(比如10个)然后做个程序验证比较好

[广告] 《精忠报国岳飞传完整版》火热发布


	llloveee

组别	士兵
级别	忠义校尉
功绩	2
帖子	211
编号	15661
注册	2004-8-16
家族	轩辕狼党

#27

发表于 2007-7-25 22:12 资料短消息只看该作者

QUOTE:

原帖由 沈沉沦 于 2007-7-24 12:10 发表
我晕，出差了一端时间，就被误解成这样啊！
可能是我前面的表述有问题，现在从新解释一下：
前面大家争论的关键是偶数个人被重复叫出去放风并且对灯进行操作就会导致错误，那么我们可以锁定一下，在每100天中 ...

看到楼主的这个贴，我再次晕倒，我原来以为楼主是读历史或者文学相关专业的，但我现在感觉到我错了，楼主一定一定是政治专业毕业的，对吧？

请让我将楼主的解法简单讲一下：只要从第一百个人开始，连续一百个人不重复地被放出，那么灯就没有被操作，最后一人可以判断所有人都已被放出过一次以上。

建议楼主再看看4楼的解法，如果看不懂的话请和你的老公或者BF讨论讨论。

[广告] 真诚支持说岳，携手共创辉煌


	asky (春意思)

组别	羽林都尉
级别	骠骑将军
功绩	94
帖子	8938
编号	16632
注册	2004-8-29

#28

发表于 2007-7-25 23:58 资料个人空间短消息只看该作者

也，这个帖子还在讨论

我那个方法数学期望是10000，10000/365约等于27.4，大概按照正常概率有生之年可以出结果。

楼主你那个方法糟糕就糟糕在归零上面，期望大概是100的100次方，大概在一个零头的时候，太阳系已经毁灭

[广告] 真诚支持说岳，携手共创辉煌


	an老忘密码

组别	士兵
级别	讨逆将军
功绩	6
帖子	634
编号	101522
注册	2007-1-16

#29

发表于 2007-7-26 09:58 资料短消息只看该作者

然后再以100天为1段区间,此时灯是灭的.
在第2个100天内,如果每个囚犯是第一次被叫出去,那么他不对灯进行操作,如果他是第2次被叫出去,那么他就操作灯,如果他是2次以上被叫出去,那么他也不操作灯.
则如果第100个囚犯发现灯是灭的,则表示每个囚犯都出去了.当然更大的可能性是他看到灯是亮的.

若第2个100天内，只有俩个人被叫出去（以前的出场次数少于2），那这俩人就都会操做一次。即由原先的灯灭会被开关各一次，最后灯是灭的。不知我写的能否证明楼主的算法有问题。

[广告] 真诚支持说岳，携手共创辉煌


	沈沉沦

组别	百姓
级别	破贼校尉
功绩	1
帖子	99
编号	45224
注册	2005-8-9

#30

发表于 2007-7-26 17:46 资料短消息只看该作者

QUOTE:

原帖由 asky 于 2007-7-25 23:58 发表
也，这个帖子还在讨论

我那个方法数学期望是10000，10000/365约等于27.4，大概按照正常概率有生之年可以出结果。

楼主你那个方法糟糕就糟糕在归零上面，期望大概是100的100次方，大概在一个零头的 ...

我们可以做一个最简单的假设：每个单位循环时间内（100天）就是没有人被重复叫出。
那么4楼的方法判断囚犯全部被叫出需要10000天，而我的方法判断囚犯全部被叫出只需要200天。孰优孰劣，一目了然。

楼上是怎么算出我的方法的数学期望的？100的100次方？很不解

很明显囚犯全部被叫出大概只需要2到3年，我们需要的只是最快的判断方法而已。

[广告] 安装Alexa工具条，提高轩辕排名，支持轩辕发展！