用c++编写一个程序：有 100 个囚犯分别关在 100 间牢房里。牢房外有一个空荡荡的房间，房间里有一个由开

Question

有 100 个囚犯分别关在 100 间牢房里。牢房外有一个空荡荡的房间，房间里有一个由开关控制的灯泡。初始时，灯是关着的（或者随机）。看守每天随便选择一名囚犯进入房间，但保证每个囚犯都会被选中无穷多次。如果在某一时刻，有囚犯成功断定出所有人都进过这个房间了，所有囚犯都能释放。游戏开始前，所有囚犯可以聚在一起商量对策，但在此之后它们唯一可用来交流的工具就只有那个灯泡。他们应该设计一个怎样的协议呢？请根据此协议设计实现一个程序，把解题过程详细输出并给出解题所需天数。求各位大佬帮帮忙！！！非常急啊

Answer 1

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

int getNumber()
{
return (rand() % 100) ;
}
int main()
{
int day = 0;
int toggle = 0;//0表示灯关闭,1表示灯打开
int all[100] = { 0 };//100个犯人的状态,0表示没来过,1表示来过
int count = 0;//记录来过的犯人数量等于100时结束
srand(time(0));
while (count < 100)
{
int once = getNumber();//随机抽取犯人
if (all[once] == 0)//若之前没有来过
{
all[once ] = 1;
if (toggle == 0)//若关着灯那么打开通知其他人
{
toggle = 1;
}
count++;//来过的人数累加
}
else//如果已经来过了
{
if (toggle == 1)//若灯开着那么关闭它,保持灯是关闭状态
{
toggle = 0;
}
}
day++;//天数累加
}

cout << "需要: " << day << " 天" << endl;
system("pause");
}

/*
有 100 个囚犯分别关在 100 间牢房里。牢房外有一个空荡荡的房间，房间里有一个由开关控制的灯泡。
初始时，灯是关着的（或者随机）。看守每天随便选择一名囚犯进入房间，但保证每个囚犯都会被选中无穷多次。
如果在某一时刻，有囚犯成功断定出所有人都进过这个房间了，所有囚犯都能释放。
游戏开始前，所有囚犯可以聚在一起商量对策，但在此之后它们唯一可用来交流的工具就只有那个灯泡。
他们应该设计一个怎样的协议呢？请根据此协议设计实现一个程序，把解题过程详细输出并给出解题所需天数。
*/
/*
分析：灯泡只有两种状态:开启关闭,囚犯也有两种状态:来过没来过.
完全可以一一对应,囚犯没来过只会出现一次,而来过则会出现多次,
假定灯开始时是关闭着的,如果有囚犯没来过那么把灯打开,如果来过了那么保持灯的关闭状态(如果原来是开着的关闭它)
记录灯打开的次数如果等于100次说明都来过了那么结束
*/

Answer 2

100个人协议好第一个进入房间的人当计数者，每个人（除计数者）通过开灯表示自己来过了，灯一旦打开，别人就不能关闭，只能等待计数者关闭。计数者关到第99次的时候，他就可以确定100个人都来过了。
实现代码如下：
#include <bits/stdc++.h>
using namespace std;
int counter, cnt;
bool vis[100];
bool flag;
void put(int id) {
if (counter == -1) {
counter = id; // 第一个进入房间的人当计数者
flag = 0; // 将灯恢复关闭状态
return;
}
if (id == counter && flag) {
// 只有计数者将灯关闭并计数
flag = 0;
++cnt;
}
if(id != counter && !flag && !vis[id]) {
// 非计数者第一次见到灯灭时，将灯打开
vis[id] = 1;
flag = 1;
}
}
bool check() {
// 检查是否所有人都进入了房间
return cnt == 99;
}
int main() {
int days = 0;
srand(time(NULL));
flag = rand() % 2; // 初始灯的状态随机
counter = -1;
while (true)
{
int id = rand() % 100; // 每次随机一个人进入房间
put(id);
days++;
if (check())
break;
}
printf("所需天数:%d", days);
return 0;
}

追问

Cannot open include file: 'bits/stdc++.h': No such file or directory
运行后提示错误，找不到这个头文件，大哥你是不是忘发了

追答

那就去掉该行，添加：
#include
#include

追问

ok，可以了