Чтобы хранить информацию о текущем состоянии цепочки считающихся, заведем массив М, в котором для каждого участника будем отмечать его состояние: 1 – живой, 0 – мертвый. В начале все элементы отметим 1 (все живые). Дальше будем считать до S по ненулевым элементам. Элемент, на котором остановились – выбывший – заменяем его на 0. Повторять эту операцию будем ровно N раз. При повторении этой операции, мы в некоторый момент придем к тому, что элемент, который должен выбыть, уже выбыл раньше, т.е. необходим переход к следующему элементу. Однако и он может быть выбывшим, а следовательно требуется еще один переход к следующему элементу. При большом количестве выбывших элементов переход к следующему элементу становится очень частым. Это и есть основная причина медленной работы этого алгоритма. О другой причине медленной работы алгоритма будет рассказано в описании второго способа.
N = 7
S = 5 |
- M = (1, 1, 1, 1, 1, 1, 1). Выбывший элемент – 5.
- M = (1, 1, 1, 1, 0, 1, 1). Выбывший элемент – 3.
- M = (1, 1, 0, 1, 0, 1, 1). Выбывший элемент – 2.
- M = (1, 0, 0, 1, 0, 1, 1). Выбывший элемент – 4.
- M = (1, 0, 0, 0, 0, 1, 1). Выбывший элемент – 7.
- M = (1, 0, 0, 0, 0, 1, 0). Выбывший элемент – 1.
- M = (0, 0, 0, 0, 0, 1, 0). Выбывший элемент – 6.
|
|
Результаты тестирования программы на компьютере с процессором
AMD Athlon II X2 245 с операционной системой Windows XP:
n=2000, s=2000: время- 1,5 секунды,
n=10000, s=10000: время- 47 секунд.
|
|
|