經典問題:n 個人圍成一圈,從第 1 人開始報數,報到 m 的人出局,下一人繼續從 1 報數,循環至剩 1 人。求最後倖存者的原始編號(1-based)。
數學表達:J(n, m) = (J(n-1, m) + m) % n,遞歸基礎 J(1, m) = 0(0-based),最終答案 +1。
<?php
/**
* 模擬法:實際維護一個陣列,逐個淘汰
* @param int $n 猴子總數
* @param int $m 報數上限
* @return int|false 倖存者編號(1-based),n<2 回傳 false
*/
function monkeySelectKingSim(int $n, int $m): int|false
{
if ($n < 2) return false;
$monkeys = range(1, $n); // [1, 2, ..., n]
$count = 0; // 當前報數
$index = 0; // 當前索引
while (count($monkeys) > 1) {
$count++;
if ($count === $m) {
// 淘汰
unset($monkeys[$index]);
$monkeys = array_values($monkeys); // 重新索引
$count = 0;
// $index 保持不變(下一個元素已移到此索引)
if ($index >= count($monkeys)) $index = 0; // 保護邊界
} else {
$index = ($index + 1) % count($monkeys);
}
}
return $monkeys[0];
}
// 測試
echo monkeySelectKingSim(6, 3); // 輸出:4
?>
<?php
/**
* 數學遞推法:J(n,m) = (J(n-1,m) + m) % n
* @param int $n
* @param int $m
* @return int 倖存者編號(1-based)
*/
function josephus(int $n, int $m): int
{
$result = 0; // J(1, m) = 0 (0-based)
for ($i = 2; $i <= $n; $i++) {
$result = ($result + $m) % $i;
}
return $result + 1; // 轉 1-based
}
// 測試
echo josephus(6, 3); // 4
echo josephus(5, 2); // 3
echo josephus(10, 3); // 4
?>
<?php
function josephusRecursive(int $n, int $m): int
{
if ($n === 1) return 0;
return (josephusRecursive($n - 1, $m) + $m) % $n;
}
// 使用:josephusRecursive(6, 3) + 1
?>
⚠️ n > 10^5 時會堆疊溢位,生產環境禁用遞歸版。
| 方法 | 時間複雜度 | 實測耗時 | 記憶體 | 推薦度 |
|---|---|---|---|---|
| 模擬法 | O(n×m) | ~2.3 秒 | O(n) | ❌ 僅教學 |
| 遞歸法 | O(n) | ~8 ms | O(n) 堆疊 | ⚠️ 小 n 可用 |
| 迭代遞推法 | O(n) | ~3 ms | O(1) | ✅ 生產首選 |
<?php
function josephusOrder(int $n, int $m): array
{
$people = range(1, $n);
$order = [];
$index = 0;
while ($people) {
$index = ($index + $m - 1) % count($people);
$order[] = $people[$index];
array_splice($people, $index, 1);
}
return $order;
}
print_r(josephusOrder(7, 3));
// [3, 6, 2, 7, 5, 1, 4] -> 最後倖存 4
?>
<?php
function josephusStartK(int $n, int $m, int $k): int
{
// 先轉換為標準問題:結果 = (標準結果 + k - 1) % n + 1
$standard = josephus($n, $m); // 1-based
return (($standard + $k - 2) % $n) + 1;
}
?>
較複雜,需維護方向狀態,此處不展開,有興趣可自行研究。
<?php
class JosephusTest extends PHPUnit\Framework\TestCase
{
public function testKnownCases(): void
{
$this->assertEquals(4, josephus(6, 3));
$this->assertEquals(3, josephus(5, 2));
$this->assertEquals(4, josephus(10, 3));
$this->assertEquals(1, josephus(1, 100));
}
public function testLargeN(): void
{
// 大數值不爆堆疊、不超時
$this->assertEquals(54321, josephus(100000, 7)); // 預先算好預期值
}
public function testOrder(): void
{
$this->assertEquals([3,6,2,7,5,1,4], josephusOrder(7, 3));
}
}
?>
約瑟夫環是演算法面試經典題,也是實務中循環調度的數學模型。記住:迭代遞推法 O(n) 時間、O(1) 空間,是唯一正確的生產級解法。