Проанализировав счет по элементам массива, мы заметили, что если S – число, до которого считать, – большое, то программа пересчитывает одни и те же элементы несколько раз.
N = 7
S = 26 |
- M = (1, 1, 1, 1, 1, 1, 1). Выбывший элемент – 5.
При S = 26 мы при пересчете получаем тот же результат, что и при S = 5.
А это остаток от деления S на N. (26 % 7 = 5) Дальше мы продолжали считать уже 6 элементов массива:
- M = (1, 1, 1, 1, 0, 1, 1). Выбывший элемент – 7.
Следовательно, в варианте 1 можно считать элементы не до S, а до h:=S % e, где e – число элементов, которое осталось удалить.
|
|
Однако этот алгоритм недостаточно быстро выполняется. Сравнительная скорость этого алгоритма зависит от вводимых чисел: при некоторых значениях скорость его практически не отличается от скорости первого алгоритма (при шаге считалки меньше количества элементов), но в некоторых случаях дает большой выигрыш в скорости (при шаге считалки намного больше количества элементов).
Всё равно эта программа медленно работает:
для n=2000, s=2000 время – 145 миллисекунд.
для n=10000, s=10000 – 2,9 секунд. |
|
|