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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Задача Иосифа Флавия или считалка Джозефуса — известная математическая задача с историческим подтекстом.

Задача основана на легенде, что отряд Иосифа Флавия, защищавший город Йодфат, не пожелал сдаваться в плен блокировавшим пещеру превосходящими силам римлян. Воины, в составе сорока человек, стали по кругу и договорились, что каждые два воина будут убивать третьего, пока не погибнут все. При этом двое воинов, оставшихся последними в живых, должны были убить друг друга. Иосиф Флавий, командовавший этим отрядом, якобы быстро рассчитал, где нужно встать ему и его товарищу, чтобы остаться последними, но не для того, чтобы убить друг друга, а чтобы сдать крепость римлянам.

В современной формулировке задачи участвует n воинов, стоящих по кругу, и убивают каждого m-го. Требуется определить номер k начальной позиции воина, который останется последним.

Рекуррентные соотношения[править | править исходный текст]

Если известно решение задачи для некоторого числа воинов, то его можно использовать для решения задачи с на единицу большим числом воинов. Для m=2 имеем

 k(n)= \begin{cases} 1, & \mbox{if }n= 1 \\ 1+(k(n-1)+1) \mod {n}, & \mbox {if }n>1\end{cases}.

Для m=3 имеем

 k(n)= \begin{cases} 1, & \mbox{if }n= 1 \\ 1+(k(n-1)+2) \mod {n}, & \mbox {if }n>1\end{cases}.

Очевидно для общего случая будем иметь

 \forall m>0: k(n,m)= \begin{cases} 1, & \mbox{if }n= 1 \\ 1+(k(n-1,m)+m-1) \mod {n}, & \mbox {if }n>1\end{cases}.

Возможно построение рекуррентных соотношений, которые сходятся намного быстрее чем линейные. Вот пример решения задачи для m=2 с логарифмическим числом шагов рекурсии:

 
k(n)= \begin{cases} 
1, & \mbox{if }n= 1 \\ 
2k\left( \frac{n}{2} \right)-1, & \mbox{if }n>1\mbox{ is even} \\
2k\left( \frac{n-1}{2} \right)+1, & \mbox{if }n>1\mbox{ is odd}
\end{cases}
.

Замкнутая формула[править | править исходный текст]

При программировании приведенные выше рекуррентные соотношения дают вычислительную сложность O(n) и O(\log n) соответственно. Получение решения в замкнутой форме должно приводить к алгоритмам в которых вычислительная сложность минимальна — O(1), т. е. вообще не зависит от n и m. (Длина записи представления чисел в системе счисления не учитывается). Построение таких формул крайне желательно и для данной задачи. Например, для m=2 не сложно получить формулу

 k(n)=2\cdot\left(n-2^{\lfloor \log_2 n \rfloor}\right)+1

Способы решения[править | править исходный текст]

Переборное решение[править | править исходный текст]

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

Способ первый[править | править исходный текст]

Будем хранить в массиве имена (то есть номера) всех живых на текущий момент воинов. Причем удобно, чтобы номера людей были записаны в элементах массива с 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 (N^2). Используя дерево отрезков, можно произвести моделирование за O(N log N). Однако попытаемся найти закономерность, выражающую ответ для задачи (N,K) через решение предыдущих задач. С помощью моделирования построим таблицу значений, скажем, приведенную ниже.

Табличка
1 2 3 4 5 6 7 8 9 10
1 1 1 1 1 1 1 1 1 1 1
2 2 1 2 1 2 1 2 1 2 1
3 3 3 2 2 1 1 3 3 2 2
4 4 1 1 2 2 3 2 3 3 4
5 5 3 4 1 2 4 4 1 2 4
6 6 5 1 5 1 4 5 3 5 2
7 7 7 4 2 6 3 5 4 7 5
8 8 1 7 6 3 1 4 4 8 7
9 9 3 1 1 8 7 2 3 8 8
10 10 5 4 5 3 3 9 1 7 8

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

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

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

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

Пример[править | править исходный текст]

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

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

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

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

400 400 400
Рис 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.

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

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

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

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

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

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

400

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

Решение на основе двоичного представления n[править | править исходный текст]

Рассмотрим двоичные представлениям величин n и J(n):

n = bm*2^m + bm-1*2^(m-1) + … + b1*2 + b0

где каждое bi равно 0 или 1, причем старший бит bm равен 1. Вспоминая, что n=2^m+k, последовательно получаем:
n = (1 bm-1 … b1 b0)2
k = (0 bm-1 … b1 b0)2
(т.к. k= n−2^m = 2^m + bm-1*2^(m-1) + … + b1*2 + b0 − 2^m = 0∙2^m + bm-12^(m-1) + …+ b1*2 + b0)
2k = (bm-1 … b1 b0 0)2
(т.к. 2 k=2(bm-1*2^(m-1) +bm-2*2^(m-2) …+ b1*2 + b0)=bm-1*2^m + bm-2*2^(m-1) + … + b1*2^2 + b0*2+0)
2k+1 = (bm-1 … b1 b0 1)2
J(n) = (bm-1 … b1 b0 bm)2
(т.к. J(n) = 2k+1 и bm = 1)
Таким образом, мы получили, что
J((bm bm-1 … b1 b0)2) = (bm-1 … b1 b0 bm)2
т.е. J(n) получается путем циклического сдвига двоичного представления n влево на одну позицию.

Литература[править | править исходный текст]