关注公众号 后端搬运工《王者编程大赛之四 — 猴子选大王》

每年夏季公司都会组织夏季夏令营活动，给来京参加夏令营的小朋友准备礼物。

组委会准备了一些小游戏来获得这些礼物，其中有一个游戏是这样的：组委会让小朋友围成一个圈。然后随机制定一个数 e，让编号为 0 的小朋友开始报数。每次喊道 e-1 的小朋友直接出列，淘达出局。从本次喊道 e-1 的下一个小朋友开始，继续从 0 报数…e-1 淘汰出局…一直这样进行…最后进行到最后一个小朋友，这位小朋友可以拿到一些奖品。（注：小朋友的编号是从 0 到 n-1 )

示例：
输入：n=1314 e=520
输出：796
输入：n=88888 e=1018
输出：69148

解题思路

该题是一个 约瑟夫环 问题（猴子选大王），这里运用数学知识找出递推关系式。

假设，总共有 n 个人，数到 k（n >= k）的人被杀掉，幸存者的位置为 Pn（为了便于理解，编号从 1 开始）。

易知，初始位置为 k 的人会被第一个杀掉。此时，经过重新排序之后，问题变成了 n-1 个人的情形。幸存者的位置为 Pn-1。如果能够找到从 Pn 到 Pn-1 的递推关系，那么问题就解决了。

重新编号后，上一轮相对这一轮每个人位置关系映射为：

1 -> n-k+1
2 -> n-k+2
…
k-1 -> n-1
k+1 -> 1

…

Pn -> Pn-1

…
n-1 -> n-k+1
n -> n-k

这样，我们就得到一个递推关系式：Pn = (Pn-1 + k) % n，初始条件 P1 = 1

（1 个人时幸存者为自己），当然该提递推公式同样适用于 n < k 的情况。

编码实现

约瑟夫环递推实现：

function josephus($n, $e)
{
    $idx = 0;
    for ($i = 2; $i <= $n; $i ++) {
        $idx = ($idx + $e) % $i;
    }
    return $idx;
}

接收标准输入处理并输出结果：

$input = str_replace(' ', '&', $input);
parse_str($input, $arr);
echo josephus($arr['n'], $arr['e']), PHP_EOL;

总结

由于本题只是需要求出最终的幸存者编号，所以可以直接使用递推公式求解，算法时间复杂度为 O(n)。若需要模拟整个游戏过程，则需要使用 链表 模拟实现。