MAXimal

добавлено: 11 Jun 2008 11:25
редактировано: 14 Oct 2011 0:05

Задача Иосифа

Условие задачи. Даны натуральные $n$ и $k$ . По кругу выписывают все натуральные числа от 1 до $n$ . Сначала отсчитывают $k$ -ое число, начиная с первого, и удаляют его. Затем от него отсчитывают $k$ чисел и $k$ -ое удаляют, и т.д. Процесс останавливается, когда остаётся одно число. Требуется найти это число.

Задача была поставлена Иосифом Флавием (Flavius Josephus) ещё в 1 веке (правда, в несколько более узкой формулировке: при $k = 2$ ).

Решать эту задачу можно моделированием. Простейшее моделирование будет работать $O (n^2)$ . Используя Дерево отрезков, можно произвести моделирование за $O (n \log n)$ .

Решение за $O(n)$

Попытаемся найти закономерность, выражающую ответ для задачи $J_{n,k}$ через решение предыдущих задач.

С помощью моделирования построим таблицу значений, например, такую:

$\bordermatrix { n \setminus k&1&2&3&4&5&6&7&8&9&[...]$

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

$J_{n,k} = \left( J_{(n-1),k} + k - 1 \right)\ \%\[...]$
$J_{1,k} = 1$

Здесь 1-индексация несколько портит элегантность формулы, если нумеровать позиции с нуля, то получится очень наглядная формула:

$J_{n,k} = \left( J_{(n-1),k} + k \right)\ \%\ n =[...]$

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

Простая рекурсивная реализация (в 1-индексации):

int joseph (int n, int k) {
	return n>1 ? (joseph (n-1, k) + k - 1) % n + 1 : 1;
}

Нерекурсивная форма:

int joseph (int n, int k) {
	int res = 0;
	for (int i=1; i<=n; ++i)
		res = (res + k) % i;
	return res + 1;
}

Решение за $O(k \log n)$

Для сравнительно небольших $k$ можно придумать более оптимальное решение, чем рассмотренное выше рекурсивное решение за $O(n)$ . Если $k$ небольшое, то даже интуитивно понятно, что тот алгоритм делает много лишних действий: серьёзные изменения происходят, только когда происходит взятие по модулю $n$ , а до этого момента алгоритм просто несколько раз прибавляет к ответу число $k$ . Соответственно, можно избавиться от этих ненужных шагов,

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

Также отдельно надо разбирать случай, когда $n$ станет меньше $k$ — в этом случае вышеописанная оптимизация выродится в бесконечный цикл.

Реализация (для удобства в 0-индексации):

int joseph (int n, int k) {
	if (n == 1)  return 0;
	if (k == 1)  return n-1;
	if (k > n)  return (joseph (n-1, k) + k) % n;
	int cnt = n / k;
	int res = joseph (n - cnt, k);
	res -= n % k;
	if (res < 0)  res += n;
	else  res += res / (k - 1);
	return res;
}

Оценим асимптотику этого алгоритма. Сразу заметим, что случай $n < k$ разбирается у нас старым решением, которое отработает в данном случае за $O(k)$ . Теперь рассмотрим сам алгоритм. Фактически, на каждой его итерации вместо $n$ чисел мы получаем примерно $n \left( 1 - \frac{1}{k} \right)$ чисел, поэтому общее число $x$ итераций алгоритма примерно можно найти из уравнения:

$n \left( 1 - \frac{1}{k} \right) ^ x = 1,$

логарифмируя его, получаем:

$\ln n + x \ln \left( 1 - \frac{1}{k} \right) = 0,[...]$
$x = - \frac{ \ln n }{ \ln \left( 1 - \frac{1}{k} [...]$

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

$x \approx k \ln n$

Таким образом, асимптотика алгоритма действительно $O(k \log n)$ .

Аналитическое решение для $k=2$

В этом частном случае (в котором и была поставлена эта задача Иосифом Флавием) задача решается значительно проще.

В случае чётного $n$ получаем, что будут вычеркнуты все чётные числа, а потом останется задача для $\frac{n}{2}$ , тогда ответ для $n$ будет получаться из ответа для $\frac{n}{2}$ умножением на два и вычитанием единицы (за счёт сдвига позиций):

$J_{2n,2} = 2 J_{n,2} - 1$

Аналогично, в случае нечётного $n$ будут вычеркнуты все чётные числа, затем первое число, и останется задача для $\frac{n-1}{2}$ , и с учётом сдвига позиций получаем вторую формулу:

$J_{2n+1,2} = 2 J_{n,2} + 1$

При реализации можно непосредственно использовать эту рекуррентную зависимость. Можно эту закономерность перевести в другую форму: $J_{n,2}$ представляют собой последовательность всех нечётных чисел, "перезапускающуюся" с единицы всякий раз, когда $n$ оказывается степенью двойки. Это можно записать и в виде одной формулы:

$J_{n,2} = 1 + 2 \left( n - 2^{\lfloor \log_2 n \r[...]$

Аналитическое решение для $k>2$

Несмотря на простой вид задачи и большое количество статей по этой и смежным задачам, простого аналитического представления решения задачи Иосифа до сих пор не найдено. Для небольших $k$ выведены некоторые формулы, но, по-видимому, все они трудноприменимы на практике (например, см. Halbeisen, Hungerbuhler "The Josephus Problem" и Odlyzko, Wilf "Functional iteration and the Josephus problem").