структуры данных-Головоломка

Вокруг стола сидят 5 человек. Ключевым значением является количество участников, сидящих за столом. Итак, теперь ключевое значение будет 5. Террорист сказал участникам, что, поскольку вас 5 участников, я буду считать с первого участника, а человек, который насчитал 5, будет застрелен. Он считает, и 5-й человек умирает. Он снова считает до пяти, и 1-й человек умирает. Он снова считает, и 3-й человек умирает, и теперь остаются 2 и 4. Он считает, что нет между ними, наконец, 4 будет засчитано как 5, и он будет застрелен. Последним оставшимся человеком будет 2.

Точно так же, если попробовать для семи человек, ответ будет 8. А для 8 человек ответ будет 4.

Как установить формулу для этого, чтобы компьютер мог правильно снимать человека.

Я предполагаю, что это может быть круговой связанный список, когда членам присваивается значение токена. Но я не мог прийти к уравнению. Таким образом, присвоив значение ключа, будет определен человек, который будет жить.


person spandana    schedule 25.05.2011    source источник
comment
Это называется проблемой Иосифа Флавия: en.wikipedia.org/wiki/Josephus_problem   -  person Mitch Wheat    schedule 25.05.2011
comment
@Mitch Wheat: это должно быть ответом, поскольку вы указываете на соответствующую информацию.   -  person Benoit    schedule 25.05.2011
comment
@Mitch Wheat: Спасибо, что дали мне правильную ссылку для изучения.   -  person spandana    schedule 25.05.2011
comment
Так как есть довольно много людей, для которых теракты — это больше реальность, чем математическая головоломка, я настоятельно рекомендую изменить здесь терминологию. Даже в исходной задаче Иосифа Флавия говорится о самоубийстве.   -  person davka    schedule 25.05.2011


Ответы (3)


Это хорошо известная проблема, называемая проблемой Иосифа Флавия. Проверьте википедию и mathworld для возможного решения. И вы можете использовать Google для многочисленных статей об этом.

person taskinoor    schedule 25.05.2011

Это называется проблемой Иосифа.

person Mitch Wheat    schedule 25.05.2011

это классическая задача, называемая задачей Иосифа Флавия. имеет рекурсивное решение:

Дж (1) = 1 ; это основа

когда n четно J(2n) = 2J(n) - 1

когда n нечетно J(2n + 1) = 2J(n) + 1

person Mushrit Shabnam    schedule 05.03.2015