Задача
Сама задача відома з прадавніх часів під назвою “задача Йосифа Флавія“. На співбесідах її можна почути в такому вигляді.
100 воїнів вишикувалися у замкнене коло. У першого воїна і лише у нього є меч. Він цим мечем вбиває наступного за ним (тобто другого) і передає меч наступному ще не вбитому (тобто третьому). Той хто отримує меч так само вбиває наступного і передає меч далі. І так доки не лишиться лише один живий воїн. Питання – який номер залишиться в живих.
В більш загальному випадку кількість воїнів може бути довільною так само як порядок вбивств.
Рішення
Наївним рішенням буде створити у пам’яті колекцію флагів для кожного воїна і по колу позначати вбитих доки не лишиться один не позначений елемент. Таке рішення звісно буде працювати, але воно вимагатиме додаткової пам’яті і процесорного часу щоб зробити всі ітерації.
Щоб знайти номер воїна який вижив дешевшим способом можна спробувати наступне. Спочатку з’ясуємо для якої кількості воїнів перший виживе гарантовано. Це звісно буде парна кількість. Тепер щоб гарантувати що перший воїн виживе на наступні і наступній ітерації і так далі нам теж треба щоб кількість елементів на кожній з них була парною. Таким чином якщо кількість воїнів дорівнює ступеню двійки то виживе перший воїн.
Для довільної кількості елементів N знайдемо найбільший ступінь двійки X такий що X <= N (це можна зробити, наприклад, модифікувавши алгоритм з Знайти найближчий ступінь двійки). Індекс з якого коло з N елементів перетвориться на коло з елементів кількість яких дорівнюватиме ступеню двійки і буде нашою відповіддю. Тобто нам треба знайти скільки елементів M треба пройти (половину з яких буде “вбито”) таких що M/2 + (N-M)=X. Просте рівняння з якого знаходимо що M=(N-X)*2.
Тобто для 100 воїнів (N=100) найближчим ступенем двійки не більшим за 100 буде 64 (X=64) і таким чином залишиться в живих 73-й воїн (M=(100-64)*2=72).