论坛 › 趣题妙解 › 一个囚徒问题

shshsh_0510 发表于 2009-6-18 13:57:32

一个囚徒问题

有趣而有考脑筋的问题有100个无期囚徒，被关在100个独立的小房间，互相无法通信。

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

放风的地方有一盏灯，囚徒可以打开或者关上，除囚徒外，没有别人会去动这个灯。每个人除非出来防风，是看不到这个灯的。

一天，全体囚徒大会，国王大赦，给大家一个机会：如果某一天，某个囚徒能够明确表示，所有的囚徒都已经被放过风了，而且的确如此，那么所有囚徒释放；如果仍有囚徒未被放过风，那么所有的囚徒一起处死！

囚徒大会后给大家20分钟时间讨论，囚徒们能找到方法么？
我加一问：如果能找到方法，那么按你的方法，囚徒到被释放平均还需要做多长时间的牢？

gogdizzy 发表于 2009-6-18 15:02:56

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

gxqcn 发表于 2009-6-18 20:18:18

是可以的。

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

gxqcn 发表于 2009-6-18 20:41:27

具体为：

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

gxqcn 发表于 2009-6-18 20:46:36

考虑到节能，以及灯的寿命，
最好是将状态颠倒一下：点灯仅由指定的人去完成；而由其他人则是去关灯。

此时要求灯初始状态是关闭的。计数满100则表明全部都放过风。

gxqcn 发表于 2009-6-18 20:51:29

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

风云剑 发表于 2009-6-18 21:21:01

以前用计算机模拟过，最终是需要相当长的时间才能出来。
/*
有100个无期徒刑囚徒，被关在100个独立的小房间，互相无法通信。
每天会有一个囚徒被随机地抽出来放风，随机就是说可能被抽到多次。
放风的地方有一盏灯，囚徒可以打开或者关上，除囚徒外，没有别人会去动这个灯。每
个人除非出来防风，是看不到这个灯的。

一天，全体囚徒大会，国王大赦，给大家一个机会：如果某一天，某个囚徒能够明确表
示，所有的囚徒都已经被放过风了，而且的确如此，那么所有囚徒释放；如果仍有囚徒
未被放过风，那么所有的囚徒一起处死！

囚徒大会后给大家20分钟时间讨论，帮囚徒们能找到方法。

答案：？
囚徒们这样商定好：凡是第一次出来放风的囚徒就把灯点燃，凡不止是第一次出来放风的囚徒出来放风，就把点燃的灯熄灭。
这样一来，当某一个囚徒第二次出来放风时，如果他发现灯是亮着的，
那么他就可以确定：前一天出来的那个囚徒一定是到目前为止第一次出来放风的。
这样下去，当这个囚徒第N次出来放风时，如果他第九十九次
（注意：N≥99，表示他可能在某些次出来发现灯关掉了。）发现灯是亮着的，那么他就可以宣布：所有的囚徒均已经放过风。

答案：？
假设希望寄托在第一个人身上，他出去后看到灯是关着的，不管它
   第二个出去的人把灯打开，后面出去的人看到灯是开的不要管
   等第一个人有机会被抽到第二次出去，将灯关掉
   此时下一个出去的人看到灯是关的，他如果没有开过灯，打开；开过，不要管
   ………………
   ………………
   以此类推，也就是遵循以下原则：
   1 只有第一个出去的人有权力关灯
   2 每个人只有一次开灯机会

这样等第一个人第99次关灯时，就可以证明全部都放过风了

*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

#define _PRINT_ 0

const longMAX_JAILBIRD=100;

typedef struct
{
    long    count;            //放风次数
    long    on;               //发现灯为开的次数(对于第二方案是开灯次数)
    long    off;                //发现灯为关的次数(对于第二方案是关灯次数)
    bool    first;            //是否是第一个被叫出去防风
} JAILBIRD;                     //囚徒类
bool      light;            //灯的开关状态，1－开，0－关
long      days;               //经过的天数
JAILBIRD    jb;   //100个囚徒
bool      ok;               //所有的囚徒都已经被放过风了

/*
初始化函数
*/
void init(void)
{
    light=0;
    days=0;
    ok=false;
    randomize();
    for(long i=0; i < MAX_JAILBIRD; i++)
    {
      jb.count=0;
      jb.on=0;
      jb.off=0;
      jb.first=false;
    }
}

/*
放风函数
*/
void ff1(void)
{
    long    v;
    v=rand() % MAX_JAILBIRD;    //随机抽一个囚徒
    days++;
#if (_PRINT_)
    printf("第%ld天开始，囚徒%d已经放风%ld次，灯为开%ld次，灯为关%ld次，灯%d。\n",
               days,
               v,
               jb.count,
               jb.on,
               jb.off,
               light);
#endif
    jb.count++;
    if(light)                   //如果灯是开的，计数
    {
      jb.on++;
    }
    else
    {
      jb.off++;
    }

    if(jb.on == 99)          //第99次发现灯为开，结束
    {
      ok=true;
    }

    if(jb.count == 1)      //如果是第一次出来放风
    {
      if(!light)            //将关的灯打开
      {
            light=true;
      }
    }
    else                        //如果不是第一次出来放风
    {
      if(light)               //将开的灯关上
      {
            light=false;
      }
    }

#if (_PRINT_)
    printf("第%ld天结束，囚徒%d已经放风%ld次，灯为开%ld次，灯为关%ld次，灯%d\n",
               days,
               v,
               jb.count,
               jb.on,
               jb.off,
               light);
#endif
}

/*
放风函数
*/
void ff2(void)
{
    long    v;
    v=rand() % MAX_JAILBIRD;            //随机抽一个囚徒
    days++;
#if (_PRINT_)
    printf("第%ld天开始，囚徒%d已经放风%ld次，开灯%ld次，关灯%ld次，灯%d。\n",
               days,
               v,
               jb.count,
               jb.on,
               jb.off,
               light);
#endif
    if(days == 1)
    {
      jb.first=true;               //记下第一个出来放风的囚徒
#if (_PRINT_)
      printf("第一个出来放风的囚徒是%d号\n", v);
#endif
    }

    jb.count++;
    if(jb.first)                     //如果是第一个出来放风的囚徒
    {
      if(light)                     //如果灯是开的
      {
            light=false;                //关灯
            jb.off++;                //关灯次数计数
#if (_PRINT_)
            printf("第一个出来放风的囚徒第%ld次关灯\n", jb.off);
#endif
      }
    }
    else                              //如果不是第一个出来放风的囚徒
    {
      if(!light)                      //如果灯是关的
      {
            if(jb.on == 0)         //如果他没有开过灯
            {
                light=true;             //开灯
                jb.on++;             //开灯次数计数
            }
      }
    }

    if(jb.first && jb.off == 99)//第一个放风的囚徒第99次关灯，结束
    {
      ok=true;
    }

#if (_PRINT_)
    printf("第%ld天结束，囚徒%d已经放风%ld次，开灯%ld次，关灯%ld次，灯%d\n",
               days,
               v,
               jb.count,
               jb.on,
               jb.off,
               light);
#endif
}

/* */
int main(void)
{
    init();
    while(!ok)
    {
      ff2();
    }

    printf("\n共%ld天，以下是每个囚徒出来放风的次数\n", days);
    for(long i=0; i < MAX_JAILBIRD; i++)
    {
      printf("%ld\t", jb.count);
    }

    printf("\n");

    return 0;
}

gxqcn 发表于 2009-6-18 21:31:59

7# 风云剑

这两种方案平均起来哪个更优？

shshsh_0510 发表于 2009-6-19 07:59:50

昨天想了想，这个问题还是比较有意思的，又查了查，下面是网上查的几种方法

第一天出來的這個囚徒負責關燈，以後出來的囚徒：
1）當燈是關著的時候，如果他沒有開過燈，那他可以打開燈，否則他不能開燈；
2）當燈是開著的時候，他不動燈。
3）第一個囚徒在他放風的時候，如果發現燈是開的，那麼他就關閉燈。這時他就把放過風的囚徒數加一。
當第一個囚徒的計數達到99的時候(加上他自己是100)，他就可以宣佈所有的囚徒都放過風啦,按平均計算100×99＝9900天，就是27年呀！



第二個方法分兩個階段：
階段一：前100天決定誰來計數。
1）第1-99天，初始燈關著，第一個兩次放過風的人將成為計數者，並將燈關上。設其為第K天第2次放風，則他知道已經有k-1個人放過風，做為100天後計數的初始值。
2）第100天放風的人如果看見等關著，則宣佈所有人都放過風；否則把燈關上
階段二：100天後
1）如果計數者放風看見燈開著，則將放過風的人數加1，到100時宣佈勝利
2）其他人如果以前沒放過風，並且燈關著，則開燈，否則不動
此方法期望年數為24.42年


第三種方法提示如下:分為一個基本記數者和N個2級記數者,基本記數者的獨立記數上限Cp和2級記數的獨立計數上限Cs,時間由長度為S1和S2的兩段交替組成.在S1階段,計數者計數直到達到其獨立計數上限,在S2階段,達到計數上限的2級計數者將通過開燈方法告訴基本計數者直到基本計數者得到所有2級計數者完成任務並加上自己計數為100時宣佈自由.
此方法通過計算機模擬優化可在10年左右完成.

shshsh_0510 发表于 2009-6-19 08:08:21

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

查看完整版本: 一个囚徒问题