janqii

国王招来100个囚犯，对他们说：你们犯的是死罪，本应该将你们统统杀掉，但我慈悲为怀，给你们一次求生的机会。15分钟以后，你们将被关进一个有100间隔离牢房的监狱里，每人一间牢房，都与外界隔绝，什么也听不见、看不到，连时间都没法计算，更别说获得外界的任何信息。（送饭除外，但也是不规律的送）

这所监狱有一个院子，每天会随机（注意是完全随机）打开一间牢房的门，让那个囚犯到院子里来放风。院子里有一盏路灯，放风的囚犯可以控制它的开关，将它打开或是关闭。除囚犯之外，其他人都不会去碰开关。这盏灯会永远有充足的能源供应，如果灯泡坏了或是电路出了故障会马上修好，当然修理人员不会改变灯的状态（开或关）。

除了开关这盏灯，放风的囚犯放风时留下的任何其它痕迹都会在夜晚被清除干净（包括在灯上作的任何记号）。

牢房是完全封闭的，院子里的灯光在牢房里看不到。只有放风出到院子里的人才能看到。

好了现在我向你们提出一个要求，只要你们做到了，就可以全部获得释放： 若干天以后，你们中只要有任何一个人能够向我证明所有的人都曾到院子里去过，你们就全体释放。当然要有证据！因为我只会给你们一次机会，如果向我证明的那个人无法自圆其说，你们就全部砍头。所以，要珍惜这次机会。如果你们永远做不到我的要求，你们就全部关到死。

现在给你们15分钟商量你们的方案。15分钟以后，你们将被关进我刚才说的那个监狱，永远无法再交流。

-------------------------------------------------------------------------------------------------------------

第一天出来的人作为“计数者”（第一个出来的人确定自己是“计数者”，其他人确定自己不是“计数者”）

如果是“计数者”就把灯打开（关闭的情况下打开），计数+1，若灯开着的话就什么也不做

如果不是“计数者”，如果是第一次出来放风而且灯开着就关闭它，否则什么也不做

当“计数者”的 counter=100的时候就可以想国王申请走人了。

-------------------------------------------------------------------------------------------------------------

这种算法需要多长的时间才可以获得释放呢，写代码验证之。答案是10000天左右，也就是20-30年的时间，够漫长的。不知道还有没有其他更好的方法。

#include<iostream>
#include<vector>
#include<ctime>
using namespace std;

int   getDays(void);
bool not_selected(vector<int> v,int key);

int main(void)
{
cout<<getDays()<<endl;
return 0;
}

int getDays(void)
{
int observer=-1;
int rd=-1;
int counter=0;
int days=0;
vector<int> prison;
volatile bool b_light=false;

srand(time(NULL));
observer=rand()%100;
b_light=true;
days++;

while(1)
{
   days++;
   if((rd=rand()%100)==observer)
   {
    if(b_light==false)
    {
     counter++;
     b_light=true;
    }
    if(counter==99)
     break;
   }
   else
   {
    if(b_light&&not_selected(prison,rd))
    {
     prison.push_back(rd);
     b_light=false;
    }
   } //else
} //while

return days;
}

bool not_selected(vector<int> v, int key)
{
for(vector<int>::iterator iter=v.begin();iter!=v.end();++iter)
{
   if(*iter==key)
    return false;
}

return true;
}