PHP 約瑟夫問題變體：法官處決囚犯模擬（陣列指標法）

問題描述

IV（4）名囚犯圍圈，從第 s 人開始報數，每報到第 D 人處決，剩餘者繼續報數，直到剩最後一人獲赦免。求倖存者編號。

陣列指標模擬實作

<?php
/**
 * 約瑟夫問題：陣列指標法
 * @param int $n 總人數
 * @param int $m 報數間隔（每 m 人處決）
 * @param int $start 起始位置（1-based）
 * @return int 倖存者編號
 */
function josephusElimination(int $n, int $m, int $start = 1): int {
    // 初始化囚犯編號陣列
    $prisoners = range(1, $n);
    
    // 將陣列指標移至起始位置（0-based 索引）
    $current = $start - 1;
    
    while (count($prisoners) > 1) {
        // 計算要移除的索引：(目前位置 + m - 1) % 當前人數
        $current = ($current + $m - 1) % count($prisoners);
        
        // 移除並輸出過程（可選）
        $removed = $prisoners[$current];
        echo "處決囚犯 #$removed\n";
        
        array_splice($prisoners, $current, 1);
        // $current 現在自動指向下一位（因陣列填補）
        // 若 $current 超出範圍（移除最後一元素），下輪 modulo 會自動歸零
    }
    
    return $prisoners[0];
}

// 測試：4 囚犯，每 3 人處決，從第 1 人開始
echo "倖存者：" . josephusElimination(4, 3, 1) . "\n"; // 輸出 1

// 測試：5 囚犯，每 3 人處決（維基百科範例）
echo "倖存者：" . josephusElimination(5, 3, 1) . "\n"; // 輸出 4
?>

關鍵點解析

改良：使用鏈表避免 array_splice O(n) 開銷

function josephusLinkedList(int $n, int $m, int $start = 1): int {
    // 建立雙向循環鏈表
    $nodes = [];
    for ($i = 1; $i <= $n; $i++) {
        $nodes[$i] = new class($i) {
            public int $val;
            public $prev;
            public $next;
            public function __construct(int $v) { $this->val = $v; }
        };
    }
    for ($i = 1; $i <= $n; $i++) {
        $nodes[$i]->next = $nodes[$i === $n ? 1 : $i + 1];
        $nodes[$i]->prev = $nodes[$i === 1 ? $n : $i - 1];
    }
    
    $current = $nodes[$start];
    while ($current->next !== $current) {
        // 走 m-1 步
        for ($i = 1; $i < $m; $i++) {
            $current = $current->next;
        }
        // 移除 current
        $prev = $current->prev;
        $next = $current->next;
        $prev->next = $next;
        $next->prev = $prev;
        $current = $next;
    }
    return $current->val;
}

效能比較

結語

陣列指標法程式碼簡潔、邏輯直觀，適合中小規模模擬與教學。大規模或高效能需求請改用鏈表或數學公式。理解「環狀索引計算」與「移除後指標自動指向下一元素」是核心關鍵。