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


	沈沉沦

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

#1

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

囚犯点灯

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

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


	沈沉沦

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

#2

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

QUOTE:

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

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

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

所以对此答案表示怀疑!

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


	沈沉沦

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

#3

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

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

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

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


	沈沉沦

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

#4

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

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

这肯定不是最优解!

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


	沈沉沦

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

#5

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

QUOTE:

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

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

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


	沈沉沦

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

#6

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

看来要公布答案了!

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

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

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


	沈沉沦

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

#7

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

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

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


	沈沉沦

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

#8

发表于 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工具条，提高轩辕排名，支持轩辕发展！


	沈沉沦

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

#9

发表于 2007-7-26 22:07 资料短消息看全部作者

本人思路：其实这个题目能做文章的只有灯，天数和人数。天数和人数这个在每个囚犯心里都是有数，而灯只有两种状态，最主要的是把这三个结合起来碰出一个绝对情况。
误区：所谓的什么1个人被反复的叫上n次，或者始终有一个人没被叫出来，或者每次大家机会平等的被叫出来的的时候总是有人被叫两次。
asky思路：拿一个人做记数器。记上自己关灯的次数。来推算大家有没有都被放出来，显然只利用了灯的状态而没有用到过了多少天和人数的关系。但确实这个方法可以让大家出来。而且我认为很高明。
我的思路：就是每一百天做为一个单位。如果在一百天里有任何一个人被重复，或者n个人被重复，就放弃这一百天。拿下一个一百天来计算。
我的思路和asky的思路比较：
假设1：运气非常好，每个人都只被叫出来1次。而且大家都知道第一天的灯的状态（进去前大家可以商量灯的原始状态）那么100天时候只要灯的状态和第1天一样，大家都可以出来了。（说了运气好大家就不要在什么什么的了，），只要100天大家都可以出来了。而这个时候似乎，asky记数只记了0吧。
假设2：如果运气不好，第一个100天里面有人被叫出来两次或者两次以上或者n个人被叫出来n次（反正是乱七八糟的情况出现）那大家都放弃这100天，怎么放弃呢？就是第一个被叫出来两次的人对灯的初始状态做一下改变。其余的同志你们大概都知道第一天灯的状态是什么把，如果你们在这100天里看到灯与第一天的状态不同，请你们不要手痒-----放弃对灯操作（第一个被叫出来两次的人你已经对灯操作了，就请你如果在这100天里被第三次叫出来的时候不要手痒了，让灯保持你看到的状态）。让所有的人都知道在101天的时候灯的状态（如果有人怀疑大家都不知道1，101，201，301，xx01；xx趋于无穷大时候灯的状态，请你想想或者仔细看看我的方法）这个时候同志们都没有出来。在101-200里asky状态有3种：1.巧合：1）你又被叫了99次，2）还要是隔天被叫，3）其余同志也是隔天被叫，且只被叫了一次。而asky要天时，地利，人和呀！ 2.3个巧合有任何一个不成立。 3.就是大家运气好又只被叫了一次，那么200我的人都可以出来了，但asky你才记了1。
在前两百天里，100天的时候拼人品，我出来了。asky只能有50个人（包括他自己）人品超级好（而且他的人品是其余49个人的总和），这样他可以记49次。
200天（前一天人我这边有人人品稍微好了点被叫出来2次以上）大家改邪归正，人品平均，那么200我出来了。asky人品超级好是其余99个人的总和，而其余人品都平均，且隔天爆发超过了asky。那么asky也出来了。
假设3：201-300.这个时候asky状态：1.人品好被叫出来99次（300天的任何1天），其余人不用隔天出来，但要看asky是那天出来99次的，如果是201那么asky有一次可以是隔两天出来。202可以是隔三天或者有两次隔2天出来。依次类推。那么asky你出来了，我还没有头，两百天我的人总有发扬雷风精神，被天谴责了。大家人品拉到同一个起跑线，300天我才出来。
假设4：301-400天，大家可以推算了。
比较：前200天，我优先。如果有人没看懂，那算了。如果有人就觉得asky人品超级好，那也算了。
201-300天，asky可以比我先出来，我输。但是这个取决于asky的人品了。
301-400天，asky可以比我先出来，我输。但是这个也取决于asky的人品了。
以后asky都可以比我先出来，我输。无穷的时候asky人品递减。
总的来说我的思路是希望大家都很平等，虽然有的时候有人出风头，但是总有那么xx01-x(x+1)00天里大家人品平等。当然你可以用数学期望值，也可以用极端法来反驳，就是总是在100天这个单位里，有人出风头。那么我承认我人品差。我不该相信人人平等或者趋向平等这个说法。当然其实如果有人能想到不用100作为单位而用更合理的一个单位，最好是无论什么时候只要100个人都出来那么就让这个人宣布大家都出来了。
asky的思路是有一个人人品超级好，那么他可以在大于200天后的某一天就能出来了。如果大家平均的人品的话，他只能到10000以后了。
总结：1.100个人人品平均那么我10000里可以出来100次;.asky人品超级好，10000可以出来50次;2.10000里，只要让我逮到一次100天为单位里面大家人品平均我就能出来了;.10000里随着asky人品的递减出来的次数减少。3.超过10000天asky你牛，你随时都能出来，而我机会永远是比你小。
27年呀，1个人呆着说话能力都没了。能不能数到99呀。
还有我的那个方法，再解释一下：100里reynolds_wwy 你被第2次叫出来，你就对灯操作一下。墨叶你虽然也是第2次被叫出来，就委屈你不要对灯操作，其余的人也是。reynolds_wwy 你第3次被叫出来，也不要对灯再操作了。即使你被叫了99次你也不要再对灯操作了。这样100天的时候只要看到等和第1天状态1样，就能宣布了。因为100里灯只能由亮变暗或者由暗变亮。不会出现亮变暗再变亮。要是还在对我的方法怀疑，我要发飚了。
但和asky的方法比较的话，同志们拼运气比人品及题目的合理性综合考虑一下。

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


	沈沉沦

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

#10

发表于 2007-7-26 22:31 资料短消息看全部作者

PS：
对ASKY思路：我所谓的你是把你当作了记数的人。
对我自己的思路：我所谓的我是把我当做第N个100天出来的人。

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


	沈沉沦

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

#11

发表于 2007-7-27 00:08 资料短消息看全部作者

reynolds_wwy 万一100个人都只被叫出来一次，难道你还不让大家出来吗？
天数趋于无穷，记数的那个人当然才叫出来99次的可能性大了很多，而他关灯的概率也随着天数的增加而增加。我那个方法确实就是你理解的100天为一个单位。
我的方法随着天数的增加概率变的越来越少。因为放样的话，我的方法就一个情况100，每个人只出来一次。10000以后我的分子概率仍然不变，而分母增大。所以我的出来的概率会越来越小。
大姐你非要按无穷来想，那么大家都不要出来算了！我就死都不让一个人出来。其实让一个人20年在没有任何交流的情况下生活我令愿死了算了。如果我是囚犯我令愿相信大家运气都好，就100天或者200左右就被放出去。而不愿意到200天后才可能只被记数1。
什么东西都按公式，或者理论什么的而脱离了实际情况，我想是不是太极端了？

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


	沈沉沦

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

#12

发表于 2007-7-27 09:12 资料短消息看全部作者

QUOTE:

原帖由 reynolds_wwy 于 2007-7-27 08:35 发表
orz........楼主原来是在胡闹啊，艾看来我掺和错了
哦对了刚刚的计算实在每天叫到任何一个人机会均等的情况下算的
其实作为囚犯你制定策略时也只能做一些合理的假设，毕竟你根本不知道那个选人的究竟会用何种 ...

现在有2点需要说明：
1）有人表示我的方法不能判断囚犯被全部叫出，这个我已经解释过了，若有意见请多看看我的解法。

2）有人认为我的方法能判断囚犯被全部叫出，只是时间很长，大概10^44天，不如4楼的方法好，只要大概10000天。
reynolds_wwy你计算过的，大概100个人第一次全部被叫出大概只需要518天（见《囚犯点灯引出的问题》），也就是说大概2年时间囚犯可以被认为全部被叫出过，只是我们没有办法在2年时间内去很明确地判断出他们已经全部被叫出。
那么我们就说说我们的判断方法：
4楼的思路是记数
我的方思路是计算第N个100天的人能看见第N个100天的灯能够证明囚犯全部被叫出的状态（亮OR灭），用我的方法需要计算的数学期望应该是这个才对，所以十分怀疑reynolds_wwy计算结果的正确性。
若还有意见，请继续拍砖吧！

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


	沈沉沦

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

#13

发表于 2007-7-27 09:27 资料短消息看全部作者

QUOTE:

原帖由 asky 于 2007-7-27 01:49 发表
概率计算并不是指公式的问题，概率是这个世界上发生事件的一般规律的考虑。

reynolds_wwy的概率计算是基于事件分布统计的。

你的方法因为清零，使得数据的累积停留在100天以内，问题是100天内每个人被叫出 ...

我所谓的每个100天归零是说判断方法的改变，而不是将该100天进出的人数也忽略掉！
毕竟在2年到3年的时间内，囚犯应该都能被叫出，我完全没有必要认定所有人都在第N个100天全部被叫出。

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


	沈沉沦

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

#14

发表于 2007-7-27 10:10 资料短消息看全部作者

QUOTE:

原帖由 an老忘密码 于 2007-7-27 09:45 发表
楼主的语言，即然有那么多人有异意，那起嘛你在表述上的逻辑是有些不清晰的。至于算法上的逻辑，只要你写出来，我不会看，也会输入运行。不当机就行。

我也感觉到表述有问题！居然没有人看的懂！

看来要好好组织语言了。

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


	沈沉沦

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

#15

发表于 2007-8-1 14:00 资料短消息看全部作者

想清楚了，我的解法的确有问题！对不起了大家！
不过希望大家能继续思考，个人认为还有更优解！

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