1

假设 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;
}
?>
4

3 回答 3

4

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

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
要阅读有关此数学公式的更多信息，您可以在 wiki 页面上查看。

于 2015-12-08T22:19:32.650 回答
2

问题是这个while循环

    while ($count < 14) {
        if ($array[$pos] != NULL) {
            $count++;
        }
        $pos++;
        if ($pos > 99) { $pos = 0; }
    }

因为即使 count 为 14，您也会增加 $pos，您将以不正确的值结束并永远循环。用这个替换它：

    while (true) {
        if ($array[$pos] != NULL) {
            $count++;
            if($count == 14) {break;}
        }
        $pos++;
        if ($pos > 99) { $pos = 0; }
    }

此外，比较 0 和 NULL 不会给您@Barmar 提到的预期结果，因此您可以更改 NULL 比较，或从 1 开始计数

注意：如果您不每次都循环遍历数组，这会更快：D 考虑使用变量来计算剩余项目

于 2015-12-08T22:10:57.713 回答
0

任何再次偶然发现这一点的人，这里有一个稍微快一点的：

function josephus($n){
    $toBin = decbin($n); // to binary
    $toBack = substr($toBin,1) . "1"; // remove first bit and add to end
    return bindec($toBack); // back to value
}

基于此解决方案。

于 2020-01-20T12:16:55.050 回答