猴子选大王-php面试题

封面图 • 2025-10-20 • PHP

“猴子选大王”是一个经典的算法问题，常被用作编程面试题，尤其是在 PHP 面试中。这个问题的典型描述是：

> 一群猴子排成一圈，从第1个开始报数，每轮数到 **k** 的猴子被淘汰，然后下一轮从下一个猴子开始继续报数，直到只剩下一只猴子为止，这只猴子就是“大王”。

---

## 一、题目示例

假设总共有 `n` 只猴子，每次数到 `k` 的猴子被杀，问最后哪只猴子能成为“大王”。

### 示例：
- n = 5（猴子数量）
- k = 2（每轮数到2的被淘汰）

答案：**3号猴子**

---

## 二、解法思路

这是一个典型的 **约瑟夫环（Josephus Problem）** 问题。

### 方法一：模拟法（适合小规模数据）

我们可以使用循环和数组来模拟这个过程。

```php
function monkeyKing($n, $k) {
    $monkeys = range(1, $n); // 创建一个包含1~n的数组
    $index = 0;

while (count($monkeys) > 1) {
        $index = ($index + $k - 1) % count($monkeys);
        array_splice($monkeys, $index, 1); // 删除该位置的猴子
    }

return $monkeys[0];
}

// 测试
echo monkeyKing(5, 2); // 输出 3
```

---

### 方法二：递归法（数学方法）

约瑟夫环问题可以用递推公式解决：

$$
f(n, k) = \begin{cases}
0 & \text{if } n = 1 \\
(f(n-1, k) + k) \% n & \text{if } n > 1
\end{cases}
$$

注意：这里的结果是从 0 开始编号的，所以最终结果要加 1。

```php
function josephus($n, $k) {
    if ($n == 1) {
        return 0;
    } else {
        return (josephus($n - 1, $k) + $k) % $n;
    }
}

// 调用
echo josephus(5, 2) + 1; // 输出 3
```

---

## 三、面试中可能的问题

在 PHP 面试中，面试官可能会问以下问题：

1. 如何优化这个算法？
   - 模拟法时间复杂度为 O(nk)，当 n 很大时效率低。
   - 递归法时间复杂度为 O(n)，更高效。

2. 如果 k 是固定的，如何进一步优化？
   - 使用数学公式直接计算，不需要模拟或递归。

3. 如果猴子编号不是从 1 开始而是从 0 开始，怎么处理？

4. 如果 n 和 k 都很大，比如 n=100000，k=1000，哪种方法更好？

---

## 四、总结

| 方法 | 时间复杂度 | 适用场景 |
|------|-------------|----------|
| 模拟法 | O(nk) | 小规模数据 |
| 递归法 | O(n) | 中等规模数据 |
| 数学公式 | O(1) | 大规模数据 |

---

如果你正在准备 PHP 面试，建议掌握这两种方法，并理解它们的优缺点。如果有具体题目或参数，也可以告诉我，我可以帮你进一步分析。