E144. 問題 Иосифа

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

問題文 задачи. given натуральные

и

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

. Сначала

отсчитывают

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

чисел и

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

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

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

. Используя

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

.

解法 за

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

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

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

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

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

}

解法 за

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

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

рекурсивное 解法 за

. Если

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

, а до этого

момента アルゴリズム просто несколько раз прибавляет к ответу number

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

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

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

с меньшим

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

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

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

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

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

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

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

}

Оценим асимптотику этого アルゴリズムа. Сразу заметим, что случай

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

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

. Теперь рассмотрим сам アルゴリズム. Фактически, на каждой

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

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

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

итераций

アルゴリズムа 例но можно find из уравнения: логарифмируя его, получаем:

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

Таким образом, Asymptotic complexity アルゴリズムа действительно

.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

выведены

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