微软|微软面试题:1000个瓶子,999瓶是水,1瓶是毒药,怎么找出那瓶毒药?

微软|微软面试题:1000个瓶子,999瓶是水,1瓶是毒药,怎么找出那瓶毒药?

文章图片

微软|微软面试题:1000个瓶子,999瓶是水,1瓶是毒药,怎么找出那瓶毒药?

【微软|微软面试题:1000个瓶子,999瓶是水,1瓶是毒药,怎么找出那瓶毒药?】微软面试题 , 有1000个瓶子 , 其中999瓶是水 , 1瓶是毒药 , 外观无法区别 。 现有10只小白鼠和无限多干净试管 , 怎么找出那瓶毒药?

用混检的方法即可实现:
1、1000个分两组(500/组):会死一只老鼠
2、剩余分两组(250/组):会死一只老鼠
3、125/组:死一只
4、62.5/组:死一只
5、31.25/组 死一只
6、15.6/组 死一只
7、7.8/组 死一只
8、3.9/组 死一只
9、1.9/组 死一只
10、第十次刚好验证出有毒的瓶子

但我觉得这种类似穷举的算法不够优雅 , 各位大神还有何高见?


网友:为何要十次 , 三到四次即可 。 把1000只分十份 , 每份100只取样混合给十只老鼠吃 , 死一只老鼠确定100瓶 , 再分十份给九只老鼠吃 , 再死一只确定十瓶 , 再分十组给八只老鼠吃 , 确定一瓶或二瓶 。 死到四只老鼠就行了 。


网友:这题考一个 , 算法 , 逻辑!可以有很多种解法 , 要问清楚 , 1000瓶子是多大容量 , 一只小白鼠有多大 , 能喝多少水 , 有没有时间要求 , 小白鼠死几只?等等?!这样才是一个合格的程序员 。


网友:分成11份 , 10份90瓶 , 1份100瓶 , 前10份给10只老鼠喝 , 死了就在90瓶里 , 没死就在100瓶里 , 然后继续按这个方法 , 最多3次 , 优点在于运气好时一只老鼠都不用死 。