TUZ_2-01_ Вычисление порядкового номера в задаче Иосифа Флавия
2.01_ Вычисление порядкового номера в задаче Иосифа Флавия
Задача Иосифа Флавия – широко известная в информатике теоретическая задача. Суть ее заключается в следующем: в круг выстраивается n человек.Из стоящих выбирается k-й человек, который покидает круг. Далее покинувшие круг не участвуют в процессе подсчета, а последний оставшийся считается победителем.
Цель состоит в том, чтобы разработать функцию, которая принимает заданные значения n и k и возвращает порядок, в котором игроки будут покидать круг. Здесь n представляет общее количество людей, а k – количество пропусков. Важно отметить, что k может быть меньше, равно или даже больше n.
Например, рассмотрим рис. 2.1, где в круг встали пять человек. Для k = 2 и n = 5 определите, в каком порядке они будут покидать круг.
Пусть ex – это массив людей, покинувших круг. Поскольку k = 2, то сразу после начала игры выбирается x
2 и исключается из круга; ex = [2].
Далее выполняется k шагов по кругу и выбывает 2 + 2 = 4-й участник, т. е. x
4; ex = [2, 4]. И снова выполняется k шагов, в результате выбывает участник x
1; ex = [2, 4, 1]. Обратите внимание, что при пересечении конца массива происходит переход в его начало (как по кругу), поэтому на предыдущем шаге выбор пал на игрока x
1. Теперь в круге остаются x
3 и x
5. После выполнения k шагов из круга выбывает x
5, соответственно, ex = [2, 4, 1, 5]. Последний игрок, оставшийся в круге, – x
3, поэтому искомый порядок исключения из круга ex = [2, 4, 1, 5, 3].
В табл. 2.1 показаны некоторые ожидаемые результаты (содержимое массива ex) для разных значений k и n.
| Таблица 2.1. Некоторые ожидаемые результаты для разных значений k и n |
| n, k |
Ожидаемый результат |
| 6, 2 |
2, 4, 6, 3, 1, 5 |
| 5, 2 |
2, 4, 1, 5, 3 |
| 8, 8 |
8, 1, 3, 6, 5, 2, 7, 4 |
| 3, 9 |
3, 1, 2 |
| 4, 3 |
3, 2, 4, 1 |