一个囚徒问题

shshsh_0510

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

我加一问：如果能找到方法，那么按你的方法，囚徒到被释放平均还需要做多长时间的牢？

gogdizzy

我觉得是没办法的，只有一个灯，两个状态。

gxqcn

是可以的。 取其中一个状态作为囚徒是否放风的标志，然后统计总数是否足够即可。 这样需要事先设定一个专员对标志状态复位并统计。

gxqcn

具体为： 推选一个固定的囚犯，其任务是复位并计数。 其他人放风时，当灯是关闭状态且自己从未开灯时，就把灯点亮；否则不要碰灯； 而那个指定的囚犯，则是负责给大家关灯的，每关一次就累加一下， 如果灯初始状态是关的，当达到99次时，则表明全部囚犯均放过风。

gxqcn

考虑到节能，以及灯的寿命， 最好是将状态颠倒一下：点灯仅由指定的人去完成；而由其他人则是去关灯。 此时要求灯初始状态是关闭的。计数满100则表明全部都放过风。

gxqcn

一个新的问题： 假定每次放风有且仅一人（随机的），放风时长固定，中间无间断（或固定间隔时长）， 那么：用 4# 或 5# 的方案，哪个更节能？节能多少？（假设灯是长命灯，且功率固定）

风云剑

以前用计算机模拟过，最终是需要相当长的时间才能出来。

2. /*
3. 有100个无期徒刑囚徒，被关在100个独立的小房间，互相无法通信。
4. 每天会有一个囚徒被随机地抽出来放风，随机就是说可能被抽到多次。
5. 放风的地方有一盏灯，囚徒可以打开或者关上，除囚徒外，没有别人会去动这个灯。每
6. 个人除非出来防风，是看不到这个灯的。
8. 一天，全体囚徒大会，国王大赦，给大家一个机会：如果某一天，某个囚徒能够明确表
9. 示，所有的囚徒都已经被放过风了，而且的确如此，那么所有囚徒释放；如果仍有囚徒
10. 未被放过风，那么所有的囚徒一起处死！
12. 囚徒大会后给大家20分钟时间讨论，帮囚徒们能找到方法。
14. 答案：？
15. 囚徒们这样商定好：凡是第一次出来放风的囚徒就把灯点燃，凡不止是第一次出来放风的囚徒出来放风，就把点燃的灯熄灭。
16. 这样一来，当某一个囚徒第二次出来放风时，如果他发现灯是亮着的，
17. 那么他就可以确定：前一天出来的那个囚徒一定是到目前为止第一次出来放风的。
18. 这样下去，当这个囚徒第N次出来放风时，如果他第九十九次
19. （注意：N≥99，表示他可能在某些次出来发现灯关掉了。）发现灯是亮着的，那么他就可以宣布：所有的囚徒均已经放过风。
21. 答案：？
22. 假设希望寄托在第一个人身上，他出去后看到灯是关着的，不管它
23. 第二个出去的人把灯打开，后面出去的人看到灯是开的不要管
24. 等第一个人有机会被抽到第二次出去，将灯关掉
25. 此时下一个出去的人看到灯是关的，他如果没有开过灯，打开；开过，不要管
26. ………………
27. ………………
28. 以此类推，也就是遵循以下原则：
29. 1 只有第一个出去的人有权力关灯
30. 2 每个人只有一次开灯机会
32. 这样等第一个人第99次关灯时，就可以证明全部都放过风了
34. */
35. #include <stdio.h>
36. #include <stdlib.h>
37. #include <string.h>
38. #include <time.h>
40. #define _PRINT_ 0
42. const long MAX_JAILBIRD=100;
44. typedef struct
45. {
46. long count; //放风次数
47. long on; //发现灯为开的次数(对于第二方案是开灯次数)
48. long off; //发现灯为关的次数(对于第二方案是关灯次数)
49. bool first; //是否是第一个被叫出去防风
50. } JAILBIRD; //囚徒类
51. bool light; //灯的开关状态，1－开，0－关
52. long days; //经过的天数
53. JAILBIRD jb[MAX_JAILBIRD]; //100个囚徒
54. bool ok; //所有的囚徒都已经被放过风了
56. /*
57. 初始化函数
58. */
59. void init(void)
60. {
61. light=0;
62. days=0;
63. ok=false;
64. randomize();
65. for(long i=0; i < MAX_JAILBIRD; i++)
66. {
67. jb[i].count=0;
68. jb[i].on=0;
69. jb[i].off=0;
70. jb[i].first=false;
71. }
72. }
74. /*
75. 放风函数
76. */
77. void ff1(void)
78. {
79. long v;
80. v=rand() % MAX_JAILBIRD; //随机抽一个囚徒
81. days++;
82. #if (_PRINT_)
83. printf("第%ld天开始，囚徒%d已经放风%ld次，灯为开%ld次，灯为关%ld次，灯%d。\n",
84. days,
85. v,
86. jb[v].count,
87. jb[v].on,
88. jb[v].off,
89. light);
90. #endif
91. jb[v].count++;
92. if(light) //如果灯是开的，计数
93. {
94. jb[v].on++;
95. }
96. else
97. {
98. jb[v].off++;
99. }
101. if(jb[v].on == 99) //第99次发现灯为开，结束
102. {
103. ok=true;
104. }
106. if(jb[v].count == 1) //如果是第一次出来放风
107. {
108. if(!light) //将关的灯打开
109. {
110. light=true;
111. }
112. }
113. else //如果不是第一次出来放风
114. {
115. if(light) //将开的灯关上
116. {
117. light=false;
118. }
119. }
121. #if (_PRINT_)
122. printf("第%ld天结束，囚徒%d已经放风%ld次，灯为开%ld次，灯为关%ld次，灯%d\n",
123. days,
124. v,
125. jb[v].count,
126. jb[v].on,
127. jb[v].off,
128. light);
129. #endif
130. }
132. /*
133. 放风函数
134. */
135. void ff2(void)
136. {
137. long v;
138. v=rand() % MAX_JAILBIRD; //随机抽一个囚徒
139. days++;
140. #if (_PRINT_)
141. printf("第%ld天开始，囚徒%d已经放风%ld次，开灯%ld次，关灯%ld次，灯%d。\n",
142. days,
143. v,
144. jb[v].count,
145. jb[v].on,
146. jb[v].off,
147. light);
148. #endif
149. if(days == 1)
150. {
151. jb[v].first=true; //记下第一个出来放风的囚徒
152. #if (_PRINT_)
153. printf("第一个出来放风的囚徒是%d号\n", v);
154. #endif
155. }
157. jb[v].count++;
158. if(jb[v].first) //如果是第一个出来放风的囚徒
159. {
160. if(light) //如果灯是开的
161. {
162. light=false; //关灯
163. jb[v].off++; //关灯次数计数
164. #if (_PRINT_)
165. printf("第一个出来放风的囚徒第%ld次关灯\n", jb[v].off);
166. #endif
167. }
168. }
169. else //如果不是第一个出来放风的囚徒
170. {
171. if(!light) //如果灯是关的
172. {
173. if(jb[v].on == 0) //如果他没有开过灯
174. {
175. light=true; //开灯
176. jb[v].on++; //开灯次数计数
177. }
178. }
179. }
181. if(jb[v].first && jb[v].off == 99) //第一个放风的囚徒第99次关灯，结束
182. {
183. ok=true;
184. }
186. #if (_PRINT_)
187. printf("第%ld天结束，囚徒%d已经放风%ld次，开灯%ld次，关灯%ld次，灯%d\n",
188. days,
189. v,
190. jb[v].count,
191. jb[v].on,
192. jb[v].off,
193. light);
194. #endif
195. }
197. /* */
198. int main(void)
199. {
200. init();
201. while(!ok)
202. {
203. ff2();
204. }
206. printf("\n共%ld天，以下是每个囚徒出来放风的次数\n", days);
207. for(long i=0; i < MAX_JAILBIRD; i++)
208. {
209. printf("%ld\t", jb[i].count);
210. }
212. printf("\n");
214. return 0;
215. }

复制代码

gxqcn

7# 风云剑 这两种方案平均起来哪个更优？

shshsh_0510

昨天想了想，这个问题还是比较有意思的，又查了查，下面是网上查的几种方法 [zt] 第一天出來的這個囚徒負責關燈，以後出來的囚徒： 1）當燈是關著的時候，如果他沒有開過燈，那他可以打開燈，否則他不能開燈； 2）當燈是開著的時候，他不動燈。 3）第一個囚徒在他放風的時候，如果發現燈是開的，那麼他就關閉燈。這時他就把放過風的囚徒數加一。 當第一個囚徒的計數達到99的時候(加上他自己是100)，他就可以宣佈所有的囚徒都放過風啦,按平均計算100×99＝9900天，就是27年呀！ [zt] 第二個方法分兩個階段： 階段一：前100天決定誰來計數。 1）第1-99天，初始燈關著，第一個兩次放過風的人將成為計數者，並將燈關上。設其為第K天第2次放風，則他知道已經有k-1個人放過風，做為100天後計數的初始值。 2）第100天放風的人如果看見等關著，則宣佈所有人都放過風；否則把燈關上 階段二：100天後 1）如果計數者放風看見燈開著，則將放過風的人數加1，到100時宣佈勝利 2）其他人如果以前沒放過風，並且燈關著，則開燈，否則不動 此方法期望年數為24.42年 [zt] 第三種方法提示如下:分為一個基本記數者和N個2級記數者,基本記數者的獨立記數上限Cp和2級記數的獨立計數上限Cs,時間由長度為S1和S2的兩段交替組成.在S1階段,計數者計數直到達到其獨立計數上限,在S2階段,達到計數上限的2級計數者將通過開燈方法告訴基本計數者直到基本計數者得到所有2級計數者完成任務並加上自己計數為100時宣佈自由. 此方法通過計算機模擬優化可在10年左右完成.

shshsh_0510

上面几种方法都比较巧妙 第一种和4#一样，我们分析一下： 设系统还有x个没开过灯的囚徒，没开过灯的某个囚徒被防风的概率是 x/100 ,所以期望时间是 100/x,然后等统计者出来关灯计数，此期望时间是100，于是总的期望为 $\sum_(i=1)^99{100+100/i} =10418天=28.5年$