能理解这个 说明你的思维理解能力没有问题,适合当程序员
面试题如下:有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”也明明白白的,转成十进制,毒药就显而易见啦。
学习的时候参考的这位大佬,写的很详细,为了使自己记得更清楚一点,用自己的语言重写一遍,看不懂我写的可以看一下该博主。
嘻嘻嘻,再次膜拜大佬!(以及十只小白鼠的友情出演~)