小王庄村 2020-10-30 16:22 采纳率: 0%
浏览 351

(非常烧脑)1000瓶药水,只有一瓶是有毒的,如何使用最少的小白鼠测出那瓶是毒药?

能理解这个 说明你的思维理解能力没有问题,适合当程序员

面试题如下:有1000瓶药水,只有一瓶是有毒的,小白鼠喝了就会身亡,但是需要一天的时间才会有结果,而且你只有一天时间去判断,问题是,如何使用最少的小白鼠,试验出哪瓶是毒药?

答: 转换成二进制,最少需要10只 ,2^10=1024,为什么这么取呢,我们将1000瓶药水变成二进制,我们需要得知多少位二进制可以表示1000瓶药水,下方是我们求的步骤:

1.第一步,将1000瓶药水编上编号1.2.3....1000,取十只小白鼠也编上编号1.2.3...10。

2.将十只小白鼠按照二进制的位数排列,排列除了1024种组合,将1000瓶药水编号转成二进制,如果小白鼠的位数是1(这里要好好理解一下,理解好了这里你就懂的差不多了),就给当前位数的小白鼠喝下去。

3.将1000瓶药水依次喂给小白鼠喝下去。

4.一天后,将死亡的小白鼠的二进制数转成十进制,该编号的药水就是毒药。

例如:

1.编号为66的药水,转换成二进制就是 00 0100 0010 ,此时喂给编号2与7的小白鼠喝下去。以此类推。。。

2.判断结果时,比如小白鼠死亡的编号是 00 0101 1100,转换成十进制就是92号,那么92号药水就是毒药。

注意Tips:

这个算法从面试到现在看了很多遍,过了一阵就会弄混,今天彻底捋请了一下:

1.如何将1000瓶给小白鼠喂下去(博主脑残,所以超过10的数就摆楞不过来了,还请见谅(#`O′),再次遇到了瓶颈hiahiahia。。。):

首先第一步是将1000瓶与十位二进制扯上关系,即转换成二进制,变成了0/1数列,然后按照“1”就喝,“0”就不喝,给他们喂下去(记得等分一下,不等分也没关系,只是为了让它们死的公平一点hiahiahia),不停的喂完1000瓶(你累了可以歇一下)

2.因为只有一瓶毒药,所以答案显而易见,可以假设前999瓶都是没毒的,十只小白鼠喝下去999瓶全都安然无恙(此时不包括它们撑死的可能(#`O′)),当最后一瓶喝下去之后,喝毒药死亡的某几只小白鼠就死的明明白白的,十位二进制哪位是“1”也明明白白的,转成十进制,毒药就显而易见啦。

学习的时候参考的这位大佬,写的很详细,为了使自己记得更清楚一点,用自己的语言重写一遍,看不懂我写的可以看一下该博主。

嘻嘻嘻,再次膜拜大佬!(以及十只小白鼠的友情出演~)

  • 写回答

1条回答 默认 最新

  • weixin_46009974 2022-02-03 13:07
    关注

    找人借990只小白鼠,一只试一瓶,结果死掉一只小白鼠,还给别人999只。

    评论

报告相同问题?

悬赏问题

  • ¥15 MATLAB怎么通过柱坐标变换画开口是圆形的旋转抛物面?
  • ¥15 寻一个支付宝扫码远程授权登录的软件助手app
  • ¥15 解riccati方程组
  • ¥15 display:none;样式在嵌套结构中的已设置了display样式的元素上不起作用?
  • ¥15 使用rabbitMQ 消息队列作为url源进行多线程爬取时,总有几个url没有处理的问题。
  • ¥15 Ubuntu在安装序列比对软件STAR时出现报错如何解决
  • ¥50 树莓派安卓APK系统签名
  • ¥65 汇编语言除法溢出问题
  • ¥15 Visual Studio问题
  • ¥20 求一个html代码,有偿