PHP 解決約瑟夫環問題：數學公式法與模擬法完整比較

問題定義

n 人圍圈（編號 1~n），從第 1 人報數，每數到 m 者出列，下一人從 1 重新報數，循環至剩最後一人。求倖存者編號。

方法一：數學遞推公式（O(n) 時間、O(1) 空間）

遞推關係：f(1) = 0; f(i) = (f(i-1) + m) % i，最終答案 f(n) + 1（轉 1-based）。

<?php
function josephusMath(int $n, int $m): int {
    $result = 0; // f(1) = 0 (0-based)
    for ($i = 2; $i <= $n; $i++) {
        $result = ($result + $m) % $i;
    }
    return $result + 1; // 轉 1-based
}

// 測試
echo "n=13, m=34 => 倖存者：" . josephusMath(13, 34) . "\n"; // 輸出 10
echo "n=5, m=3 => 倖存者：" . josephusMath(5, 3) . "\n";     // 輸出 4
echo "n=41, m=3 => 倖存者：" . josephusMath(41, 3) . "\n";   // 輸出 31 (歷史典故)
?>

方法二：陣列模擬法（直觀、可視化過程）

<?php
function josephusSimulate(int $n, int $m, bool $verbose = false): int {
    $people = range(1, $n);
    $index = 0; // 當前報數起始位置
    
    while (count($people) > 1) {
        // 計算要移除的索引：(目前位置 + m - 1) % 當前人數
        $index = ($index + $m - 1) % count($people);
        $removed = $people[$index];
        
        if ($verbose) {
            echo "移除：$removed (剩餘：" . implode(', ', $people) . ")\n";
        }
        
        array_splice($people, $index, 1);
        // $index 已指向下一人，無需調整
    }
    
    return $people[0];
}

// 測試
echo "模擬法 n=13, m=34 => " . josephusSimulate(13, 34) . "\n";
echo "模擬法 n=5, m=3 (詳細)：\n";
josephusSimulate(5, 3, true);
?>

方法三：鏈表模擬（大 n 時較陣列快）

<?php
class Node {
    public int $val;
    public Node $next;
    public function __construct(int $val) { $this->val = $val; }
}

function josephusLinkedList(int $n, int $m): int {
    // 建立循環鏈表
    $head = new Node(1);
    $prev = $head;
    for ($i = 2; $i <= $n; $i++) {
        $node = new Node($i);
        $prev->next = $node;
        $prev = $node;
    }
    $prev->next = $head; // 閉環
    
    $current = $head;
    $prev = $prev; // 尾節點
    
    while ($current->next !== $current) {
        // 走 m-1 步
        for ($i = 1; $i < $m; $i++) {
            $prev = $current;
            $current = $current->next;
        }
        // 移除 current
        $prev->next = $current->next;
        $current = $prev->next;
    }
    
    return $current->val;
}
?>

效能比較

變體：指定起始位置 k

function josephusWithStart(int $n, int $m, int $k): int {
    // k: 1-based 起始位置
    $mathResult = josephusMath($n, $m); // 從 1 開始的結果
    // 旋轉調整
    return (($mathResult - 1 + $k - 1) % $n) + 1;
}

結語

約瑟夫環是經典演算法題。僅需結果用數學公式法（O(n)）；需展示過程用陣列模擬（直觀）或鏈表（較大 n）。理解遞推公式推導過程有助於掌握動態規劃與模運算思維。