您现在的位置是:首页 > 学无止境 > 其他网站首页其他 16杯水只有一杯有毒,最少用多少老鼠测试能找出有毒?二进制方法快速找出

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

  • 莫愁
  • 其他
  • 2019-11-07
简介有一个需求如下,用最短时间以及最少老鼠测出哪一杯水有毒,使用的每一只老鼠可以喝多杯水。
字数 1238

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

常规思路

需要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。

权限 二进制代码
无任何权限 000
可执行 001
可写 010
可写可执行 011
可读 100
可读可执行 101
可读可写 110
可读可写可执行 111

 

看了是不是有点感觉了?发现左边出现1有可读,中间出现1有可写,右边出现1可执行。3个权限可以组成8个数字,也就是2^3。

下面我们来给16杯水编号。

0001 0010 0011 0100 0101 0110 0111 1000
1001 1010 1011 1100 1101 1110 1111 0000

 

是不是只花了4位来编号,每一位混合组合可以得到唯一的一杯水,将每一位看成一只老鼠,我们只需要知道哪些老鼠死了,即可找到所对应的唯一一杯有毒的水。


转载: 感谢您对莫愁个人博客网站平台的认可,非常欢迎各位朋友分享到个人站长或者朋友圈,但转载请说明文章出处“来源莫愁个人博客 https://www.mochoublog.com/study/365.html”。

文章评论

    • 评论
    人参与,条评论

技术在线

服务时间

周一至周日 12:00-22:00

关闭下雪
关闭背景特效

最新文章