Задача Иосифа Флавия

Рассмотрим ещё два способа решения задачи, не опирающихся на приведенную выше формулу. Несмотря на то, что они сложнее для вычисления в плане вычислительной скорости, все же, алгоритм более нагляден. Давайте повторим в ОЗУ события, происходившие в легенде.

Будем хранить в массиве имена (то есть номера) всех живых на текущий момент воинов. Причем удобно, чтобы номера людей были записаны в элементах массива с 0 по N — 1 (это свойство будет использоваться для операции взятия остатка). Когда воин будет умирать, будем удалять его из массива, и тех, кто стоял за ним, «сдвигать» на один элемент влево.

Заметим, что если мы уже убили L человек, то в живых осталось M = N — L. Пусть мы только что (на L-ом шаге) убили человека, который был записан в нашем массиве в элементе с номером j (и сдвинули людей, которые были записаны в массиве в элементах с j + 1 по M на один элемент влево). Тогда следующим нужно убивать человека, который записан в этом массиве в элементе с номером (j + k — 1) % M.

Заведем массив, где будем помечать мертвых воинов (то есть в i-м элементе хранится, жив воин i, или уже нет). Пусть у нас на текущем шаге M живых людей и на предыдущем шаге умер воин j. Чтобы найти следующего, будем бежать по массиву, отсчитывая живых и пропуская мертвых. Тот человек, на котором мы насчитаем k % M и должен умереть следующим. Через N — 1 шаг останется один человек.

Простейшее моделирование будет работать O (${\displaystyle N^{2}}$). Используя дерево отрезков, можно произвести моделирование за ${\displaystyle O(NlogN)}$. Однако попытаемся найти закономерность, выражающую ответ для задачи (N,K) через решение предыдущих задач. С помощью моделирования построим таблицу значений, скажем, приведенную ниже.

И здесь достаточно отчётливо видна следующая закономерность:

 joseph (n, k) = ( joseph (n-1, k) + k - 1 ) % n + 1;
 joseph (1, k) = 1

(здесь индексация с единицы несколько портит элегантность формулы)

Итак, мы нашли решение задачи Иосифа Флавия, работающее за ${\displaystyle O(N)}$ итераций.

С целью подробного объяснения возможных ситуаций, которые могут возникнуть в ходе решения, упростим исходную задачу и рассмотрим случай № 1, причем, уменьшим круг солдат с сорока одного (сорок солдат и Иосиф) до десяти и предположим, что вместо каждого третьего солдата должен умереть каждый второй. В результате будем рассматривать круг солдат, изображенный на рис 1.

Рис 1. Круг из 10 солдат, в котором
должен «умереть» каждый второй

Если производить отсчет от 1-го солдата в круге, то порядок удаления будет следующим: 2, 4, 6, 8, 10, 3, 7, 1, 9. Солдат под номером 5 — в конечном итоге остается в живых.

Этапы «уничтожения» солдат из круга графически представлены на рис 2 — 4.

Рис 2. 1-й этап удаления	Рис 3. 2-й этап удаления	Рис 4. 3-й этап удаления

Рассмотрим конкретную ситуацию и определим результаты, используя предопределенные условия. Задача состоит в том, чтобы установить зависимости между параметрами k, n (где n — это количество людей в круге, k — служит для определения каждого k-го солдата для «исключения» из круга), и решить задачу независимо от того, сколько солдат стоят в круге. Попробуем вывести общие формулы для решения задачи с любыми входными параметрами (на вход подаются значения k и n). Для этого определяем функцию F(n), где F(n) — возвращает номер победителя. Сразу возникает первое предположение, что F(n) может быть в пределах F(n) = n / 2, что верно при n = 10 или n = 2. Однако при n = 4 F(4) = 1, что доказывает неправильность рассуждений. Следующее замечание из рассмотренной выше ситуации: полученный результат — нечетный номер, независимо от значения n, так произошло вследствие того, что в ходе 1-го этапа — были убраны все четные номера. Также следует учесть тот факт, что при n = 1 F(1) = 1. Предположив, что на входе солдат = 2n. То, что остается после 1-го этапа показано на рис. 5.

Рис. 5 — 1-й этап при количестве солдат в круге 2n

Наблюдается аналогичная ситуация и при 2n − 1 — солдатах на входе (рис.6). Однако вводится поправка- уменьшение на единицу и увеличение F(n) в 2 раза.

Рис. 6. солдат в круге 2n — 1

Из чего можно вывести формулу F(2n) = 2 F(n) − 1 (для всех n > 1). Рассмотрим случай № 2, приняв во внимание тот факт, что на вход подаются 2n + 1 число солдат (то есть нечетное количество солдат). После проведения 1-го этапа «исключения» солдат из круга получится нечто, приведенное на рис.7.

Рис. 7 — 1-й этап при количестве солдат в круге 2n + 1

Из чего можно вывести формулу F(2n +1) = 2 F(n) + 1 (для всех n > 1). Сведем все рассмотренные ситуации и запишем все случаи в виде системы, позволяющей определить значение функции F(n) — для любых значений n:

Выведенные выше формулы могут быть применены и для решения исходной задачи — Иосифа Флавия. А именно: F(2^m + k) = 2k + 1 для любого m любого k.

Рассмотрим двоичные представлениям величин n и F(n): ${\displaystyle n=b_{m}\cdot 2^{m}+b_{m-1}\cdot 2^{m-1}+...+b_{1}\cdot 2+b_{0}}$, где каждое ${\displaystyle b_{i}}$ равно 0 или 1, причем старший бит ${\displaystyle b_{m}}$ равен 1. Вспоминая, что ${\displaystyle n=2^{m}+k}$, последовательно получаем:

${\displaystyle n=(1\,b_{m-1}...b_{1}b_{0})_{2}}$

${\displaystyle k=(0\,b_{m-1}...b_{1}b_{0})_{2}}$

(так как ${\displaystyle k=n-2^{m}=2^{m}+b_{m-1}\cdot 2^{m-1}+\ldots +b_{1}\cdot 2+b_{0}-2^{m}=0\cdot 2^{m}+b_{m-1}\cdot 2^{m-1}+\ldots +b_{1}\cdot 2+b_{0}}$)

${\displaystyle 2k=(b_{m-1}\ldots b_{1}b_{0}0)_{2}}$

(так как ${\displaystyle 2k=2(b_{m-1}\cdot 2^{m-1}+b_{m-2}\cdot 2^{m-2}+\ldots +b_{1}\cdot 2+b_{0})=b_{m-1}\cdot 2^{m}+b_{m-2}\cdot 2^{m-1}+\ldots +b_{1}\cdot 2^{2}+b_{0}\cdot 2+0}$)

${\displaystyle 2k+1=(b_{m-1}\ldots b_{1}b_{0}1)_{2}}$

${\displaystyle F(n)=(b_{m-1}\ldots b_{1}b_{0}b_{m})_{2}}$

(так как ${\displaystyle F(n)=2k+1}$ и ${\displaystyle b_{m}=1}$)
Таким образом, мы получили, что

${\displaystyle F((b_{m}b_{m-1}\ldots b_{1}b_{0})_{2})=(b_{m-1}\ldots b_{1}b_{0}b_{m})_{2}}$,

то есть F(n) получается путём циклического сдвига двоичного представления n влево на одну позицию.