萬盛學電腦網

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

PHP 實作約瑟夫問題的兩種經典解法詳解

前言

約瑟夫問題是一個經典的數學與程式設計課題,描述一群人圍成一圈,按特定規則依次淘汰,最終剩下最後一位「大王」。本文將介紹兩種常見的 PHP 實作方式:數學推導法與陣列模擬法,並提供完整程式碼供參考。

問題描述

假設有 n 隻猴子圍成一圈,編號 1 到 n。從第 1 隻開始報數,數到第 m 隻時將其踢出圈,從下一隻繼續報數,重複此過程直到只剩一隻猴子,該猴子即為猴王。輸入 m、n,輸出最後猴王的編號。

解法一:數學遞推公式(最佳效能)

利用約瑟夫環的數學特性,可推導出遞推公式:f(1) = 0; f(i) = (f(i-1) + m) % i,最終結果為 f(n) + 1。此法時間複雜度 O(n),空間複雜度 O(1),極為高效。

程式碼實作

<?php
function getLeader($n, $m) {
    $res = 0;
    for ($i = 2; $i <= $n; $i++) {
        $res = ($res + $m) % $i;
    }
    return $res + 1;
}

$leader = getLeader(13, 34);
echo $leader; // 輸出猴王編號
?>

解法二:陣列模擬法(直觀易懂)

直接模擬淘汰過程:建立猴子編號陣列,透過遞迴或迴圈依序移除第 m 個元素,直到陣列剩下一個元素。雖時間複雜度較高(O(n*m)),但邏輯清晰,適合教學示範。

程式碼實作

<?php
function getKing($monkeys, $m, $current = 0) {
    $number = count($monkeys);
    if ($number == 1) {
        echo '<font color="red">編號為 ' . $monkeys[0] . ' 的猴子成為猴王了!</font>';
        return;
    }
    $num = 1;
    while ($num++ < $m) {
        $current++;
        $current = $current % $number;
    }
    echo "編號為 " . $monkeys[$current] . " 的猴子被踢掉了...<br/>";
    array_splice($monkeys, $current, 1);
    getKing($monkeys, $m, $current);
}

$n = 13;
$m = 34;
$monkeys = range(1, $n);
getKing($monkeys, $m);
?>

總結

兩種方法各有優劣:數學法效能極佳,適合大數據量;模擬法直觀易懂,適合理解問題本質。實際開發中可根據需求選擇。

copyright © 萬盛學電腦網 all rights reserved