Последовательность Иосифа
Описание: В кругу стоят люди, ожидающие казни. Отсчет начинается в некоторой точке круга и продолжается по кругу в фиксированном направлении. На каждом шаге пропускается определенное количество людей и выполняется следующий человек. Исключение происходит по кругу (который становится все меньше и меньше по мере удаления казненных людей), пока не останется только последний человек, которому предоставлена свобода.
Я гуглил этоИосиф Флавий и хит из Википедии дает мне решение для динамического программирования:f(n,k)=((f(n-1,k)+k-1) mod n)+1, with f(1,k)=1
, но это только дает последнего выжившего. Как я могу получить последовательность людей казненных? Скажем, p (5, 3) = {3,1,5,2,4}.
Кроме того, есть лиO(nlogn)
решение вместоO(nk)
один?