[面试题]1000瓶毒药里面只有1瓶是有毒的,问需要多少只老鼠才能试出那瓶有毒。 |
您所在的位置:网站首页 › 有多少人用梅毒试纸没测出来的 › [面试题]1000瓶毒药里面只有1瓶是有毒的,问需要多少只老鼠才能试出那瓶有毒。 |
题目:1000瓶毒药里面只有1瓶是有毒的,毒发时间为24个小时,问需要多少只老鼠才能在24小时后试出那瓶有毒。
思路:这题试Bloom Fliter 算法。详情可以参考:https://blog.csdn.net/jiaomeng/article/details/1495500 这题和我之前看到的一道题有点像。题为, 有1000个苹果,分别装在10个箱子里,任意给出1到1000之间的整数,都可以利用某几个箱子中的苹果数量获得次数。
2^10 =1024 。也就是说10层二叉树一定可以记录1000种的状态。每个节点放1。每一层的和就是一个数。 所以数分别为1 , 2 ,4 ,8,16, 32,64,128,256,489。(489=488+1,因为总数为1000)。
我们能表示出1024种状态。 这个题是对bit位的应用,1000接近1024,所以需要10个bit位,对瓶子进行编号,从0到999,这样需要10只老鼠。瓶子的编号分别为: 老鼠用 a ,b ,c ,d ,e ,f ,g ,h ,i , j ,表示 第0号瓶:00000,00000 第1号瓶:00000,00001 a 第2号瓶:00000,00010, b 第3号瓶:00000,00011 a b 第4号瓶:00000,00101 a c 第5号瓶:00000,00111 a b c 。。。。。。 第999号瓶:11111,00111 a b c [] [] f g h i j 同时给老鼠编号,从1,2,...10,从低位开始,让第n个老鼠喝下第n个bit位为1瓶子中的药水。24小时后,若所有的老鼠都没有发病,那么是第一个瓶子有毒,如果有一些老鼠发病,那么共同喝的那瓶毒药的二进制做与运算,得到的就是共同喝的那瓶,最低位+1,变成整数后,对应的数字即为有毒药水的编号。 比如:第四瓶有毒,全部做与运算得到的(编号第三号)00000011 +1 =00000100 = 4 。第四瓶有毒(没有第零瓶,所以+加1) 所以只要10只老鼠就能在 24小时后 排查出到底那瓶有毒。
看到有人用二分法解决: 第一次: 将1-500瓶兑在一起喝。 如果老鼠死了,则拿另一只老鼠去品尝501-725瓶兑的药水。否则去喝2-250瓶兑的水。 采用如此二分法,因为2^10>1000 2^9 |
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |