datastructures-головоломка

Question

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

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

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

Answer 1

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

Answer 2

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

Answer 3

это классическая проблема под названием проблема Иосифа.имеет рекурсивное решение:

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

, когда n является четным J (2n) = 2J (n) - 1

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