Начнем с описания проблемы Иосифа Флавия:

Люди стоят в кругу в ожидании казни. Подсчет начинается в указанной точке круга и продолжается по кругу в указанном направлении. После того, как указанное количество людей пропущено, выполняется следующий человек. Процедура повторяется с оставшимися людьми, начиная со следующего человека, идя в том же направлении и пропуская такое же количество людей, пока не останется только один человек, и его освободят.

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

Звучит довольно интересно, правда? Если бы вы оказались в этой ситуации, на каком месте вы бы сели?

Начнем с двух солдат, сидящих на двух стульях, в данном случае все довольно просто. Если мы начнем с солдата 1, то солдат 1 убивает солдата 2, и он выживает, поэтому в случае двух солдат стул 1 является самым безопасным.

Давайте расширим эту логику на 3 стула: солдат 1 убивает солдата 2, а солдат 3 убивает солдата 1. Стул 3 самый безопасный.

Это легко сделать для нескольких солдат, но когда количество солдат увеличивается, становится трудно рассчитать. Конечно, должен быть лучший подход, давайте нарисуем диаграмму, показывающую, кто выживает, исходя из количества солдат.

Здесь есть интересное наблюдение: на каждое 2 ^ n-е место всегда выигрывает 1, а для любого числа от 2 ^ n до 2 ^ (n + 1) победителями являются просто последовательные нечетные числа. Здесь у нас есть закономерность.

Для данной конфигурации X солдат найдите ближайшее 2 ^ n, которое меньше X. Тогда самое безопасное место - 2 * [X - (2 ^ n)] + 1. Здесь мы находим ближайшее число 2 ^ n и перескакиваем через это количество чисел по шкале нечетных чисел.

Возьмем пример: для X = 5 ближайшее (2 ^ n) равно 4, что составляет 2², поэтому
2 * [5–2²] + 1 равно 3. Это правильный ответ.

Вот и все, теперь вы знаете, какое место выбрать, если вы когда-нибудь столкнетесь с такой ситуацией. Выбирайте с умом 😉.

Но это не весело. Было бы здорово смоделировать весь процесс, верно? Давайте сделаем это.

Мы будем использовать p5.js, чтобы смоделировать это с помощью JavaScript (почему именно JavaScript, вы спрашиваете? Прочтите мою биографию).

Мы можем разделить проект на два основных блока:

  1. Класс солдата, который умеет рисовать себя на экране, менять состояние с живого на мертвое и убивать другого солдата.
  2. Фактический алгоритм, запускающий моделирование.

Вот как будет выглядеть класс солдата:

Теперь, когда мы разошлись с классом солдат, давайте посмотрим, как работает основной алгоритм.

Сохраним всех пользователей в круговом массиве, класс солдата имеет две статические переменные, в которых хранится общее количество солдат и количество живых солдат.

p5.js имеет две критические функции setup и draw. В функции настройки мы инициализируем координаты для всех объектов-солдат. Эти объекты солдат должны быть нарисованы по кругу, каждый солдат имеет значения x и y, они определяют, где солдат будет нарисован на экране.

Нам нужно рисовать точки по кругу.

Каждая точка в круге представляет солдата. r - это расстояние, на котором солдат будет размещен от центра круга. Располагаем всех солдат на равном расстоянии по окружности круга.

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

360 / numberOfSoldiers;

Здесь numberOfSoldiers - это произвольная константа, которую мы установили в начале моделирования, ее можно изменить, чтобы найти решения для различных значений n..

Делим 360⁰ на равные углы и наносим их на окружность.

Теперь к заключительной части моделирования, основному алгоритму моделирования:

  1. Убедитесь, что количество живых солдат равно 1, если да, то его место является самым безопасным, завершите симуляцию.
  2. Если количество живых солдат больше 1, тогда найдите живого солдата и сохраните номер его места, давайте назовем это prevIndex, теперь пройдемся по массиву и найдем следующего живого солдата, давайте сохраним номер его места как currentIndex, теперь солдат в prevIndex убивает солдата в currentIndex. Во время итерации по массиву убедитесь, что вы учитываете переполнение индекса, реализуя круговой массив.
  3. Перейти к шагу 1

Вот как выглядит окончательный результат -

Посмотрите код на github (просмотр).

PS: Это не лучший способ написать алгоритм моделирования, но он работает!