Задача Иосифа Флавия или считалка Джозефуса

В 1 и 2 способе мы делаем лишние действия: считаем и проверяем (1 или 0) элементы, которые уже можно и не учитывать.

Можно изменить начальный вид массива, присвоив каждому элементу его порядковый номер. Например, М = (1, 2, 3, 4, 5, 6, 7).

Досчитав по элементам массива до S, можно сдвинуть содержимое элементов массива, удалив выбывший элемент. А дальше работать с массивом из N - 1 элемента.

N = 7
S = 5
  1. M = (1, 2, 3, 4, 5, 6, 7). Выбывший элемент – 5.
  2. M = (1, 2, 3, 4, 6, 7).     Выбывший элемент – 3.
  3. M = (1, 2, 4, 6, 7).         Выбывший элемент – 2.
  4. M = (1, 4, 6, 7).             Выбывший элемент – 4.
  5. M = (1, 6, 7).                 Выбывший элемент – 7.
  6. M = (1, 6).                     Выбывший элемент – 1.
  7. M = (6).                         Выбывший элемент – 6.

Проанализировав подсчет элементов, можно заметить, что не нужно перебирать каждый элемент, а можно вычислить номер выбывающего по схеме:

  1. k = k + h - 1 – продолжаем массив влево
  2. k = k % e
где k – порядковый номер элемента,
      h – число, до чего считаем,
      e – число оставшихся элементов.

N = 7
S = 5		 M = (1, 2, 3, 4, 5, 6, 7). k = 0
k = 0 + 5 - 1 = 4
k = 4 % 7 = 4		 Выбывший элемент - 5
M = (1, 2, 3, 4, 6, 7). k = 4
k = 4 + 5 - 1 = 8
k = 8 % 6 = 2		 Выбывший элемент - 3
M = (1, 2, 4, 6, 7). k = 2
k = 2 + 5 - 1 = 6
k = 6 % 5 = 1		 Выбывший элемент - 2
M = (1, 4, 6, 7). k = 1
k = 1 + 5 - 1 = 5
k = 5 % 4 = 1		 Выбывший элемент - 4
M = (1, 6, 7). k = 1
k = 1 + 5 - 1 = 5
k = 5 % 3 = 2		 Выбывший элемент - 7
M = (1, 6). k = 2
k = 2 + 5 - 1 = 6
k = 6 % 2 = 0		 Выбывший элемент - 1
M = (6). k = 0
k = 0 + 5 - 1 = 4
k = 4 % 1 = 0		 Выбывший элемент - 6

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

Попытка создать более эффективный алгоритм по этим признакам рассматривается в 4 способе.

Результаты тестирования программы:
для n=2000, s=2000 получится результат – 87 миллисекунд.
для n=10000, s=10000 время работы – 1,1 секунда.