16杯水只有一杯有毒，最少用多少老鼠测试能找出有毒？二进制方法快速找出

莫愁
其他
2019-11-07

简介有一个需求如下，用最短时间以及最少老鼠测出哪一杯水有毒，使用的每一只老鼠可以喝多杯水。
字数 567

有一个需求如下，用最短时间以及最少老鼠测出哪一杯水有毒，可以让老鼠喝多杯水。其实这个需求是一道经典的面试逻辑题，现在还有不少面试官会问这道题。那么遇见这种题该如何解答？

常规思路

需要15只老鼠，每一只老鼠喝一杯水，如果有老鼠死亡，那么就是老鼠喝的那一杯，都没死就是那一杯没有喝的水了。

进一步思考

让一只老鼠喝2杯，1-2杯一号老鼠喝，3-4杯二号老鼠喝.......15-16杯8号老鼠喝，这时候有一只老鼠死亡，那么我们可以将范围缩小到编号是X和X+1的两杯，在之前我们再拿一只老鼠喝编号是单的即可确认，这时候我们将老鼠数量缩减到了9杯。

我们再仔细看看，会发现我们还可以少一只老鼠，15到16号水我们可以不让8号老鼠喝，让八号来喝单的，这时候出现所有老鼠没死亡，则16号水有毒，只出现8号老鼠死亡则是15号水有毒，其余情况就是2只老鼠死亡。

深度思考

我们可以发现，当老鼠喝的水越多，我们可以将需求完善的更好，但是不同老鼠喝同一杯水，如何来准确确定那一杯水是有毒的呢？说一个关键词"777",大家是不是想到权限修改了啊，的确一个7表示了3样权限(可读,可写,可执行)，6表示两个权限(可读，可写), 5表示两个权限(可读，可执行)....1表示一个权限(可执行)，我们会发现三个权限可以组成7个不同的数字组合，每一个数字表示了唯一的权限组合。

而这些是如何来的，就要讲到二进制了，在Linux中，可读的二进制位是2，可写的二进制位是1，可执行的二进制位是0。