老鼠试药问题

[sunhengzhe]

一千瓶药里只有一瓶有毒，一周后毒发。用老鼠试药，一周内最少用多少只老鼠？

[sunhengzhe]

这道题很巧妙地利用了二进制的表示法（或者说出题者就是以此为基础构思的）
1000 瓶药有点多，以 4 瓶药举例：
首先将 4 瓶药以二进制形式排序。

00  // 药1
01  // 药2
10  // 药3
11  // 药4

因为 4 瓶药用 2 位的二进制就能表示了，所以我们只需要 2 只老鼠就能试出毒来了。
每只老鼠对应二进制的一位，且 喝位数为 1 所在药水的混合药水；
比如上面的例子里第一只老鼠对应 0011，那么喝 3 号、4 号药水的混合药水；
另一只对应 0101，那么喝 2 号和 4 号药水的混合药水；
这样对应也会出现 4 种情况：

• 活活（都没喝 1 号药水，1 号药水是毒药）
• 活死（只有 2 号喝了 2 号药水，2 号药水是毒药）
• 死活（只有 1 号喝了 3 号药水，3 号药水是毒药）
• 死死（都喝了 4 号药水，4 号药水是毒药）

同样原理，因为 1000 瓶药水可以用 10 位二进制表示，那么用 10 只老鼠就足够了。

[ksky521]

分治**，500瓶倒在一起喝，然后毒死的，再250瓶倒在一起。。。

[sunhengzhe]

@ksky521 一周后才毒发，所以这样一周试不出来吧 😳