PHP中的求解算法（Josephus置换）

Question

Suppose 100 people line up in a circle. Counting from person 1 to person 14, remove person from the circle. Following the count order, counting again and remove the 14th person. Repeat. Who is the last person standing?

I've tried everything to solve this and it seems to not be working with dead loops.

<?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;
}
?>

Answer 1

For solving this with as little code as possible and quickest you could do like this:

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

echo josephus(100,14);

Here we are using an recursive statement instead, as what you are trying to solve can be defined by this mathematical statement f(n,k) = (f(n-1,k) + k) % n
For reading more about this mathematical formula you can see it here on the wiki page.