|
|
От: | UgN | |
| Дата: | 01.11.02 11:49 | ||
| Оценка: | 61 (4) | ||
.IK>Задача.
IK>Дано: массив на N элементов.
IK>Требуется: сдвинуть массив циклически на K позиций вправо.
IK>K и N — любые положительные числа (разумные).
IK>Доп.условия:
IK>1. Дополнительную память не выделять (кроме нескольких временных переменных).
IK>То есть не пропорционально K или N.
IK>2. Рекурсией в глубину K или N не пользоваться.
IK>3. Алгоритм должен обладать сложностью не хуже o(N).
IK>Пример:
IK>Для массива 1 2 3 4 5 6 7 при сдвиге на 3 позиции должно получиться
IK>5 6 7 1 2 3 4.
Принцип такой.
Дано:
1 2 3 4 5 6 7
Меняем попарно 1 - 4, 2 - 3, 5 - 7
4 3 2 1 7 6 5
Меняем попарно 4 - 5, 3 - 6, 2 - 7
5 6 7 1 2 3 4
Все.
Легко формализуется.
Для K < N
Берешь с конца K + 1 элемент, получаешь 2 части маасива
Разворачиваешь их попарными обменами
Получившийся массив целиком разворачиваешь еще раз.