当前位置：首页 > PHP

php实现约瑟夫环

2026-02-15 21:55:25PHP

约瑟夫环问题简介

约瑟夫环问题是一个经典的数学问题，描述为：N个人围成一圈，从某个指定的人开始报数，数到第M个人就将其淘汰，然后从下一个人重新开始报数，直到所有人都被淘汰。求最后剩下的人的初始位置。

PHP实现约瑟夫环的代码

以下是使用PHP实现约瑟夫环问题的代码示例：

<?php
function josephus($n, $m) {
    $people = range(1, $n); // 创建一个包含1到n的数组
    $index = 0; // 当前报数的起始位置

    while (count($people) > 1) {
        $index = ($index + $m - 1) % count($people); // 计算淘汰的位置
        array_splice($people, $index, 1); // 移除被淘汰的人
    }

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

// 示例：10个人，每数到3淘汰一人
echo josephus(10, 3); // 输出结果为4
?>

代码解析

range(1, $n) 生成一个从1到N的数组，表示初始的N个人。
$index 用于跟踪当前报数的起始位置。
($index + $m - 1) % count($people) 计算被淘汰的人的位置，取模是为了处理环形结构。
array_splice($people, $index, 1) 从数组中移除被淘汰的人。

数学公式优化

对于较大的N和M，可以使用数学公式优化计算，避免循环操作。约瑟夫环问题的数学解为：

[ J(n, m) = (J(n-1, m) + m) \mod n ]

其中，( J(1, m) = 0 )。以下是递归实现的PHP代码：

<?php
function josephusMath($n, $m) {
    if ($n == 1) {
        return 0;
    } else {
        return (josephusMath($n - 1, $m) + $m) % $n;
    }
}

// 示例：10个人，每数到3淘汰一人
echo josephusMath(10, 3) + 1; // 输出结果为4
?>