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

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

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

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

Рекуррентные соотношения

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

Для имеем

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

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

$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}$ .

Замкнутая формула

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

Способы решения

Переборное решение

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

Способ первый

Будем хранить в массиве имена (то есть номера) всех живых на текущий момент воинов. Причем удобно, чтобы номера людей были записаны в элементах массива с 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,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

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

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

Пример

С целью подробного объяснения возможных ситуаций, которые могут возникнуть в ходе решения, упростим исходную задачу и рассмотрим случай № 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

Рассмотрим двоичные представлениям величин 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 влево на одну позицию.

Литература

М. А. Алексеев Задача Иосифа Флавия // Империя Математики. — 2001. — № 2. — С. 22—28.
Дональд Кнут, Роналд Грэхем, Орен Паташник Конкретная математика. Основание информатики = Concrete Mathematics. A Foundation for Computer Science. — М.: Мир; Бином. Лаборатория знаний, 2006. — С. 703. — ISBN 5-94774-560-7

Lt304888.ru

Туристические услуги

Рекомендуем