PHP 解決约瑟夫环问题：猴子選大王算法實現與優化

PHP 解決约瑟夫环問題：猴子選大王算法實現與優化

經典問題：n 只猴子圍圈，從 1 開始報數，報到 m 的出列，剩下最後一只為王。即 Josephus Problem。提供模擬法與數學遞推法兩種解法。

模擬法 (隊列/陣列)

function josephusSim(int $n, int $m): int {
    $monkeys = range(1, $n);
    $idx = 0;
    while (count($monkeys) > 1) {
        $idx = ($idx + $m - 1) % count($monkeys);
        array_splice($monkeys, $idx, 1);
    }
    return $monkeys[0];
}

數學遞推法 O(n) 時間 O(1) 空間 (最優)

function josephusMath(int $n, int $m): int {
    $pos = 0; // 只剩 1 只時位置為 0 (0-based)
    for ($i = 2; $i <= $n; $i++) {
        $pos = ($pos + $m) % $i;
    }
    return $pos + 1; // 轉 1-based 編號
}

// 測試
echo josephusMath(100, 5); // 43
echo josephusSim(100, 5);  // 43

遞推公式推導

設 f(n,m) 為 n 人報 m 出列最後贏家的 0-based 索引。
第一輪第 (m-1)%n 人出列，剩 n-1 人，下一輪從原 (m)%n 開始。
新編號與原編號映射：old = (new + m) % n。
遞推：f(1,m)=0; f(i,m) = (f(i-1,m) + m) % i。

效能對比 (n=1,000,000)

// 模擬法: ~2.5s (大量 array_splice 移動元素)
// 數學法:  ~0.003s (單純迴圈運算)

擴展：輸出完整出列順序

function josephusOrder(int $n, int $m): array {
    $circle = range(1, $n);
    $order = [];
    $idx = 0;
    while ($circle) {
        $idx = ($idx + $m - 1) % count($circle);
        $order[] = $circle[$idx];
        array_splice($circle, $idx, 1);
    }
    return $order;
}
print_r(josephusOrder(10, 3));
// [3, 6, 9, 2, 7, 1, 8, 5, 4, 10] 最後 10 為王