Задача Иосифа Флавия: рекурсия, формула и моделирование очередью
Задача Иосифа Флавия простыми словами: моделирование списком и очередью, рекуррентная формула J(n, k) за O(n), решение для k = 2 через биты, порядок выбывания и разбор LeetCode 1823.
Коротко
| Вопрос | Ответ |
|---|---|
| Задача | человек стоят по кругу, выбывает каждый -й. Кто останется последним? |
| Моделирование | Список или очередь: или времени — для собеседования часто хватает |
| Главная формула | , — нумерация с нуля, времени и памяти |
| Случай | выживает : циклический сдвиг двоичной записи влево |
| На собеседовании | LeetCode 1823 Find the Winner of the Circular Game, вопросы про рекурсию и перенумерацию |
Задача Иосифа — отличный тест на то, умеете ли вы превращать моделирование в формулу. Решение «в лоб» пишется за пять минут, и интервьюер почти наверняка спросит: «А можно быстрее?» Ответ — одна строка с остатком от деления, но вывести её нужно уметь самому.
Условие и история
человек стоят по кругу и пронумерованы от 1 до . Начиная с первого, считают по кругу: каждый -й выбывает, счёт продолжается со следующего за ним. Круг сужается, пока не останется один человек. Нужно найти его номер.
Название — от историка Иосифа Флавия. В «Иудейской войне» он описывает, как в 67 году н. э. после падения крепости Иотапата он с соратниками укрылся в пещере, и те решили покончить с собой по жребию, а Иосиф оказался среди последних выживших. Популярная версия с 41 человеком и каждым третьим выбывающим — более поздний пересказ, превративший историю в математическую задачу. В этой версии Иосиф заранее встал на 31-е место, а своего товарища поставил на 16-е — эти двое остаются последними. Проверим это ниже кодом.
Пример для , . Считаем: 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: текущий человек сам считается первым, поэтому до -го нужно отступить на позиций. Остаток от длины списка замыкает круг.
Сложность: удалений, каждое pop(i) из середины списка стоит . Итого — для до нормально, для уже медленно. Плюс этого подхода в том, что он сразу выдаёт порядок выбывания, а не только победителя.
Решение 2: очередь
Круг естественно моделируется очередью: первые человек «переходят» из начала в конец, а -й выбывает. Это ровно то, как задачу формулируют в учебниках про стек и очередь.
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 сдвигает элементы по кругу; отрицательный аргумент — влево, то есть из начала в конец. Подробнее про устройство двусторонней очереди — в статье про дек.
Сложность : на каждое из выбываний — перекладываний. Когда маленькое, это быстрее списка; когда сравнимо с — так же медленно. Можно брать (k - 1) % len(q), чтобы не крутить лишние полные круги, но в худшем случае это всё равно .
На собеседовании решение с очередью — хороший первый ответ: оно очевидно корректное и показывает, что вы видите структуру данных за условием. Но затем вас попросят .
Решение 3: рекуррентная формула
Здесь работает тот же приём, что и в любой рекурсии: не пытаемся смоделировать всё, а сводим задачу к меньшей.
Перейдём к нумерации с нуля: люди , счёт с нулевого. Пусть — номер выжившего в круге из человек.
Шаг 1. Первым выбывает человек с номером .
Шаг 2. Остаётся человек, и счёт начинается со следующего, с номера . Это та же задача размера , только люди перенумерованы. Дадим новые номера: тот, с кого начинается счёт, получает 0, следующий 1 и так далее.
Шаг 3. Как связаны старый и новый номер? Новый номер 0 соответствует старому , новый 1 — старому . В общем виде:
Шаг 4. В меньшем круге выживает человек с новым номером . Переводим в старую нумерацию:
Вот и всё. В кругу из одного человека выживает он сам, а каждый следующий шаг — сдвиг на по модулю. Модуль здесь — обычный остаток от деления, без всяких хитростей модульной арифметики.
Пример по шагам
Для :
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | |
|---|---|---|---|---|---|---|---|
| , с нуля | 0 | 1 | 1 | 0 | 3 | 0 | 3 |
Например, , . В нумерации с единицы ответ для — это , как и при моделировании.
Код: рекурсивно и итеративно
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 упадёт на около 1000: глубина рекурсии по умолчанию ограничена. Итеративная — времени и памяти, на работает за секунды.
Внимание к модулю: в цикле берём % m, где m — текущий размер круга, а не исходное n. Это самая частая ошибка при переписывании формулы из головы.
Решение для k = 2: формула через биты
Для (выбывает каждый второй) есть закрытая формула. Посмотрим на ответы в нумерации с единицы:
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 1 | 1 | 3 | 1 | 3 | 5 | 7 | 1 | 3 | 5 | 7 | 9 | 11 | 13 | 15 | 1 |
Закономерность видна сразу: на каждой степени двойки ответ сбрасывается в 1, а потом растёт на 2.
Почему так. При чётном за первый проход выбывают все чётные: . Остаются — это человек, и счёт снова начинается с первого. Значит, .
При нечётном за проход выбывают чётные, а затем и номер 1. Остаются , счёт начинается с 3. Значит, .
Из этих двух соотношений по индукции получается: если , где , то
Интуиция: когда людей ровно степень двойки, каждый проход выбивает половину и счёт снова начинается с первого, так что первый и выживает. Если сверх степени двойки ещё человек, после выбываний (это номера ) людей остаётся ровно , а счёт начинается с номера . Он и выживет.
А теперь красивое наблюдение. в двоичной записи — это единица и за ней биты . Ответ — биты , сдвинутые влево, и единица в конце. То есть ответ — циклический сдвиг двоичной записи на один бит влево.
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
Для сдвиг даёт . Это по сравнению с , но только для . Про трюки с bit_length и сдвигами — в статье о битовых операциях.
Огромное n и маленькое k
Если , даже не годится. Для маленьких есть рекурсия за : за один полный проход по кругу выбывают сразу человек (номера в нумерации с нуля), задача сводится к кругу из человек, а затем ответ переводится обратно в исходную нумерацию.
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
Логика перевода: новый круг начинается сразу после последнего выбывшего, то есть с номера . Хвост из человек в конце старого круга стал первыми в новом — отсюда вычитание n % k. Если результат отрицательный, выживший — из этого хвоста. Иначе он из основной части, и к его номеру добавляем число выбывших перед ним: среди каждых подряд стоящих выбыл один, поэтому res // (k - 1).
Каждый шаг уменьшает примерно в раз, отсюда глубина . Это уже олимпиадный уровень; на обычном собеседовании хватит формулы за , но знать, что такое ускорение существует, полезно.
Порядок выбывания за O(n 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) — поиск -го живого спуском по дереву Фенвика. Итого .
LeetCode 1823: Find the Winner of the Circular Game
Это задача Иосифа в чистом виде: друзей по кругу, выбывает каждый -й, верните номер победителя (с единицы). Ограничения маленькие (), так что пройдёт и очередь. Но follow-up в описании прямо просит решение за линейное время и памяти — это наша формула.
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
Хорошая стратегия на собеседовании: сначала проговорить моделирование очередью и его сложность, затем вывести рекуррентность вслух через перенумерацию. Интервьюеру важнее увидеть вывод, чем услышать заученную формулу.
Типичные ошибки
Путаница нумерации с нуля и с единицы
Формула работает в нумерации с нуля. Если хочется сразу с единицы, получится — громоздко и легко ошибиться. Проще считать с нуля и прибавить 1 в самом конце.
Модуль по исходному n
res = (res + k) % n вместо % m — даёт неверный ответ, но не падает. Перенумерация на каждом шаге идёт в круге текущего размера.
Сдвиг на k вместо k − 1 при моделировании
Текущий человек тоже считается. Если отступить на , выбывать будет каждый -й. Проверяйте на маленьком примере: при , первым должен выбыть номер 2, а победить — номер 3.
Рекурсия на большом n
Красивая рекурсивная версия в Python упирается в лимит глубины уже около . Поднимать sys.setrecursionlimit до миллиона — путь к падению интерпретатора. Используйте цикл.
Формула для k = 2 в общем случае
— только для . Для других закрытой формулы такого вида нет; есть рекуррентность и ускорение для малых .
Где это встречается на собеседованиях
- LeetCode 1823 и его вариации. «Дети в кругу», «считалочка», «удаляем каждый k-й элемент из кольцевого списка». Ждут сначала моделирование, затем .
- Как задача на рекурсию. Наряду с ханойскими башнями — классический пример, где рекурсивное мышление превращает запутанный процесс в одну строку.
- Как задача на структуры данных. Кольцевой связный список, очередь, кольцевой буфер — интервьюер может попросить реализовать моделирование конкретной структурой и обсудить сложность удаления.
- Как математическая головоломка. Вариант с и вопрос «где встать, чтобы выжить» проверяет, видите ли вы закономерность в таблице и можете ли её доказать.
Чтобы закрепить, напишите все три решения — список, очередь и формулу — и сравните их на случайных и . Совпадение ответов на тысячах тестов даёт уверенность, что вы правильно поняли и перенумерацию, и сдвиг на .