模拟百囚徒问题

一道非常著名的“反直觉”智力题_哔哩哔哩_bilibili一道非常著名的“反直觉”智力题：——有100名编号分别为1，2，3......100的囚犯。——每个囚犯的编号都写在一张纸条上。这100张纸条，被随机放入一个房间里的100个外观相同的盒子里。每个盒子里放一张纸条。——每个囚犯可以单独进入房间一次，任意查看50个盒子，看完后要将盒子盖上，不留下任何痕迹。如果他能恰好看到“自己的编号”，视为完成任务，需要立刻离开房间。——囚犯们可以在开始之前讨论策略, 视频播放量 608827、弹幕量 964、点赞数 18316、投硬币枚数 1722、收藏人数 12315、转发人数 5070, 视频作者 lovelyff998, 作者简介 ，相关视频：数学有一个致命的缺陷，你应该站在哪个位置，才能活到最后？，无限巧克力悖论，美国竞赛题，老外半天没算对，中国学生一招搞定，万字解析：今天的游戏技术究竟发展到了什么程度？，怎样解释祖父悖论？，人 类 低 质 量 翻 译 鉴 赏（14），为什么成功人士从来不写待办清单（To-Do List） ？► 她提到的这个方法更有效 - 百万人气网红企业家 Rachel Hollis 瑞秋‧霍利（中英字幕），能够感受“炁”的身心小游戏，这个世界最大的幻觉https://www.bilibili.com/video/BV1kt4y1t75F?p=1&share_medium=android&share_plat=android&share_session_id=55f1ff0e-fda4-43be-8c5a-112768033498&share_source=QQ&share_tag=s_i×tamp=1656936860&unique_k=Ru3JMdE&vd_source=78c5a56b2b804449168dbad7346576d9

#include <iostream>
#include <time.h>
using namespace std;
const int N = 100;
int dfs(int a[], int x, int vis[]) {
    if (vis[a[x]]) {
        return 0;
    }
    vis[a[x]] = 1;
    return dfs(a, a[a[x]], vis) + 1;
}
int main() {
    srand(time(0));
    int cnt = 0, T = 100000;
    for (int round = 0; round < T; round++) {
        int a[128] = {0};
        for (int i = 1; i <= N; i++) {
            a[i] = i;
        }
        for (int i = N; i > 1; i--) {
            int r = 1 + rand() % i;
            int t = a[i];
            a[i] = a[r];
            a[r] = t;
        }
        int vis[128] = {0};
        for (int i = 1; i <= N; i++) {
            if (dfs(a, i, vis) > (N >> 1)) {
                cnt++;
                break;
            }
        }
    }
    cout << 1.0 * cnt / T;
    return 0;
}