Проанализировав 4-ый способ, можно заметить, что M[i][0]=M[i][1], только M[n-1][0]=n, M[n-1][1]=0. Приходим к выводу, что первую часть списка можно опустить. Заводим одномерный массив. M:(1,2,3,4..n-1,0). Каждый элемент массива указывает на последующий, поэтому считать надо начинать с k = n - 1, т.к. (n-1)-ый элемент предшествует 0-ому. Удаление элемента можно делать по схеме: M[k]:=M[M[k]]. Переход к следующему элемент: k:=M[k]. Цикл делаем до s-1, т.к. при подсчёте мы уже стоим на 1-ом элементе.
N = 7
S = 5 |
M = (1, 2, 3, 4, 5, 6, 0) |
1. k = M[0] = 1
2. k = M[1] = 2
3. k = M[2] = 3
4. k = M[3] = 4
|
Выбывший элемент - 5 |
Удаляем:
M[4] = M[M[4]] = 6 |
|
M = (1, 2, 3, 4, 6, 6, 0) |
1. k = M[4] = 6
2. k = M[6] = 0
3. k = M[0] = 1
4. k = M[1] = 2
|
Выбывший элемент - 3 |
Удаляем:
M[2] = M[M[2]] = 4 |
| M = (1, 2, 4, 4, 6, 6, 0) |
1. k = M[2] = 4
2. k = M[4] = 6
3. k = M[6] = 0
4. k = M[0] = 1
|
Выбывший элемент - 2 |
Удаляем:
M[1] = M[M[1]] = 4 |
| M = (1, 4, 4, 4, 6, 6, 0) |
1. k = M[1] = 4
2. k = M[4] = 6
3. k = M[6] = 0
4. k = M[0] = 1
|
Выбывший элемент - 4 |
Удаляем:
M[1] = M[M[1]] = 6 |
| M = (1, 6, 4, 4, 6, 6, 0) |
1. k = M[1] = 6
2. k = M[6] = 0
3. k = M[0] = 1
4. k = M[1] = 6
|
Выбывший элемент - 7 |
Удаляем:
M[6] = M[M[6]] = 1 |
| M = (1, 6, 4, 4, 6, 6, 1) |
1. k = M[6] = 1
2. k = M[1] = 6
3. k = M[6] = 1
4. k = M[1] = 6
|
Выбывший элемент - 1 |
Удаляем:
M[6] = M[M[6]] = 6 |
| M = (1, 6, 4, 4, 6, 6, 6) |
1. k = M[6] = 6
2. k = M[6] = 6
3. k = M[6] = 6
4. k = M[6] = 6
|
Выбывший элемент - 6 |
Здесь частично решена проблема с памятью. Хотя объем необходимой памяти уменьшился всего в два раза, однако и это большое достижение, если учесть что скорость выполнения даже немного больше, чем у предыдущего способа.
Результаты тестирования программы:
для n=2000, s=2000 программа работает 47 миллисекунд,
для n=10000, s=10000 время работы - 547 миллисекунд. |
|
|