微软经典面试题，毒药和老鼠。。。

文章预览

有 1000 个酒瓶，其中一个瓶子里装着有毒的酒，如果老鼠喝了有毒的酒一小时就会死掉。给你一小时至少需要多少只老鼠才能找出哪个瓶子里有毒？ 思考半分钟再来看答案： 其实这题很简单，我们只需要把所有的酒瓶编上号，用二进制表示， 1000 个酒瓶只需要 10 个二进制位就够了，因为 2^10=1024，大于 1000 了，所以至少需要 10 只老鼠。 任何一个酒瓶的二进制位中如果右边第 1 位是 1 ，就让第 1 只老鼠尝，如果右边第 2 位是 1 ，就让第 2 只老鼠尝，如果右边第 n 位是 1 ，就让第 n 只老鼠尝。。。 假如一个小时之后第 1 ，3，5 这三只老鼠死了，说明二进制位中右边第 1 ， 3，5 位肯定是 1 ，也就是 0000010101(总共 10 位)，转化为二进制就是 21 ，也就是第 21 个酒瓶肯定是有毒的。 --------------下面是今天的算法题-------------- 来看下今天的算法题，这题是 ………………………………