約瑟夫環是一個著名的數學應用問題:n 個人圍成一圈,從第 1 人開始報數,報到 m 的人出列,剩下的人繼續從 1 報數,直到剩下最後一人。本文提供 PHP 實現並分析算法邏輯。
m、出列間隔 nn 移除當前元素,否則移至隊尾<?php
function king($m, $n) {
// 初始化猴子編號數組 1..m
$arr = range(1, $m);
$i = 0; // 數組指針
while (count($arr) > 1) {
// 判斷是否為出列位置
if (($i + 1) % $n == 0) {
unset($arr[$i]); // 出列
} else {
// 非出列:移至數組末尾
array_push($arr, $arr[$i]);
unset($arr[$i]); // 刪除原位置
}
$i++;
}
// 重置鍵名並返回
return array_values($arr);
}
// 測試:100 只猴子,每 5 只出列一只
var_dump(king(100, 5));
?>
以 m=5, n=2 為例:
初始: [1, 2, 3, 4, 5]
i=0: 1 不出列 -> [2, 3, 4, 5, 1]
i=1: 2 出列 -> [3, 4, 5, 1]
i=2: 4 不出列 -> [5, 1, 3, 4] (注意:i 指向原數組位置,unset 後後續元素前移)
i=3: 1 出列 -> [5, 3, 4]
i=4: 3 不出列 -> [4, 5, 3]
... 最終剩餘: 3
| 指標 | 數值 | 說明 |
|---|---|---|
| 時間複雜度 | O(m×n) | 每次出列需遍歷約 n 個元素 |
| 空間複雜度 | O(m) | 存儲 m 個元素的數組 |
| 適用規模 | m < 10,000 | 大數據量建議數學公式法 |