100囚徒问题答案
其实把答案说出来的话，可能会招来很多人的不懈，很多人会说这个题目太无聊了。但毕竟题目不是我出的，我只是解答这个题目罢了。
基本算法就是：
- 从100个人中选出一个人，这个人只能关灯。并且记住自己关灯的次数。
- 当上面这个人关了98次，并且再次出来放风的时候发现灯是亮着的，就可以宣称所有人都出来过了。（不用我解释吧。。。）
- 其他99人出来放风只能开灯，并且只能开一次灯，也就是说，如果以前已经开过灯了，就算他再次出来的时候灯是关着的也不能开。
我最初觉得如果这样解决这个问题，可能要用n多天，因为每天是随机选一个人。但是刚才写了一个程序来验证，发现还是可行的。平均不到30年就可以出来了。。。寒-_-!。。。似乎还是太多？（至少比我想的要短多了，呵呵，能出来就好。）
使用Java写的程序模拟，源程序可以在这里下载：
发表评论
| Trackback
