囚徒问题
囚徒问题
有100个无期徒刑囚徒，被关在100个独立的小房间，互相无法通信。
每天会有一个囚徒被随机地抽出来放风，随机就是说可能被抽到多次。
放风的地方有一盏灯，囚徒可以打开或者关上，除囚徒外，没有别人会去动这个灯。每个人除非出来防风，是看不到这个灯的。
一天，全体囚徒大会，国王大赦，给大家一个机会：如果某一天，某个囚徒能够明确表示，所有的囚徒都已经被放过风了，而且的确如此，那么所有囚徒释放；如果仍有囚徒未被放过风，那么所有的囚徒一起处死！
囚徒大会后给大家20分钟时间讨论，囚徒们能找到方法么？
这个问题是著名的谜题之一，如果大家认为自己找到了方法，再仔细想想，有没有效率更高的？
每天会有一个囚徒被随机地抽出来放风，随机就是说可能被抽到多次。
放风的地方有一盏灯，囚徒可以打开或者关上，除囚徒外，没有别人会去动这个灯。每个人除非出来防风，是看不到这个灯的。
一天，全体囚徒大会，国王大赦，给大家一个机会：如果某一天，某个囚徒能够明确表示，所有的囚徒都已经被放过风了，而且的确如此，那么所有囚徒释放；如果仍有囚徒未被放过风，那么所有的囚徒一起处死！
囚徒大会后给大家20分钟时间讨论，囚徒们能找到方法么？
这个问题是著名的谜题之一，如果大家认为自己找到了方法，再仔细想想，有没有效率更高的？
回答列表
先给每个囚徒一个编号，1-100，并将天数也以100计数。刚开始假设灯是灭的。
第i个囚犯做的事情是：
如果他正好是第i天被拉去放风，则他点亮灯。
若是j天（i,j不好同），再看灯是什么状态，如果灯暗的，则什么都不做。如果灯是亮的，则把灯熄灭，并可以得到信息，第j-1号的囚犯已经放过风，因此，以后第i个囚犯可以在第i,j-1这两天被拉去放风的时候把灯点亮。
依此类推，当有囚犯可以再任何天都能点亮灯的时候就说明所有囚犯已经放过风了。
第i个囚犯做的事情是：
如果他正好是第i天被拉去放风，则他点亮灯。
若是j天（i,j不好同），再看灯是什么状态，如果灯暗的，则什么都不做。如果灯是亮的，则把灯熄灭，并可以得到信息，第j-1号的囚犯已经放过风，因此，以后第i个囚犯可以在第i,j-1这两天被拉去放风的时候把灯点亮。
依此类推，当有囚犯可以再任何天都能点亮灯的时候就说明所有囚犯已经放过风了。
三思网友QQ群：3535265