TP-LINK 最爱考的智力题:1000瓶药水找毒药

文章来自 @一个搬砖的胖子 我只是搬运工
顺便推荐胖哥开发的高频题库 https://codetop.cc 真的nice!!

一共 1000 瓶药水,其中 1 瓶有毒药。已知小白鼠喝毒药一天内死,若想在一天内找到毒药,最少需要几只小白鼠?

答案:10 只。

解析:二进制思想。

0 000 000 001表示 1 号老鼠,喝了药水 1 。
0 000 000 010表示 2 号老鼠,喝了药水 2 。
0 000 000 011表示 1 号、 2 号老鼠,喝了药水 3 。
… …
1 111 101 000表示 4、6、7、8、9、10号老鼠,喝了药水 1000。

按照上述的方法依次喝

第一回合,1 号老鼠喝药水 1

第二回合,2 号老鼠喝药水 2

...

第一千回合,4、6、7、8、9、10号老鼠喝药水 1000

喝完一天时,看 10 只老鼠的状态,根据老鼠状态就知道哪瓶药水有毒了。

比如最后只是 2 号老鼠死了,那就说明第2瓶药水有毒;如果4、6、7、8、9、10死了,那就说明第1000瓶药水有毒!


想明白这个道理,再来看怎么答案为何是10

我们需要让二进制表示的种类数>=药水总数(1000)

求的是最小值,显然,为10的时候满足要求

也可以这么计算:⌈ log N ⌉,log底数为2



#Java工程师实习##TP-LINK##面试题目#
全部评论

相关推荐

头像
不愿透露姓名的神秘牛友
今天 11:02
已编辑
华为车bu(签新公司) 通软 29*12+(0-10万) 硕士985
点赞 评论 收藏
转发
5 13 评论
分享
牛客网
牛客企业服务