WikiSort.ru - Не сортированное

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

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

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

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

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

Для ${\displaystyle m=2}$ имеем

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

Для ${\displaystyle m=3}$ имеем

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

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

${\displaystyle \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}}}$ .

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

${\displaystyle 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}}}$ .

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

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

${\displaystyle k(n)=2\cdot \left(n-2^{\lfloor \log _{2}n\rfloor }\right)+1}$

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

Рекурсивное решение

Простейшее моделирование будет работать O (${\displaystyle N^{2}}$ ). Используя дерево отрезков, можно произвести моделирование за ${\displaystyle O(NlogN)}$ . Однако попытаемся найти закономерность, выражающую ответ для задачи (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

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

Итак, мы нашли решение задачи Иосифа Флавия, работающее за ${\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.

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

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

Примечания

Литература

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