首页｜我的编程技术分享 | 趣味算法：国王和100个囚犯

趣味算法：国王和100个囚犯

2592 次阅读，发布于 : 2023-11-29

> 本文由 [简悦 SimpRead](http://ksria.com/simpread/) 转码， 原文地址 [zhuanlan.zhihu.com](https://zhuanlan.zhihu.com/p/80472777)

前几天在网上看到了一个有趣的问题，就是**国王和 100 个囚犯**的问题。第一次看到这个问题时，当时也懵了，这是什么鬼？你确定你题出的木有问题？当时就是这感觉.....

但仔细思索后还是想到了解决方法，让我们一起来看看这个有趣的问题吧。

![](https://pic4.zhimg.com/v2-873875d77541c9ef4f7ad16f0627fc0f_b.jpg)

**题目如下：**

国王招来 **100 个囚犯**，对他们说：你们犯的是死罪，但我给你们一次求生的机会。15 分钟以后，你们将被关进一个有 100 间隔离牢房的监狱里，每人一间牢房，都与外界隔绝，什么也听不见看不到，连时间都没法计算，无法获得外界的任何信息。

这所监狱有一个院子，每天只少**随机（注意是完全随机）打开一间牢房的门**，让一个囚犯到院子里来放风。**院子里有一盏灯**，放风的囚犯可以控制它的开关，**将它打开或是关闭**。除囚犯之外，其他人都不会去碰开关。这盏灯会永远有充足的能源供应，灯泡和电路不会出故障。

![](https://pic4.zhimg.com/v2-c962b38953be355d67b67d0ba6a8600b_r.jpg)

> 除了开关这盏灯，放风的囚犯放风时留下的任何其它痕迹都会在夜晚被清除干净（包括在灯上作的任何记号）。牢房是完全封闭的，院子里的灯光在牢房里看不到。只有放风到院子里的人才能看到。

国王：好了现在我向你们提出一个要求，只要你们做到了，就可以全部获得释放：

> 给你们 15 分钟商量你们的方案。15 分钟以后，你们将被关进我刚才说的那个监狱，永远无法再交流，被关若干天后，你们中间如果任何一个人能够向我证明你们每个人都至少放风了一次，我就把你们放了，不然永远别想再出来。

如果你们有谁现在可以告诉我这个方法，也就是能够证明你们每人至少放风一次的方法，我就放掉你们！

其中一个囚犯想了几分钟，回答了这个问题，国王听后，如自己所说的把他们全部给放了。请问那个囚犯是用什么方法证明的？

大致的解题思路（建议思考后再看）:
-----------------

还赶紧用你的 2.4G 赫兹的 4 核 CPU 大脑思考下，该如何解决？

![](https://pic3.zhimg.com/v2-26ed214f6adabc1f254a957ee1fafe5e_r.jpg)

> 100 个囚犯商量选出一个囚犯作为**计数员（PrisonerCounter）**，**普通囚犯 (Prisoner)** 每次出去，如果自己没有打开过灯，并且灯是灭的，则打开灯；其它情况均不操作。计数员每次出去，如果灯是亮的就自己计数一次，并把灯关掉，其它情况什么也不干。一直到计数员计数到 100，则全部囚犯都出去过至少打过一次灯。

再来细化化下每个角色的职责：

*   计数员： 如果灯亮，计数一次，并关灯。如果灯灭，啥事不干。
*   普通囚犯：如果自己没有开关灯，并且现在灯灭，就打开灯；如果自己以前开过灯或现在灯亮，则什么也不做。
*   灯：能开、能关

看到这里，你应该有一种虎躯一震的感觉，还有这骚操作.......

来看看代码具体怎么实现的吧
-------------

**对象：阿拉丁神灯**（这个灯好像不太神，只能开与关，但却掌握着 100 人的生与死）

```
/**
     * 阿拉丁神灯
     * @Author: danding
     * @Date: 2019/8/30
     */
    public class Light {
        //灯的状态（true-开，false-关）
        private Boolean state;
    
        public Light() {
            this.state = false;//默认为关
        }
    
        public Boolean getState() {
            return state;
        }
    
        public void setState(Boolean state) {
            this.state = state;
        }
    }
```

**对象：普通囚犯**

```
/**
 * 囚犯
 * @Author: danding
 * @Date: 2019/8/30
 */
public class Prisoner {
    //囚犯编号
    private int id;
    //是否打开过灯
    private Boolean isOpenLight = false;
    //院子里的灯
    protected Light light;

public Prisoner(int id) {
        this.id = id;
    }

/**
     * 放风时要干的事件
     * @return 普通囚犯返回值无意义
     */
    public boolean doSomeThing(){
        if(light==null){
            return false;
        }
        //如果这个囚犯放风时，打开过灯，则这次出去什么也不做
        if(isOpenLight==true){
            System.out.println(String.format("囚犯编号：%d，大爷的，怎么又是我，我已经开过灯了....",id));
            return false;
        }
        //如果出去发现灯的亮的，则什么也不做
        if(light.getState()==true){
            System.out.println(String.format("囚犯编号：%d，大爷的，第一次出来，灯竟然被占用了...",id));
            return false;
        }
        //如果这个囚犯被放风还没有开过灯：
        if(light.getState()==false){//如果出去发现灯的灭的，他就打开灯
            System.out.println(String.format("囚犯编号：%d，我终于出来放风了，还是第一次呢，有点小鸡冻（激动）呢！！！",id));
            light.setState(true);
            this.isOpenLight = true;
        }
        return false;
    }

/**
     * 赋予或移除灯
     * @param light
     */
    public void setLight(Light light) {
        this.light = light;
    }
}
```

**对象：囚犯计数员（比普通囚犯多一个计数功能）**

```
/**
 * 囚犯计数人
 * @Author: danding
 * @Date: 2019/8/30
 */
public class PrisonerCounter extends Prisoner{
    //已开灯的人数(自己不计算在内)
    private int prison_out_count = 1;

public PrisonerCounter(int id) {
        super(id);
    }

/**
     * 囚犯计数者每次放风：
     * 如果灯亮，则计数一次，并把灯关了
     * 如果灯灭，不作任何操作
     * @return true-全部人都打开过灯一次，false-还有其它人没有开过灯
     */
    public boolean doSomeThing(){
        if(super.light==null){
            return false;
        }
        if(super.light.getState()==false){
            return false;
        }

this.prison_out_count++;
        System.out.println(String.format("当前第%d个囚犯打开了灯",this.prison_out_count));
        if(this.prison_out_count>=100){
            return true;
        }
        super.light.setState(false);
        return false;
    }
}
```

对象：上帝（主宰一切，什么都是我说了算）

```
import java.time.Period;
import java.util.ArrayList;
import java.util.List;
import java.util.Random;

/**
 * 上帝，掌握着一切
 * @Author: danding
 * @Date: 2019/8/30
 */
public class God {

public static void main(String[] args){
        //所有囚犯集合
        List<Prisoner> prisonerList = new ArrayList<>();
        //初始化1个计数者
        Prisoner prisoner = new PrisonerCounter(0);
        prisonerList.add(prisoner);
        //初始化99个囚犯
        for(int i=1;i<100;i++){
            prisoner = new Prisoner(i);
            prisonerList.add(prisoner);
        }

//初始化一个院子里的灯
        Light light = new Light();
        Random random = new Random();
        int day = 0;
        boolean isOver;
        do{
            day++;//计天数
            //每天随机抽一个囚犯
            int index = random.nextInt(prisonerList.size());
            prisoner = prisonerList.get(index);
            //出去放风，这个时候这个囚犯拥有控制灯的权限
            prisoner.setLight(light);
            //干约定好的事件
            isOver = prisoner.doSomeThing();
            //回老方，没收控制灯的权限
            prisoner.setLight(null);
        }while(!isOver);
        System.out.println(String.format("经历了%d天，所有囚犯都出去开过至少一次灯",day));
    }
}
```

代码完了，让我们一起来看看这 100 个囚犯大概多久能出来吧

```
...
...省略部分
...
囚犯编号：88，我终于出来放风了，还是第一次呢，有点小鸡冻（激动）呢！！！
囚犯编号：72，大爷的，怎么又是我，我已经开过灯了....
囚犯编号：50，大爷的，怎么又是我，我已经开过灯了....
囚犯编号：86，大爷的，怎么又是我，我已经开过灯了....
囚犯编号：53，大爷的，怎么又是我，我已经开过灯了....
囚犯编号：48，大爷的，怎么又是我，我已经开过灯了....
囚犯编号：23，大爷的，怎么又是我，我已经开过灯了....
囚犯编号：4，大爷的，怎么又是我，我已经开过灯了....
囚犯编号：17，大爷的，怎么又是我，我已经开过灯了....
囚犯编号：35，大爷的，怎么又是我，我已经开过灯了....
囚犯编号：99，大爷的，怎么又是我，我已经开过灯了....
当前第100个囚犯打开了灯
经历了10483天，所有囚犯都出去开过至少一次灯
```

![](https://pic3.zhimg.com/v2-777b123ad10bee96b67ec1c6d6640072_r.jpg)

**what？**这不得等上将近 30 年...... 随间歇菜.....

想来也对，因为每天放风的囚犯都是随机的，至于多少天能出来，完全看运气了。  
以上运行结果并没有什么参考意义，因为你每次运行的结果都不一样，并且差别应该也不小。

运气绝对好，至少需要多少天？
--------------

作为高逼格的蜗牛哥绝不能就达此结束了，我们得想想他们运气绝对好，每次都能中彩票一等奖，这种情况下，他们最快多少天能出来呢？

**给你 5 分钟思考时间**

![](https://pic1.zhimg.com/v2-82495126655fe22531a8935cb7305248_r.jpg)

如果运气绝对好，那么他们的出场顺序应该是这样的：

```
第01天：囚犯01号
第02天：囚犯计数员
第03天：囚犯02号
第04天：囚犯计数员
第05天：囚犯03号
第06天：囚犯计数员
......
第195天：囚犯98号
第196天：囚犯计数员
第197天：囚犯99号
第198天：囚犯计数员
```

也就是说他们运气绝对好，至少需要 198 天就可以全部出狱了，这个结果还是让人满意的，也就大半年时间。

到这里就该真的结束了，希望通过这个趣味小实验，能让你从中学到些什么，哪怕有一丁点的帮助，小蜗牛在此也欣慰了。

关注公众号:**「Java 知己」**，每天更新 Java 知识哦，期待你的到来！

*   发送「**1024**」，免费领取 30 本经典编程书籍。
*   发送「**Group**」，与 10 万程序员一起进步。
*   发送「**JavaEE 实战**」，领取《JavaEE 实战》系列视频教程。
*   发送「**玩转算法**」，领取《玩转算法》系列视频教程。

![](https://pic4.zhimg.com/v2-9381c24367f4f5b4185f4d9e38b02f3b_r.jpg)