萬盛學電腦網

您现在的位置: 萬盛學電腦網 >> 程式設計 >  >> 網路程式設計 >> PHP 程式設計

PHP 實現约瑟夫环問題:猴子選大王算法詳解

經典算法問題的 PHP 實現:約瑟夫環(猴子選大王)

約瑟夫環是一個著名的數學應用問題:n 個人圍成一圈,從第 1 人開始報數,報到 m 的人出列,剩下的人繼續從 1 報數,直到剩下最後一人。本文提供 PHP 實現並分析算法邏輯。

問題形式化描述

  • 輸入:總人數 m、出列間隔 n
  • 過程:循環遍歷,計數器達到 n 移除當前元素,否則移至隊尾
  • 輸出:最後剩餘元素的原始編號

PHP 實現代碼

<?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(n) 時間)

遞推公式:f(1) = 0; f(i) = (f(i-1) + n) % i,最終結果 +1 轉為 1 基礎編號:

<?php
function josephus_math($m, $n) {
    $result = 0;
    for ($i = 2; $i <= $m; $i++) {
        $result = ($result + $n) % $i;
    }
    return $result + 1; // 轉為 1-based 編號
}

// 驗證
var_dump(josephus_math(100, 5)); // 與模擬法結果一致,但極快
?>

擴展應用

此算法廣泛應用於:負載均衡輪詢、分佈式系統領導者選舉、遊戲邏輯、密碼學、圓形數據結構處理等領域。

copyright © 萬盛學電腦網 all rights reserved
指標數值說明
時間複雜度O(m×n)每次出列需遍歷約 n 個元素
空間複雜度O(m)存儲 m 個元素的數組
適用規模m < 10,000大數據量建議數學公式法