E144. Task Иосифа

Источник: e-maxx.ru/algo, страница PDF 475.

Statement задачи. given натуральные

и

. По кругу выписывают все натуральные числа от 1 до

. Сначала

отсчитывают

-ое number, начиная с первого, и удаляют его. Затем от него отсчитывают

чисел и

-ое удаляют, и т. д. Процесс останавливается, когда остаётся одно number. it is required find это number. Task была поставлена Иосифом Флавием (Flavius Josephus) ещё в 1 веке (правда, в несколько более

узкой формулировке: при

). Решать эту задачу можно моделированием. Простейшее моделирование будет работать

. Используя

Segment tree, можно произвести моделирование за

.

Solution за

Попытаемся find закономерность, выражающую ответ для задачи

через Solution предыдущих задач. С помощью моделирования построим таблицу значений, наExample, такую: И здесь достаточно отчётливо видна следующая закономерность:

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

Итак, мы нашли Solution задачи Иосифа, работающее за

операций. Простая рекурсивная Implementation (в 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;

}

Solution за

Для сравнительно небольших

можно придумать более оптимальное Solution, чем рассмотренное выше

рекурсивное Solution за

. Если

небольшое, то даже интуитивно понятно, что тот Algorithm делает много лишних действий: серьёзные изменения происходят, только когда происходит взятие по модулю

, а до этого

момента Algorithm просто несколько раз прибавляет к ответу number

. Соответственно, можно избавиться от

этих ненужных шагов,

Небольшая возникающая при этом Complexity заключается в том, что после удаления этих чисел у нас получится Task

с меньшим

, но стартовой позицией не в первом числе, а где-то в другом месте. Поэтому, вызвав рекурсивно себя

от задачи с новым

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

Также отдельно надо разбирать случай, когда

станет меньше

— в этом случае вышеописанная

оптимизация выродится в бесконечный цикл. Implementation (для удобства в 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;

}

Оценим асимптотику этого Algorithmа. Сразу заметим, что случай

разбирается у нас старым

Solutionм, которое отработает в данном случае за

. Теперь рассмотрим сам Algorithm. Фактически, на каждой

его итерации вместо

чисел мы получаем Exampleно

чисел, поэтому общее number

итераций

Algorithmа Exampleно можно find из уравнения: логарифмируя его, получаем:

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

Таким образом, Asymptotic complexity Algorithmа действительно

.

Аналитическое Solution для

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

В случае чётного

получаем, что будут вычеркнуты все чётные числа, а потом останется Task для

, тогда ответ для

будет получаться из ответа для

умножением на два и вычитанием единицы (за счёт сдвига позиций):

Аналогично, в случае нечётного

будут вычеркнуты все чётные числа, затем первое number, и останется Task для , и с учётом сдвига позиций получаем вторую формулу: При реализации можно непосредственно использовать эту рекуррентную зависимость. Можно эту закономерность перевести в другую форму:

представляют собой последовательность всех нечётных

чисел, "перезапускающуюся" с единицы всякий раз, когда

оказывается степенью двойки. Это можно записать и в

виде одной формулы:

Аналитическое Solution для

Несмотря на простой вид задачи и большое количество статей по этой и смежным Taskм, простого аналитического представления решения задачи Иосифа до сих пор не найдено. Для небольших

выведены

некоторые формулы, но, по-видимому, все они трудноприменимы на практике (наExample, см. Halbeisen, Hungerbuhler "The Josephus Problem" и Odlyzko, Wilf "Functional iteration and the Josephus problem").