Алгоритм решения (перестановка Джозефуса) в переполнении стека

Question

Алгоритм решения (перестановка Джозефуса) в переполнении стека

Предположим, 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;
}
?>

1

algorithm josephus php

Решение

Другие решения

Проблема в том, что в то время как цикл

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

Поскольку вы увеличиваете $ pos, даже если счетчик равен 14, вы получите неправильные значения и зациклились навсегда. Замените это на это:

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

Также сравнение 0 с NULL не даст ожидаемых результатов, как упомянуто @Barmar, поэтому вы можете либо изменить сравнение NULL, либо начать отсчет с 1

ПРИМЕЧАНИЕ: это было бы намного быстрее, если бы вы не проходили через массив каждый раз: D рассмотрите возможность использования переменной для подсчета оставшихся элементов

2

Источник

Accepted Answer

Чтобы решить эту проблему с помощью как можно меньшего количества кода и как можно быстрее, вы можете сделать так:

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
Чтобы узнать больше об этой математической формуле, вы можете увидеть ее здесь на странице вики.

3