约瑟夫环php实现
约瑟夫环问题简介
约瑟夫环是一个经典的数学问题：n个人围成一圈，从某个指定的人开始报数，数到k的人出列，接着从下一个人重新开始报数，直到所有人出列。需确定出列顺序或最后幸存者的位置。
PHP实现方法
方法1：数组模拟
通过循环数组模拟报数过程，逐个移除元素：
function josephusArray($n, $k) {
$people = range(1, $n);
$result = [];
$index = 0;
while (!empty($people)) {
$index = ($index + $k - 1) % count($people);
$result[] = $people[$index];
array_splice($people, $index, 1);
}
return $result;
}
// 示例：5个人，数到3出列
print_r(josephusArray(5, 3));方法2：数学递归
利用递归公式计算幸存者位置（仅返回最后幸存者）：
function josephusMath($n, $k) {
if ($n == 1) {
return 1;
} else {
return (josephusMath($n - 1, $k) + $k - 1) % $n + 1;
}
}
// 示例：5个人中最后幸存者的初始位置
echo josephusMath(5, 3); // 输出4方法3：迭代优化
将递归转为迭代以提高效率：
function josephusIterative($n, $k) {
$result = 0;
for ($i = 2; $i <= $n; $i++) {
$result = ($result + $k) % $i;
}
return $result + 1;
}
// 示例：41个人，数到3时最后幸存者
echo josephusIterative(41, 3); // 输出31注意事项
- 数组模拟法直观但时间复杂度为O(n²)，适合小规模数据。
- 数学方法效率为O(n)，适合大规模计算，但仅返回最后幸存者。
- 参数
$n和$k需为正整数，否则需添加校验逻辑。
可根据实际需求选择实现方式。
