gpt4 book ai didi

php - PHP 中的求解算法(Josephus 置换)

转载 作者:塔克拉玛干 更新时间:2023-11-03 04:17:58 28 4
gpt4 key购买 nike

假设 100 人围成一圈。从第 1 人数到第 14 人,将此人移出圈子。按照数数顺序,再次数数,去掉第 14 个人。重复。最后站着的是谁?

我已经尝试了一切来解决这个问题,但它似乎无法处理死循环。

<?php
//init array
$array = array();
for ($i = 0; $i < 100; $i++) { $array[] = $i; }

//start from 0
$pos = 0;
while (count_not_null($array) > 1) {
//reset count
$count = 0;
while (true) {
//ignore NULL for count, that position is already removed
if ($array[$pos] !== NULL) {
$count++;
if($count == 14) { break; }
}
$pos++;
//go back to beginning, we cant go over 0-99, for 100 elements
if ($pos > 99) { $pos = 0; }
}
echo "set index {$pos} to NULL!" ."<br>";
$array[$pos] = NULL;
if (count_not_null($array) === 1) { break; }
}

echo "<pre>";
print_r($array);
echo "</pre>";


//counting not null elements
function count_not_null($array) {
$count = 0;
for ($i = 0; $i < count($array); $i++) {
if ($array[$i] !== NULL) { $count++; }
}
return $count;
}
?>

最佳答案

为了用尽可能少的代码和最快的速度解决这个问题,你可以这样做:

function josephus($n,$k){
if($n ==1)
return 1;
else
return (josephus($n-1,$k)+$k-1) % $n+1;
}

echo josephus(100,14);

这里我们使用的是递归语句,因为你要解决的问题可以用这个数学语句定义 f(n,k) = (f(n-1,k) + k) % n
要阅读有关此数学公式的更多信息,您可以查看它 here on the wiki page .

关于php - PHP 中的求解算法(Josephus 置换),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/34166455/

28 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com