经典面试题：老鼠试毒药

“老鼠试毒药”是一个经典的面试题，通常用来考察面试者对二进制编码和信息理论的理解。这个问题有很多变体，以下是常见的一种表述及其解答。

问题描述

有 1000 瓶药水，其中 999 瓶是安全的，1 瓶是有毒的。你有一些老鼠可以用来进行实验，每只老鼠在喝了毒药后，都会在 24 小时内死亡。现在，你如何通过最少数量的老鼠，在 24 小时内找出那瓶有毒的药水？

解答思路

这个问题的关键在于如何用最少的老鼠得到最多的信息。因为每只老鼠的状态（活/死）可以看作是二进制的状态，因此可以通过二进制编码的方式解决这个问题。

解题步骤

转换为二进制问题

每只老鼠有两种状态：存活或死亡，类似于二进制的 0 和 1。如果有 n 只老鼠，那么每次实验的结果（即 n 只老鼠的存活或死亡状态）可以组合成一个 n 位的二进制数。这意味着 n 只老鼠可以区分 2^n 种情况。

计算最少需要的老鼠数量

你需要能够区分 1000 瓶药水的所有情况，也就是在 1000 瓶药水中找到那一瓶有毒的。所以需要 2^n >= 1000，其中 n 是老鼠的数量。

通过计算，找到最小的 n 值：

• 2^9 = 512（不够）
• 2^10 = 1024（足够）

这意味着最少需要 10 只老鼠。

具体编码方法

给每瓶药水编号 0 到 999，将这些编号转换成二进制。每个编号用 10 位二进制数表示，因为有 10 只老鼠。对于第 i 瓶药水，它的二进制编号的第 j 位（0 或 1）决定了第 j 只老鼠是否喝该瓶药水：

• 如果第 j 位是 1，则第 j 只老鼠喝这瓶药水
• 如果第 j 位是 0，则第 j 只老鼠不喝这瓶药水

实验结果

24 小时后，观察哪些老鼠死亡。死亡老鼠的组合会形成一个二进制数，这个二进制数对应的就是有毒药水的编号。

例子说明

假设有 5 瓶药水（用 3 只老鼠来区分，2^3 = 8 大于 5 瓶药水），对应的编号为：

瓶子	二进制
瓶子 1	001
瓶子 2	010
瓶子 3	011
瓶子 4	100
瓶子 5	101

在实验中：

• 第 1 只老鼠会喝编号中二进制第 1 位为 1 的药水（瓶 1、瓶 3、瓶 5）
• 第 2 只老鼠会喝瓶 2、瓶 3
• 第 3 只老鼠会喝瓶 4、瓶 5

如果实验结束后，第 1 和第 3 只老鼠死亡，而第 2 只老鼠存活，那么死亡的二进制组合是 101，对应的就是瓶 5，说明瓶 5 是有毒的。

总结

通过将每瓶药水的编号转换为二进制，并用老鼠的生死状态表示二进制位，可以在使用 10 只老鼠的情况下，在 24 小时内从 1000 瓶药水中准确找到有毒的那一瓶。这种方法有效地利用了二进制编码的思想，极大减少了所需实验次数和老鼠数量。

JavaScript 代码实现

可以用 JavaScript 来模拟这个老鼠试毒药的场景。按照解题思路，利用二进制来分配老鼠喝药水的方式，最后通过老鼠的生死状态找到有毒的药水。

// 模拟老鼠试毒药的算法
const findPoisonedBottle = (bottles) => {
  const numberOfBottles = bottles.length; // 药水的数量
  const numberOfMice = Math.ceil(Math.log2(numberOfBottles)); // 所需老鼠的数量

  // 将每瓶药水的二进制编号映射给老鼠
  const mice = new Array(numberOfMice).fill(0).map(() => []);

  // 让老鼠按照二进制位喝药水
  for (let i = 0; i < numberOfBottles; i++) {
    const binary = i.toString(2).padStart(numberOfMice, '0'); // 将药水编号转成二进制
    for (let j = 0; j < numberOfMice; j++) {
      if (binary[j] === '1') {
        mice[j].push(i); // 如果该位为1，则第j只老鼠喝这瓶药水
      }
    }
  }

  // 模拟实验，标记哪只老鼠会死
  const deadMice = new Array(numberOfMice).fill(0);
  for (let i = 0; i < numberOfMice; i++) {
    for (let j = 0; j < mice[i].length; j++) {
      const bottleIndex = mice[i][j];
      if (bottles[bottleIndex] === 'poisoned') {
        deadMice[i] = 1; // 老鼠死了
        break;
      }
    }
  }

  // 根据死亡的老鼠找出有毒的药水
  const binaryResult = deadMice.join('');
  const poisonedBottle = parseInt(binaryResult, 2); // 将二进制转换回十进制

  return poisonedBottle;
};

// 测试用例
// 假设有 1000 瓶药水，随机标记其中一个为 "poisoned"
const numberOfBottles = 1000;
const bottles = new Array(numberOfBottles).fill('safe');
const poisonedIndex = Math.floor(Math.random() * numberOfBottles); // 随机有毒药水
bottles[poisonedIndex] = 'poisoned';

// 找出有毒的药水
const result = findPoisonedBottle(bottles);
console.log(`有毒的药水是第 ${result} 瓶`);
console.log(`实际有毒的药水是第 ${poisonedIndex} 瓶`);

代码说明

findPoisonedBottle 函数接收药水数组 bottles 作为参数，每瓶药水的状态要么是 "safe"（安全的），要么是 "poisoned"（有毒的），函数返回有毒药水的编号。

二进制映射：将药水的编号转换成二进制字符串，用这些二进制位来决定哪只老鼠喝哪瓶药水。假设一瓶药水的二进制编号的第 i 位是 1，那么第 i 只老鼠就会喝这瓶药水。

老鼠的死亡状态：遍历每只老鼠喝过的药水，如果该老鼠喝了有毒的药水，标记这只老鼠死亡（即在 deadMice 数组中将对应的值设为 1）。

结果分析：最后通过死亡的老鼠组合成的二进制字符串，可以反推出有毒的药水编号。

运行结果示例

有毒的药水是第 123 瓶
实际有毒的药水是第 123 瓶

复杂度分析

时间复杂度为 O(N * M)，其中 N 是药水的数量，M 是老鼠的数量（即 log(N)）。需要将每瓶药水分配给若干只老鼠，然后根据老鼠的死亡状态推导出有毒药水。

空间复杂度为 O(N)，创建了一个数组来存储每瓶药水的状态。

这个解法很好地展示了如何使用信息论中的二进制编码思想，用最少的实验次数找出有毒的药水。

延伸阅读

这道题的核心思想——用 n 个 bit 区分 2^n 种情况——在实际工程中有着广泛的应用。

Linux 文件权限的位掩码设计就是同一个套路：每个权限（读/写/执行）占据一个独立的 bit 位，通过位运算 OR 组合权限、AND 检查权限，一个整数就能表达完整的权限集合。

网络领域的子网掩码也是位掩码的经典应用。255.255.255.0 用二进制表示就是前 24 位为 1、后 8 位为 0，通过位运算 AND 就能快速提取网络地址，判断两台机器是否在同一个子网。

这三者的底层逻辑完全相通：用最少的 bit 表达最多的状态，用位运算快速提取或判断。感兴趣可以对照本站的《Linux 数字权限设计方法》和《IP 地址：从 IPv4 到 IPv6》两篇文章，体会掩码设计在不同场景下的应用。