EssayAI
Блог
Блог
Естественные науки

Задача Иосифа Флавия: формула и решение

8 ноября 2026Время чтения: 9 минут
#задача иосифа флавия#алгоритмы#рекуррентные соотношения#двоичная система#программирование
Задача Иосифа Флавия: формула и решение

Задача Иосифа Флавия - это задача о последовательном исключении участников из круга. Начинаем с первого, считаем по кругу и каждый раз убираем каждого kk-го; счёт продолжается со следующего оставшегося. Какой номер сохранится последним? Для семи участников при шаге три это номер 4. Калькулятор показывает весь порядок выбывания: измените число участников и шаг, чтобы проверить догадку, прежде чем переходить к формуле.

Условие и правила счёта

Пусть n≥1n \geq 1 человек стоят в кругу и пронумерованы от 1 до nn по направлению счёта. Первый участник получает счёт «один». На слове kk участник выбывает; затем следующий за ним получает новый счёт «один». Уже выбывших больше не считают. Процесс заканчивается, когда остаётся один человек. Его исходный номер и требуется найти.

Здесь существенны даже мелкие соглашения: кто начинает счёт, учитывается ли он и в каком направлении идёт обход. Изменение любого из них может изменить номер ответа. В некоторых формулировках говорят «пропускаем kk человек и удаляем следующего»: это соответствует шагу k+1k+1 в нашей записи. Если участников несколько, но нужен не только последний, дополнительно ищут перестановку Иосифа - порядок всех исключений.

Для семи участников последовательно отмечены исключения при счёте каждого третьего; после появления победителя показанные состояния идут обратно к началу.

Название связывают с рассказом Иосифа Флавия о событиях в Иотапате. В «Иудейской войне», книга III описан выбор жребием, после которого Иосиф и ещё один человек остались последними. Это литературный источник названия, а не доказательство, что историческое событие происходило по приведённому здесь правилу постоянного шага.

Пример: семь человек и каждый третий

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

Проверим переход после удаления 6: оставшиеся расположены по кругу как 1, 2, 4, 5, 7, но отсчёт начинается с 7. После перехода через границу списка сначала идёт 1, затем 2. Именно поэтому начало списка в программе не всегда совпадает с началом следующего счёта.

Порядок исключения при семи участниках и шаге три: 3, 6, 2, 7, 5, 1; остаётся номер 4
Порядок исключения при семи участниках и шаге три: 3, 6, 2, 7, 5, 1; остаётся номер 4

График калькулятора показывает исходные номера по горизонтали, а очередь выбывания - по вертикали. Для оставшегося используется последнее, nn-е место: оно выделено золотым. При n=1n=1 исключений нет, и единственный участник сразу является ответом. При k=1k=1 выбывают по порядку 1, 2 и так далее, пока не останется номер nn.

Как смоделировать исключения

Прямой способ - хранить список оставшихся и индекс начала счёта. Если в списке mm элементов, индекс удаляемого равен

i=(i+k−1) mod m.i = (i + k - 1) \bmod m.

Вычитание единицы нужно потому, что участник с текущим индексом уже получает счёт «один». После удаления элемент, следующий за ним, сдвигается на тот же индекс. Если удалён последний элемент списка, остаток по модулю на следующем шаге вернёт счёт к началу. При одном оставшемся список удалений готов.

Такой алгоритм удобен, когда нужно увидеть каждый шаг. Но удаление из середины обычного массива сдвигает последующие элементы: для nn участников это занимает в худшем случае O(n2)O(n^2) времени и O(n)O(n) памяти. Если нужен только оставшийся номер, можно обойтись без списка. Сравнивать время и память алгоритмов помогает отдельный разбор временной и пространственной сложности.

Рекуррентная формула для последнего

Обозначим через J(n,k)J(n,k) индекс оставшегося при нумерации с нуля: исходные индексы идут от 0 до n−1n-1. Тогда

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

После первого удаления остаётся круг из n−1n-1 участников. Если временно назвать первого после удалённого участника нулевым, оставшаяся задача имеет прежний вид. Ответ меньшей задачи известен как J(n−1,k)J(n-1,k). Чтобы вернуться к старым индексам, сдвигаем его на kk позиций по исходному кругу; остаток по модулю nn учитывает переход через конец. Для привычной нумерации от единицы к результату добавляют 1.

Для k=3k=3 значения J(n,3)J(n,3) при n=1,2,…,7n=1,2,\ldots,7 равны соответственно 0, 1, 1, 0, 3, 0, 3. Последний индекс 3 означает исходный номер 4. Это тот же результат, что в прямом обходе, но промежуточные значения относятся к отдельным задачам с разными размерами круга, а не к последовательности выбывания в одном круге.

Вычисление можно записать без рекурсивных вызовов:

def josephus(n, k):
    if n < 1 or k < 1:
        raise ValueError('n и k должны быть положительными')
    survivor = 0
    for size in range(2, n + 1):
        survivor = (survivor + k) % size
    return survivor + 1

Цикл делает n−1n-1 обновлений, поэтому работает за O(n)O(n) времени и использует O(1)O(1) дополнительной памяти. Он возвращает лишь победителя. Для полного порядка нужна другая структура или явная симуляция; ускорять её имеет смысл после определения требуемого результата. Идея повторного использования ответа меньшей задачи встречается и в динамическом программировании на примере рюкзака, хотя здесь достаточно хранить одно предыдущее значение.

Как проверить формулу на маленьком круге

Возьмём четыре места с нулевыми индексами 0, 1, 2, 3 и шаг три. Первым удаляется индекс 2. Новый круг начинается со старого индекса 3; если перенумеровать оставшихся от нуля по направлению счёта, получим соответствие: новый 0 - старый 3, новый 1 - старый 0, новый 2 - старый 1. Для нового круга из трёх мест ответ равен 1. Возвращаясь к исходной нумерации, получаем старый индекс 0: действительно, (1+3) mod 4=0(1+3) \bmod 4=0.

Это соответствие работает и когда шаг больше размера круга. Сдвиг на полные обороты не меняет места, а остаток оставляет только существенную часть сдвига. Обратите внимание, что модуль при обратном переходе равен размеру исходного круга, то есть четырём в примере. Если вместо него поставить размер уменьшенного круга, преобразование индексов потеряет одну из возможных позиций.

Для проверки программы полезно сравнить два независимых подхода на всех небольших значениях: моделирование полного списка и вычисление только последней позиции. Они должны совпадать для каждого выбранного шага, в том числе при одном участнике и шаге один. Такая проверка не доказывает формулу для всех чисел, но помогает обнаружить ошибки индексации и неверное продолжение счёта. Само обоснование даёт переход от круга размера n−1n-1 к кругу размера nn вместе с начальным случаем.

Быстрая формула для каждого второго

При k=2k=2 есть особенно простая формула. Представим nn как 2m+ℓ2^m+\ell, где 2m2^m - наибольшая степень двойки, не превосходящая nn, а 0≤ℓ<2m0 \leq \ell < 2^m. Тогда номер оставшегося при нумерации с единицы равен

2ℓ+1.2\ell+1.

Например, для n=41n=41 ближайшая меньшая степень двойки равна 32, остаток ℓ=9\ell=9, следовательно, ответ - 2⋅9+1=192\cdot9+1=19. Смысл виден после первого обхода: выбывают чётные номера, а нечётные образуют уменьшенный круг. Когда число участников пересекает очередную степень двойки, номер оставшегося снова начинается с 1 и затем растёт на 2.

Ту же операцию удобно проделать с двоичной записью: у числа 41 это 1010012101001_2. Переносим ведущую единицу в конец и получаем 0100112=19010011_2=19. Правило относится именно к шагу k=2k=2 и заданному началу счёта; подставлять в него произвольный kk нельзя. Здесь, как и при бинарном поиске по ответу, важны чёткие границы и проверка исходных предпосылок, хотя сами алгоритмы решают разные задачи.

Где полезна такая модель

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

При реализации полезно сначала вручную проверить маленький круг, особенно переход с последнего номера на первый. В задачах обхода графов тоже важно отдельно оговаривать порядок посещения и хранить состояние; для сравнения можно посмотреть обход графа в ширину. Там очередь управляет посещением соседей, тогда как в задаче Иосифа она моделирует удаление из фиксированного круга.

Частые ошибки

  • Начинать новый счёт с удалённого. Его уже нет; единицу получает следующий оставшийся участник.
  • Забывать про нулевую индексацию. Формула JJ возвращает индекс; для номера от 1 нужно прибавить единицу.
  • Считать удалённых повторно. Шаг отсчитывают только по оставшимся, даже когда обход переходит через начало.
  • Принимать значения рекурсии за порядок выбывания. Каждое значение относится к собственной задаче размера nn.
  • Применять формулу 2ℓ+12\ell+1 для любого шага. Она выведена для исключения каждого второго.

FAQ

Что делать, если шаг больше числа оставшихся? Продолжать счёт по кругу столько раз, сколько требуется. Остаток по модулю учитывает полные обороты автоматически.

Можно ли найти весь порядок по одной рекуррентной формуле? Приведённая формула хранит только последнюю позицию. Для порядка нужно отдельно моделировать удаления или использовать структуру, поддерживающую поиск и удаление по позиции.

Что меняется при другом первом участнике? При том же направлении и правиле все исходные номера ответа циклически сдвигаются вместе с началом счёта. Поэтому первый участник должен быть задан явно.

Коротко

Задача Иосифа Флавия описывает последовательное удаление каждого kk-го участника по кругу. Для семи человек при k=3k=3 остаётся номер 4. Полный порядок даёт симуляция, а рекурсия J(n,k)=(J(n−1,k)+k) mod nJ(n,k)=(J(n-1,k)+k)\bmod n находит последний индекс за линейное время и постоянную память. Для k=2k=2 ответ можно получить переносом первой единицы двоичной записи числа участников в конец.

Доверьте текст нейросети EssayAI

Открыть EssayAI

Бесплатно, на русском языке и без VPN

Читайте также

Формула Бине: вывод и вычисление чисел Фибоначчи

Формула Бине: вывод и вычисление чисел Фибоначчи

Разбираем формулу Бине для чисел Фибоначчи: подробный вывод через корни характеристического уравнения, пример вычисления, округление и ограничения точности в программе.

8 ноября 20268 минут
Ханойские башни и рекурсия: решение по шагам

Ханойские башни и рекурсия: решение по шагам

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

8 ноября 20268 минут
Алгоритм LZ77: сжатие с помощью ссылок назад

Алгоритм LZ77: сжатие с помощью ссылок назад

Алгоритм LZ77 на пошаговом примере: как скользящее окно находит повторы, что означают расстояние и длина, как работает перекрытие и от чего зависит размер результата.

8 ноября 20268 минут
Числа Белла: разбиения множества и формула

Числа Белла: разбиения множества и формула

Числа Белла считают разбиения множества на непустые группы. Разбираем подробные примеры, рекуррентную формулу, связь с числами Стирлинга и алгоритм вычисления.

8 ноября 20269 минут
Числа трибоначчи: формула и примеры вычисления

Числа трибоначчи: формула и примеры вычисления

Числа трибоначчи: три начальных значения, рекуррентная формула и расчёт по шагам. Как последовательность считает пути по ступенькам и как написать эффективный алгоритм.

8 ноября 20269 минут
Чётность подстановки: инверсии и знак

Чётность подстановки: инверсии и знак

Чётность подстановки через инверсии, транспозиции и циклы: пошаговый подсчёт, доказательство независимости разложения и применение в алгоритмах и определителях.

8 ноября 20268 минут