В 67 году н.э. во время иудейско-римской войны Иосиф Флавий и сорок мятежников оказались в ловушке в пещере. Предпочтя самоубийство плену, они решили встать в круг и убивать каждого третьего из оставшихся в живых. Иосиф Флавий хотел остаться в живых и понял, где он должен стоять в кругу, чтобы остаться в живых в череде казней. Так он выжил, чтобы рассказать эту легенду.
На следующем собеседовании по алгоритмам вам может попасться алгоритмическая задача, основанная на этой легенде. По кругу стоят мятежников, пронумерованных от до . Начиная с нулевого, они убивают по кругу каждого -го оставшегося в живых. Обозначим через номер мятежника, оставшегося последним. Напишите программу, которая по данным и находит . Пример ниже показывает, что .
Ниже мы рассмотрим несколько алгоритмов для решения этой задачи. Читать вам будет гораздо интереснее, если вы перед прочтением придумаете алгоритм для этой задачи самостоятельно: во-первых, полезно потренироваться решать задачи с собеседований; во-вторых, решение гораздо лучше запоминается, если придумать его самостоятельно; в-третьих, удовольствие и уверенность, полученные от самостоятельного решения, мало с чем сравнятся =) Ниже мы приводим наглядную визуализацию и подробные описания алгоритмов.
Наивный алгоритм
Наивный способ решения задачи — промоделировать: завести массив размера , в котором отмечать, кто из мятежников всё ещё жив, и, проходя массив слева направо, отмечать каждого -го (из всё ещё живых) как убитого. Код на 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
Время работы работы этого алгоритма — : после каждого прохода по массиву количество живых мятежников уменьшается примерно в раз, поэтому понадобится примерно проходов. Ниже мы построим более простой и быстрый алгоритм.
Быстрый алгоритм
После того, как первый мятежник убит, остаётся та же самая задача: по-прежнему убивают каждого -го, но всего мятежников теперь , у них другие номера и убийства начинаются уже не с нулевого, а с мятежника с номером .
Новые и старые номера мятежников связаны такой формулой:
Это приводит к такому рекуррентному соотношению:
В свою очередь, это рекуррентное соотношение легко переделывается в рекурсивный алгоритм со временем работы . Код на Python:
def josephus(n, k):
return 0 if n == 0 else (josephus(n - 1, k) + k) % n
Ещё более быстрый алгоритм
Оказывается, что для частного случая, когда , можно построить ещё более быстрый алгоритм! Опять же, мы настоятельно рекомендуем вам попробовать придумать его самостоятельно. Решение можно найти в видео выше или в нашей интерактивной книге "Алгоритмические задачи с собеседований" (см. раздел 5.11, он доступен бесплатно; до 19 января действует промокод HABR, дающий скидку 40%).
Комментарии (25)
Parramon
11.01.2023 15:39def 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]
dolgov_vv
11.01.2023 17:30Функция pop для списка в общем случае имеет линейную временную сложность O(n). Для связных список это время поиска нужного элемента, для реализации на основе массива - время сдвижки правой части.
Так что у вас квадратичный алгоритм, т.к. внутри цикла O(n) у вас операция O(n).
alexanderskulikov Автор
11.01.2023 17:36Квадратичный алгоритм, ага. Но код нагляднее, действительно.
Parramon
11.01.2023 19:57Вы pop с remove не путаете? remove удаляет по значению, pop - по индексу.
PS по времени (машинному) я сравнил, у меня на порядок быстрее, но это ни о чем не говорит, конечно.
PPS В Питоне нет массивов....
alexanderskulikov Автор
11.01.2023 20:22А за какое время, на Ваш взгляд, работает pop?
Parramon
11.01.2023 20:43Упс. O(1) только для pop(0) и pop(-1), оказывается. Тогда извиняюсь.
alexanderskulikov Автор
11.01.2023 20:54+1А почему извиняетесь? Вы, вроде бы, и не утверждали, что этот код имеет линейную сложность. И для моделирования он более естественно выглядит. Мне как раз с него и стоило бы начать, кажется.
Parramon
12.01.2023 07:00За попытку утверждения, что pop(i) выполняется за О(1).
На самом деле, в голову приходит тогда два варианта - связанный список и чисто математическое решение. Сегодня поразмышляю.
alexanderskulikov Автор
12.01.2023 10:35Из списка можно удалять за , да, но в нём нет индексации за . Кажется, что уже при простой формулы не знают.
qw1
11.01.2023 21:10Меня в своё время больше удивило решение задачи
www.youtube.com/watch?v=wWQ9YdreY9c
Alexandroppolus
11.01.2023 21:14Кстати, если не ошибаюсь, представленный в статье наивный алгоритм работает за O(k*n), потому что на одно убиение приходится k шагов.
alexanderskulikov Автор
11.01.2023 21:15Вы имеете в виду первый алгоритм?
Alexandroppolus
11.01.2023 21:17да
alexanderskulikov Автор
12.01.2023 02:03На самом деле, на одно убийство может и больше k шагов уйти: ведь в массиве будет становиться всё больше и больше убитых (и пока мы найдём k-го живого, нам придётся пройти много индексов).
Alexandroppolus
12.01.2023 02:49Действительно. Всё ещё хуже :)
k шагов на убийство можно сохранить, если вместо массива использовать связный список и выкидывать из него элементы.
OptimumOption
12.01.2023 11:56Не совсем понимаю, почему 12й грохает 7го, хотя при ходе 12го "каждый второй" - это теоретически он сам?!
alexanderskulikov Автор
12.01.2023 12:01Вы ведь имеете в виду последнее убийство? Предпоследним убит нулевой. После этого идём по кругу и считаем: 7 — первый, 12 — второй, 7 — третий. Правильно?..
GlukKazan
Насколько я помню эту задачку из "Конкретной математики", он не только выжил сам, но и поставил на правильное место своего товарища.
alexanderskulikov Автор
На википедии так же написано, ага!
GlukKazan
Не знаю, там я не читал.