PHP百题：PHP实现约瑟夫环问题完整代码-php教程-PHP中文网

约瑟夫环问题有数组模拟和递推公式两种php解法：前者直观易懂，用range和array_splice模拟淘汰过程；后者高效o(n)，基于f(n)=(f(n−1)+m)%n递推并+1转为1-based编号；还可扩展返回完整淘汰顺序。

php百题：php实现约瑟夫环问题完整代码

约瑟夫环（Josephus Problem）是一个经典的数学与算法问题：n个人围成一圈，从第1个人开始报数，每报到第m个人就将其淘汰，接着从下一个人重新开始报数，直到剩下最后一个人。PHP可以通过数组模拟或数学递推两种方式实现，下面给出清晰、可运行、带注释的完整代码，包含两种主流解法。

方法一：数组模拟（直观易懂，适合理解逻辑）

用PHP数组模拟环形结构，通过循环删除元素实现淘汰过程：

<?php function josephusArray($n, $m) {
    // 初始化编号为1~n的数组
    $people = range(1, $n);
    $index = 0; // 当前报数起始位置（0索引）
<pre class='brush:php;toolbar:false;'>while (count($people) > 1) {
    // 计算要删除的位置：(当前索引 + m - 1) % 当前人数
    $index = ($index + $m - 1) % count($people);
    array_splice($people, $index, 1); // 删除该位置的人
    // 注意：删除后数组自动前移，$index保持指向下一个报数起点，无需额外-1
}

return $people[0]; // 返回最后剩下的人的编号

}

btpanel phpsite 宝塔面板PHP网站

宝塔面板 PHP 网站管理：站点创建、删除、启停、PHP 版本切换、域名管理、SSL证书管理、伪静态管理、数据库管理

下载

// 示例：10人，每数到3淘汰一人 echo "数组模拟结果: " . josephusArray(10, 3) . "\n"; // 输出: 4 ?>

方法二：递推公式（高效，O(n)时间复杂度）

约瑟夫问题存在经典递推关系：
f(1) = 0
f(n) = (f(n−1) + m) % n （结果为0-based，最终+1转为1-based）
该公式避免数组操作，适合大数据量场景：

<?php function josephusRecurrence($n, $m) {
    $survivor = 0; // f(1) = 0
    for ($i = 2; $i <= $n; $i++) {
        $survivor = ($survivor + $m) % $i;
    }
    return $survivor + 1; // 转为1-based编号
}
<p>// 示例验证
echo "递推公式结果: " . josephusRecurrence(10, 3) . "\n"; // 输出: 4
?>

增强版：返回完整淘汰顺序（调试/教学更友好）

若需观察每轮淘汰过程（如教学演示），可扩展数组模拟法，记录淘汰序列：

<?php function josephusTrace($n, $m) {
    $people = range(1, $n);
    $index = 0;
    $eliminated = [];
<pre class='brush:php;toolbar:false;'>while (count($people) > 1) {
    $index = ($index + $m - 1) % count($people);
    $eliminated[] = $people[$index];
    array_splice($people, $index, 1);
}

return [
    'last' => $people[0],
    'sequence' => $eliminated
];

}

$result = josephusTrace(7, 3); echo "淘汰顺序: " . implode(', ', $result['sequence']) . "\n"; // 3, 6, 2, 7, 5, 1 echo "幸存者: " . $result['last'] . "\n"; // 4 ?>