PHP實現約瑟夫環問題：循環鏈表與數學推導兩種解法

約瑟夫問題：從「處死犯人」到經典算法模型

約瑟夫環（Josephus Problem）描述：n 個人圍成一圈，從第 s 人開始報數，數到 m 的人出列，下一人繼續從 1 報數，循環直到剩最後一人。求最後倖存者的原始編號。

解法一：模擬循環陣列（直觀易懂）

<?php
function josephusSimulation(int $n, int $m, int $start = 1): int {
    $people = range(1, $n);
    $idx = $start - 1; // 0-based
    while (count($people) > 1) {
        $idx = ($idx + $m - 1) % count($people);
        array_splice($people, $idx, 1);
    }
    return $people[0];
}
echo josephusSimulation(5, 3); // 輸出 4

解法二：數學遞推公式（O(n) 時間 O(1) 空間）

設 f(n, m) 為 n 人報數 m 時的倖存者編號（0-based）。首輪淘汰第 (m-1)%n 人，問題縮減為 n-1 人，但起始位置偏移。遞推關係：

f(1, m) = 0
f(i, m) = (f(i-1, m) + m) % i   (i = 2..n)

最終答案為 f(n, m) + 1（轉 1-based）。

<?php
function josephusMath(int $n, int $m): int {
    $res = 0;
    for ($i = 2; $i <= $n; $i++) {
        $res = ($res + $m) % $i;
    }
    return $res + 1;
}
echo josephusMath(13, 34); // 輸出 10

解法三：遞歸模擬（教學演示用）

<?php
function josephusRecursive(array $people, int $m, int $start = 0): int {
    if (count($people) === 1) return $people[0];
    $kill = ($start + $m - 1) % count($people);
    $next = $kill % (count($people) - 1); // 下一輪起始索引
    $newPeople = array_merge(
        array_slice($people, $kill + 1),
        array_slice($people, 0, $kill)
    );
    return josephusRecursive($newPeople, $m, $next);
}
$monkeys = range(1, 13);
echo josephusRecursive($monkeys, 34);

複雜度對比與選型建議

實際開發中，數學遞推法是首選；若需記錄完整淘汰序列，可用雙向循環鏈表優化模擬至 O(n log n)。