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

На следующем собеседовании по алгоритмам вам может попасться алгоритмическая задача, основанная на этой легенде. По кругу стоят nмятежников, пронумерованных от 0до n-1. Начиная с нулевого, они убивают по кругу каждого k-го оставшегося в живых. Обозначим через \operatorname{Josephus}(n,k) номер мятежника, оставшегося последним. Напишите программу, которая по данным nи kнаходит \operatorname{Josephus}(n,k). Пример ниже показывает, что \operatorname{Josephus}(13,3)=12.

Ниже мы рассмотрим несколько алгоритмов для решения этой задачи. Читать вам будет гораздо интереснее, если вы перед прочтением придумаете алгоритм для этой задачи самостоятельно: во-первых, полезно потренироваться решать задачи с собеседований; во-вторых, решение гораздо лучше запоминается, если придумать его самостоятельно; в-третьих, удовольствие и уверенность, полученные от самостоятельного решения, мало с чем сравнятся =) Ниже мы приводим наглядную визуализацию и подробные описания алгоритмов.

Наивный алгоритм

Наивный способ решения задачи — промоделировать: завести массив размера n, в котором отмечать, кто из мятежников всё ещё жив, и, проходя массив слева направо, отмечать каждого k-го (из всё ещё живых) как убитого. Код на Python:

def josephus(n, k):
    alive = [True] * n
    num_survivors, current_position, index = n, 0, 0
    while num_survivors:
        if alive[current_position]:
            index += 1
            if index == k:
                num_survivors = num_survivors - 1
                if not num_survivors:
                    return current_position
                else:
                    alive[current_position] = False
                    index = 0
        current_position = (current_position + 1) % n

Время работы работы этого алгоритма — O(n\log n): после каждого прохода по массиву количество живых мятежников уменьшается примерно в k/(k-1)раз, поэтому понадобится примерно \log_{k/(k-1)}nпроходов. Ниже мы построим более простой и быстрый алгоритм.

Быстрый алгоритм

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

Новые и старые номера мятежников связаны такой формулой:

(\text{старый номер}-k) \bmod n=\text{новый номер}

Это приводит к такому рекуррентному соотношению:

(\operatorname{Josephus}(n,k)-k) \bmod n=\operatorname{Josephus}(n-1,k)

В свою очередь, это рекуррентное соотношение легко переделывается в рекурсивный алгоритм со временем работы O(n). Код на Python:

def josephus(n, k):
    return 0 if n == 0 else (josephus(n - 1, k) + k) % n

Ещё более быстрый алгоритм

Оказывается, что для частного случая, когда k=2, можно построить ещё более быстрый алгоритм! Опять же, мы настоятельно рекомендуем вам попробовать придумать его самостоятельно. Решение можно найти в видео выше или в нашей интерактивной книге "Алгоритмические задачи с собеседований" (см. раздел 5.11, он доступен бесплатно; до 19 января действует промокод HABR, дающий скидку 40%).

Комментарии (25)


  1. GlukKazan
    11.01.2023 12:43

    Насколько я помню эту задачку из "Конкретной математики", он не только выжил сам, но и поставил на правильное место своего товарища.


    1. alexanderskulikov Автор
      11.01.2023 12:45

      На википедии так же написано, ага!


      1. GlukKazan
        11.01.2023 14:25

        Не знаю, там я не читал.


  1. just-a-dev
    11.01.2023 12:58
    +1

    Рекурсивный алгоритм линейной глубины - не очень хорошая идея..


    1. alexanderskulikov Автор
      11.01.2023 13:00

      Ага. Но в одну строчку зато =)


  1. Alexandroppolus
    11.01.2023 13:33
    +2

    Для небольших k это дело оптимизируется до O(k * ln(n))

    https://e-maxx.ru/algo/joseph_problem


    1. alexanderskulikov Автор
      11.01.2023 15:39

      Здорово, спасибо!


  1. Parramon
    11.01.2023 15:39

    def josephus2(n, k):
        alive = [i for i in range(n)]
        i = 0
        while len(alive) > 1:
            i = (i + k - 1) % n
            alive.pop(i)
            n -= 1
        return alive[0]


    1. dolgov_vv
      11.01.2023 17:30

      Функция pop для списка в общем случае имеет линейную временную сложность O(n). Для связных список это время поиска нужного элемента, для реализации на основе массива - время сдвижки правой части.

      Так что у вас квадратичный алгоритм, т.к. внутри цикла O(n) у вас операция O(n).


      1. alexanderskulikov Автор
        11.01.2023 17:36

        Квадратичный алгоритм, ага. Но код нагляднее, действительно.


      1. Parramon
        11.01.2023 19:57

        Вы pop с remove не путаете? remove удаляет по значению, pop - по индексу.

        PS по времени (машинному) я сравнил, у меня на порядок быстрее, но это ни о чем не говорит, конечно.

        PPS В Питоне нет массивов....


        1. alexanderskulikov Автор
          11.01.2023 20:22

          А за какое время, на Ваш взгляд, работает pop?


          1. Parramon
            11.01.2023 20:43

            Упс. O(1) только для pop(0) и pop(-1), оказывается. Тогда извиняюсь.


            1. alexanderskulikov Автор
              11.01.2023 20:54
              +1

              А почему извиняетесь? Вы, вроде бы, и не утверждали, что этот код имеет линейную сложность. И для моделирования он более естественно выглядит. Мне как раз с него и стоило бы начать, кажется.


              1. Parramon
                12.01.2023 07:00

                За попытку утверждения, что pop(i) выполняется за О(1).

                На самом деле, в голову приходит тогда два варианта - связанный список и чисто математическое решение. Сегодня поразмышляю.


                1. alexanderskulikov Автор
                  12.01.2023 10:35

                  Из списка можно удалять за O(1), да, но в нём нет индексации за O(1). Кажется, что уже при k=3простой формулы не знают.


  1. qw1
    11.01.2023 21:10

    Меня в своё время больше удивило решение задачи
    www.youtube.com/watch?v=wWQ9YdreY9c


  1. Alexandroppolus
    11.01.2023 21:14

    Кстати, если не ошибаюсь, представленный в статье наивный алгоритм работает за O(k*n), потому что на одно убиение приходится k шагов.


    1. alexanderskulikov Автор
      11.01.2023 21:15

      Вы имеете в виду первый алгоритм?


      1. Alexandroppolus
        11.01.2023 21:17

        да


        1. alexanderskulikov Автор
          12.01.2023 02:03

          На самом деле, на одно убийство может и больше k шагов уйти: ведь в массиве будет становиться всё больше и больше убитых (и пока мы найдём k-го живого, нам придётся пройти много индексов).


          1. Alexandroppolus
            12.01.2023 02:49

            Действительно. Всё ещё хуже :)

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


            1. alexanderskulikov Автор
              12.01.2023 02:54

              Ага! =)


  1. OptimumOption
    12.01.2023 11:56

    Не совсем понимаю, почему 12й грохает 7го, хотя при ходе 12го "каждый второй" - это теоретически он сам?!


    1. alexanderskulikov Автор
      12.01.2023 12:01

      Вы ведь имеете в виду последнее убийство? Предпоследним убит нулевой. После этого идём по кругу и считаем: 7 — первый, 12 — второй, 7 — третий. Правильно?..