Задача Иосифа Флавия: рекурсия, формула и моделирование очередью

Задача Иосифа Флавия простыми словами: моделирование списком и очередью, рекуррентная формула J(n, k) за O(n), решение для k = 2 через биты, порядок выбывания и разбор LeetCode 1823.

11 мин чтенияалгоритмы · рекурсия · математика · python

Коротко

ВопросОтвет
Задачаnn человек стоят по кругу, выбывает каждый kk-й. Кто останется последним?
МоделированиеСписок или очередь: O(n2)O(n^2) или O(nk)O(nk) времени — для собеседования часто хватает
Главная формулаJ(1)=0J(1) = 0, J(n)=(J(n−1)+k) mod nJ(n) = (J(n-1) + k) \bmod n — нумерация с нуля, O(n)O(n) времени и O(1)O(1) памяти
Случай k=2k = 2n=2m+l⇒n = 2^m + l \Rightarrow выживает 2l+12l + 1: циклический сдвиг двоичной записи nn влево
На собеседованииLeetCode 1823 Find the Winner of the Circular Game, вопросы про рекурсию и перенумерацию

Задача Иосифа — отличный тест на то, умеете ли вы превращать моделирование в формулу. Решение «в лоб» пишется за пять минут, и интервьюер почти наверняка спросит: «А можно быстрее?» Ответ — одна строка с остатком от деления, но вывести её нужно уметь самому.

Условие и история

nn человек стоят по кругу и пронумерованы от 1 до nn. Начиная с первого, считают по кругу: каждый kk-й выбывает, счёт продолжается со следующего за ним. Круг сужается, пока не останется один человек. Нужно найти его номер.

Название — от историка Иосифа Флавия. В «Иудейской войне» он описывает, как в 67 году н. э. после падения крепости Иотапата он с соратниками укрылся в пещере, и те решили покончить с собой по жребию, а Иосиф оказался среди последних выживших. Популярная версия с 41 человеком и каждым третьим выбывающим — более поздний пересказ, превративший историю в математическую задачу. В этой версии Иосиф заранее встал на 31-е место, а своего товарища поставил на 16-е — эти двое остаются последними. Проверим это ниже кодом.

Пример для n=7n = 7, k=3k = 3. Считаем: 1, 2, 3 — выбывает 3. Дальше 4, 5, 6 — выбывает 6. Потом 7, 1, 2, затем 4, 5, 7, затем 1, 4, 5. Остались двое, 1 и 4: считаем 1, 4, 1 — выбывает 1. Последним остаётся 4.

Порядок выбывания: 3, 6, 2, 7, 5, 1, 4. Вручную легко сбиться, поэтому начнём с кода, который считает за нас.

Решение 1: моделирование списком

Самое прямолинейное — хранить живых в списке и удалять по индексу. Ключевая деталь: после удаления элемента с индексом i следующий за ним сдвигается на место i, поэтому счёт продолжается с того же индекса.

def josephus_list(n, k): people = list(range(1, n + 1)) order = [] i = 0 while people: i = (i + k - 1) % len(people) # индекс k-го, считая от текущего order.append(people.pop(i)) return order # последний в order — выживший print(josephus_list(7, 3)) # [3, 6, 2, 7, 5, 1, 4] print(josephus_list(41, 3)[-2:]) # [16, 31] — Иосиф и его товарищ

Почему k - 1, а не k: текущий человек сам считается первым, поэтому до kk-го нужно отступить на k−1k - 1 позиций. Остаток от длины списка замыкает круг.

Сложность: nn удалений, каждое pop(i) из середины списка стоит O(n)O(n). Итого O(n2)O(n^2) — для nn до 10410^4 нормально, для 10610^6 уже медленно. Плюс этого подхода в том, что он сразу выдаёт порядок выбывания, а не только победителя.

Решение 2: очередь

Круг естественно моделируется очередью: первые k−1k - 1 человек «переходят» из начала в конец, а kk-й выбывает. Это ровно то, как задачу формулируют в учебниках про стек и очередь.

from collections import deque def josephus_deque(n, k): q = deque(range(1, n + 1)) while len(q) > 1: q.rotate(-(k - 1)) # k-1 человек уходят из начала в конец q.popleft() # k-й выбывает return q[0] print(josephus_deque(7, 3)) # 4

deque.rotate сдвигает элементы по кругу; отрицательный аргумент — влево, то есть из начала в конец. Подробнее про устройство двусторонней очереди — в статье про дек.

Сложность O(nk)O(nk): на каждое из nn выбываний — O(k)O(k) перекладываний. Когда kk маленькое, это быстрее списка; когда kk сравнимо с nn — так же медленно. Можно брать (k - 1) % len(q), чтобы не крутить лишние полные круги, но в худшем случае это всё равно O(n2)O(n^2).

На собеседовании решение с очередью — хороший первый ответ: оно очевидно корректное и показывает, что вы видите структуру данных за условием. Но затем вас попросят O(n)O(n).

Решение 3: рекуррентная формула

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

Перейдём к нумерации с нуля: люди 0,1,…,n−10, 1, \dots, n - 1, счёт с нулевого. Пусть J(n)J(n) — номер выжившего в круге из nn человек.

Шаг 1. Первым выбывает человек с номером (k−1) mod n(k - 1) \bmod n.

Шаг 2. Остаётся n−1n - 1 человек, и счёт начинается со следующего, с номера k mod nk \bmod n. Это та же задача размера n−1n - 1, только люди перенумерованы. Дадим новые номера: тот, с кого начинается счёт, получает 0, следующий 1 и так далее.

Шаг 3. Как связаны старый и новый номер? Новый номер 0 соответствует старому k mod nk \bmod n, новый 1 — старому (k+1) mod n(k + 1) \bmod n. В общем виде:

старый=(новый+k) mod n.\text{старый} = (\text{новый} + k) \bmod n.

Шаг 4. В меньшем круге выживает человек с новым номером J(n−1)J(n - 1). Переводим в старую нумерацию:

J(1)=0,J(n)=(J(n−1)+k) mod n.J(1) = 0, \qquad J(n) = (J(n-1) + k) \bmod n.

Вот и всё. В кругу из одного человека выживает он сам, а каждый следующий шаг — сдвиг на kk по модулю. Модуль здесь — обычный остаток от деления, без всяких хитростей модульной арифметики.

Пример по шагам

Для k=3k = 3:

nn1234567
J(n)J(n), с нуля0110303

Например, J(5)=(0+3) mod 5=3J(5) = (0 + 3) \bmod 5 = 3, J(7)=(0+3) mod 7=3J(7) = (0 + 3) \bmod 7 = 3. В нумерации с единицы ответ для n=7n = 7 — это 3+1=43 + 1 = 4, как и при моделировании.

Код: рекурсивно и итеративно

def josephus_rec(n, k): # ответ в нумерации с нуля if n == 1: return 0 return (josephus_rec(n - 1, k) + k) % n def josephus(n, k): res = 0 # J(1) = 0 for m in range(2, n + 1): res = (res + k) % m return res + 1 # переводим в нумерацию с единицы print(josephus_rec(7, 3) + 1, josephus(7, 3)) # 4 4 print(josephus(41, 3)) # 31

Рекурсивная версия красивая, но в Python упадёт на nn около 1000: глубина рекурсии по умолчанию ограничена. Итеративная — O(n)O(n) времени и O(1)O(1) памяти, на n=107n = 10^7 работает за секунды.

Внимание к модулю: в цикле берём % m, где m — текущий размер круга, а не исходное n. Это самая частая ошибка при переписывании формулы из головы.

Решение для k = 2: формула через биты

Для k=2k = 2 (выбывает каждый второй) есть закрытая формула. Посмотрим на ответы в нумерации с единицы:

nn12345678910111213141516
J(n)J(n)1131357135791113151

Закономерность видна сразу: на каждой степени двойки ответ сбрасывается в 1, а потом растёт на 2.

Почему так. При чётном n=2mn = 2m за первый проход выбывают все чётные: 2,4,…,2m2, 4, \dots, 2m. Остаются 1,3,…,2m−11, 3, \dots, 2m - 1 — это mm человек, и счёт снова начинается с первого. Значит, J(2m)=2J(m)−1J(2m) = 2J(m) - 1.

При нечётном n=2m+1n = 2m + 1 за проход выбывают чётные, а затем и номер 1. Остаются 3,5,…,2m+13, 5, \dots, 2m + 1, счёт начинается с 3. Значит, J(2m+1)=2J(m)+1J(2m + 1) = 2J(m) + 1.

Из этих двух соотношений по индукции получается: если n=2a+ln = 2^a + l, где 0≤l<2a0 \le l < 2^a, то

J(n)=2l+1.J(n) = 2l + 1.

Интуиция: когда людей ровно степень двойки, каждый проход выбивает половину и счёт снова начинается с первого, так что первый и выживает. Если сверх степени двойки ещё ll человек, после ll выбываний (это номера 2,4,…,2l2, 4, \dots, 2l) людей остаётся ровно 2a2^a, а счёт начинается с номера 2l+12l + 1. Он и выживет.

А теперь красивое наблюдение. n=2a+ln = 2^a + l в двоичной записи — это единица и за ней биты ll. Ответ 2l+12l + 1 — биты ll, сдвинутые влево, и единица в конце. То есть ответ — циклический сдвиг двоичной записи nn на один бит влево.

def josephus_k2(n): l = n - (1 << (n.bit_length() - 1)) # n = 2^a + l return 2 * l + 1 def josephus_k2_bits(n): b = bin(n)[2:] return int(b[1:] + b[0], 2) # циклический сдвиг влево print(josephus_k2(41), josephus_k2_bits(41)) # 19 19

Для n=41=1010012n = 41 = 101001_2 сдвиг даёт 0100112=19010011_2 = 19. Это O(1)O(1) по сравнению с O(n)O(n), но только для k=2k = 2. Про трюки с bit_length и сдвигами — в статье о битовых операциях.

Огромное n и маленькое k

Если n=1018n = 10^{18}, даже O(n)O(n) не годится. Для маленьких kk есть рекурсия за O(klog⁡n)O(k \log n): за один полный проход по кругу выбывают сразу ⌊n/k⌋\lfloor n / k \rfloor человек (номера k−1,2k−1,…k - 1, 2k - 1, \dots в нумерации с нуля), задача сводится к кругу из n−⌊n/k⌋n - \lfloor n/k \rfloor человек, а затем ответ переводится обратно в исходную нумерацию.

def josephus_fast(n, k): # O(k log n): выгодно, когда k мало, а n огромно; ответ с нуля if n == 1: return 0 if k == 1: return n - 1 if k > n: return (josephus_fast(n - 1, k) + k) % n cnt = n // k # за один проход по кругу выбывает n // k человек res = josephus_fast(n - cnt, k) res -= n % k if res < 0: res += n else: res += res // (k - 1) return res print(josephus_fast(7, 3) + 1) # 4 print(josephus_fast(10**18, 3) + 1) # 774011304974515843

Логика перевода: новый круг начинается сразу после последнего выбывшего, то есть с номера k⋅cntk \cdot \text{cnt}. Хвост из n mod kn \bmod k человек в конце старого круга стал первыми в новом — отсюда вычитание n % k. Если результат отрицательный, выживший — из этого хвоста. Иначе он из основной части, и к его номеру добавляем число выбывших перед ним: среди каждых kk подряд стоящих выбыл один, поэтому res // (k - 1).

Каждый шаг уменьшает nn примерно в kk−1\frac{k}{k-1} раз, отсюда глубина O(klog⁡n)O(k \log n). Это уже олимпиадный уровень; на обычном собеседовании хватит формулы за O(n)O(n), но знать, что такое ускорение существует, полезно.

Порядок выбывания за O(n log n)

Формула даёт только победителя. Если нужен весь порядок выбывания для больших nn, моделирование списком за O(n2)O(n^2) не подойдёт. Нужна структура, которая умеет «найти tt-го живого» и «удалить человека» за O(log⁡n)O(\log n). Подходит дерево Фенвика или дерево отрезков, где в каждой позиции лежит 1 для живых и 0 для выбывших.

def elimination_order(n, k): # дерево Фенвика: tree хранит, сколько живых людей в каждом блоке tree = [0] * (n + 1) for i in range(1, n + 1): tree[i] += 1 j = i + (i & -i) if j <= n: tree[j] += tree[i] def remove(i): while i <= n: tree[i] -= 1 i += i & -i def kth(t): # позиция t-го живого (с единицы) за O(log n) pos, step = 0, 1 << n.bit_length() while step: nxt = pos + step if nxt <= n and tree[nxt] < t: pos = nxt t -= tree[nxt] step >>= 1 return pos + 1 order, idx = [], 0 # idx — номер текущего среди живых, с нуля for alive in range(n, 0, -1): idx = (idx + k - 1) % alive person = kth(idx + 1) remove(person) order.append(person) return order print(elimination_order(7, 3)) # [3, 6, 2, 7, 5, 1, 4]

Индексная арифметика та же, что в решении со списком, только вместо people.pop(i) — поиск ii-го живого спуском по дереву Фенвика. Итого O(nlog⁡n)O(n \log n).

LeetCode 1823: Find the Winner of the Circular Game

Это задача Иосифа в чистом виде: nn друзей по кругу, выбывает каждый kk-й, верните номер победителя (с единицы). Ограничения маленькие (n≤500n \le 500), так что пройдёт и очередь. Но follow-up в описании прямо просит решение за линейное время и O(1)O(1) памяти — это наша формула.

function findTheWinner(n, k) { let res = 0 for (let m = 2; m <= n; m++) res = (res + k) % m return res + 1 } console.log(findTheWinner(5, 2)) // 3 console.log(findTheWinner(6, 5)) // 1

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

Типичные ошибки

Путаница нумерации с нуля и с единицы

Формула J(n)=(J(n−1)+k) mod nJ(n) = (J(n-1) + k) \bmod n работает в нумерации с нуля. Если хочется сразу с единицы, получится J(n)=((J(n−1)+k−1) mod n)+1J(n) = ((J(n-1) + k - 1) \bmod n) + 1 — громоздко и легко ошибиться. Проще считать с нуля и прибавить 1 в самом конце.

Модуль по исходному n

res = (res + k) % n вместо % m — даёт неверный ответ, но не падает. Перенумерация на каждом шаге идёт в круге текущего размера.

Сдвиг на k вместо k − 1 при моделировании

Текущий человек тоже считается. Если отступить на kk, выбывать будет каждый (k+1)(k + 1)-й. Проверяйте на маленьком примере: при n=5n = 5, k=2k = 2 первым должен выбыть номер 2, а победить — номер 3.

Рекурсия на большом n

Красивая рекурсивная версия в Python упирается в лимит глубины уже около n=1000n = 1000. Поднимать sys.setrecursionlimit до миллиона — путь к падению интерпретатора. Используйте цикл.

Формула для k = 2 в общем случае

2l+12l + 1 — только для k=2k = 2. Для других kk закрытой формулы такого вида нет; есть рекуррентность и ускорение для малых kk.

Где это встречается на собеседованиях

  • LeetCode 1823 и его вариации. «Дети в кругу», «считалочка», «удаляем каждый k-й элемент из кольцевого списка». Ждут сначала моделирование, затем O(n)O(n).
  • Как задача на рекурсию. Наряду с ханойскими башнями — классический пример, где рекурсивное мышление превращает запутанный процесс в одну строку.
  • Как задача на структуры данных. Кольцевой связный список, очередь, кольцевой буфер — интервьюер может попросить реализовать моделирование конкретной структурой и обсудить сложность удаления.
  • Как математическая головоломка. Вариант с k=2k = 2 и вопрос «где встать, чтобы выжить» проверяет, видите ли вы закономерность в таблице и можете ли её доказать.

Чтобы закрепить, напишите все три решения — список, очередь и формулу — и сравните их на случайных nn и kk. Совпадение ответов на тысячах тестов даёт уверенность, что вы правильно поняли и перенумерацию, и сдвиг на k−1k - 1.

Потренироваться в спокойной обстановке

Все задачи