Реверсирование строк и массивов

Реверсирование (обращение) последовательности – фундаментальная операция обработки данных, сводящаяся к перестановке элементов в обратном порядке. Она встречается в развороте подмассивов при сортировке (в частности, в «пирожковой» сортировке), в преобразованиях строк, в алгоритмах разворота стека/очереди, при ускоренном циклическом сдвиге «три-рёвёрсом», а также в кодировании/декодировании данных.
Для ЕГЭ по информатике реверс – идеальная площадка для тренировки инвариантов цикла, аккуратной индексации, оценок сложности, работы с массивами и строками, а также корректной обработки краевых случаев.

Формальная модель

1. Объект и отображение
   

   Пусть дана конечная последовательность

   A : {1,2,…,n} → X

   (массив или строка над алфавитом X). Операция реверса – биекция Rev_n:

   Rev_n(i) = n − i + 1,      1 ≤ i ≤ n,

   а новая последовательность B определяется как

   B[i] = A[Rev_n(i)] = A[n − i + 1].

   Свойства:
   (1) Rev_n – инволюция: Rev_n(Rev_n(i)) = i.
   (2) Мультисет значений сохраняется: {B[i]} = {A[i]}.
   (3) Реверс подотрезка [ℓ..r] (1 ≤ ℓ ≤ r ≤ n) определяется аналогично:

   B[i] =

     A[i],                        если i ∉ [ℓ..r];

     A[ℓ + r − i],                если i ∈ [ℓ..r].

2. Целевая модель вычислений
   В классической (RAM) модели допускается доступ к A[i] за O(1) и обмен двух элементов за O(1). Цель – реализовать Rev_n за линейное время Θ(n) и, по возможности, O(1) дополнительной памяти (in-place).
   

Корректность: инварианты, вариант завершения

1. Двухуказательный алгоритм (итерационный in-place)
   

   Основная идея: симметричные обмены A[L] ↔ A[R] для пар индексов, удовлетворяющих L + R = n + 1, с поэтапным сдвигом указателей к центру.

   Псевдокод (1-индексация):

   процедура reverse(A: массив, n: цел)

       L ← 1; R ← n

       пока L < R делай

           обмен(A[L], A[R])     // swap

           L ← L + 1

           R ← R − 1

       все

   конец

   Инвариант Inv(k) после k обменов:
   (а) Для всех i < L выполнено B[i] = A₀[n − i + 1].
   (б) Для всех i > R выполнено B[i] = A₀[n − i + 1].
   (в) Мультисет значений внутри [L..R] совпадает с исходным A₀[L..R].

   Здесь A₀ – исходное состояние массива.
   База: до первого обмена свойства тривиальны.
   Переход: на каждой итерации пара (L, R) удовлетворяет L + R = n + 1; обмен ставит корректные элементы на позиции L и R. Сдвиг указателей сохраняет (а) и (б), а (в) выполняется, так как внутри окна меняется только мультисет.
   Завершение: вариант R − L + 1 убывает на 2 ≥ 1; цикл останавливается при L ≥ R, когда все позиции удовлетворяют определению реверса.

   Сложность: Θ(n) времени, Θ(1) памяти.

2. Рекурсивная версия (для методического разбора)
   

   Рекурсивно реверсируем крайние элементы и подзадачу [L+1..R−1]:

   процедура reverse_rec(A, L, R)

       если L ≥ R то вернуть

       обмен(A[L], A[R])

       reverse_rec(A, L+1, R-1)

   конец

   Инвариант аналогичен; глубина стека Θ(n), следовательно, дополнительная память – Θ(n) кадров (на практике – Θ(n) вызовов). Для ЕГЭ обычно предпочитается итерационный вариант.

3. Реверс подмассива
   

   Для [ℓ..r] запускаем двухуказательный алгоритм на окне (остальные элементы не трогаются). Корректность следует из тех же инвариантов на сузенном индексе.

Алгоритмические стратегии и расширения

1. «Три-рёвёрса» для циклического сдвига
   

   Для циклического сдвига массива на k позиций вправо (k = k mod n) классический приём:

   reverse(A, 1, n)                 // глобальный реверс

   reverse(A, 1, k)                 // реверс первых k

   reverse(A, k+1, n)               // реверс оставшихся

   Доказательство: после первого реверса «хвост» оказывается в начале, вторые два реверса возвращают оба блока в правильном порядке с сохранением циклической структуры. Время Θ(n), память Θ(1).

2. Реверс как частный случай перестановки
   

   Реверс – перестановка, раскладывающаяся на независимые 2-циклы: (1 n)(2 n−1)…. Это объясняет, почему достаточно попарных обменов, и задаёт нижнюю границу: в сравнительной модели требуются хотя бы ⌊n/2⌋ обменов.

3. Блочный реверс и выравнивание памяти
   

   При работе с широкими типами (структуры, 64-битные элементы) имеет смысл обменивать блоки указателями/перемещением целых слов, соблюдая выравнивание – это инженерная оптимизация без изменения асимптотики.

4. Реверс строк: кодировки и графемы 
   

   Для ASCII/ANSI строк (1 байт на символ) реверс аналогичен массиву байтов. Для UTF-8/UTF-16 простой обмен байтов/кодовых единиц может искусственно разрушить символы (разрез много-байтовой последовательности) и/или сцепленные графемные кластеры (например, буква + диакритика, флажки-эмодзи).
   Подходы:

   • Реверс по кодовым точкам Unicode (предварительно декодировать в массив «runes»/code points).

   • Реверс по графемным кластерам (нормально для пользовательского интерфейса): предварительно разложить строку на кластеры, затем применить двухуказательный алгоритм к массиву кластеров.
     Для ЕГЭ обычно достаточно модели «строка как массив символов фиксированной ширины».

Правила корректности и безопасной реализации

1. Единая индексация. Зафиксируйте 1- или 0-индексацию, используйте её везде.
2. Границы окна. При реверсе [ℓ..r] предварительно проверьте 1 ≤ ℓ ≤ r ≤ n.
3. Обмен как атомарная операция. Независимо от типа – либо через временную переменную, либо кортежно (A[L], A[R]) ← (A[R], A[L]).
4. Строки и кодировки. Для UTF-8 реверсируйте массив кодовых точек либо графем, а не байтов.
5. Идемпотентность. Повторный реверс возвращает исходную последовательность: reverse(reverse(A)) = A. Это служит удобной проверкой для тестов.
6. Асимптотика. Базовый алгоритм должен иметь Θ(n) времени, Θ(1) памяти (кроме рекурсии).
7. Побочные эффекты. Процедура реверса не должна создавать/удалять элементы или изменять внешние структуры, кроме целевого окна.

Мини-шпаргалка 

Двухуказательный реверс целого массива (0-индексация):

процедура reverse(A: массив, n: цел)

    L ← 0; R ← n − 1

    пока L < R делай

        обмен(A[L], A[R])

        L ← L + 1

        R ← R − 1

    все

конец

Реверс подмассива [ℓ..r] (1-индексация):

процедура reverse_range(A, ℓ, r)

    треб: 1 ≤ ℓ ≤ r ≤ |A|

    L ← ℓ; R ← r

    пока L < R делай

        обмен(A[L], A[R])

        L ← L + 1

        R ← R − 1

    все

конец

Циклический сдвиг вправо на k через три реверса (1-индексация):

процедура rotate_right(A, n, k)

    k ← k mod n

    если k = 0 то вернуть

    reverse_range(A, 1, n)

    reverse_range(A, 1, k)

    reverse_range(A, k+1, n)

конец

Инвариант двухуказательного реверса (для отчёта/доказательства):

Inv(L,R): ∀i < L: A[i] = A₀[n − i + 1]  и ∀i > R: A[i] = A₀[n − i + 1]

Вариант: R − L + 1

Типичные ошибки и профилактика

• Неверные границы цикла. Ошибка: пока L ≤ R с обменом – дублирование центрального элемента при нечётном n. Правильно: пока L < R.
• Смешение индексаций. Начали с 1-индексации, а формулу взяли для 0-; итог – сдвиг на 1 и выход за границы. Закрепляйте соглашение в преамбуле.
• Ошибки в окне [ℓ..r]. Отсутствие проверки ℓ ≤ r ведёт к пустой/отрицательной длине. Добавляйте предусловия.
• Реверс строк по байтам в UTF-8. Разрушение многобайтовых символов. Решение: декодировать в массив кодовых точек/кластеров.
• Рекурсия без учёта стека. На больших n переполнение стека. Для экзамена – итерация предпочтительна.
• Обмен без временной переменной с арифметикой/XOR. Нечитаемо и рискованно; используйте стандартный swap. 

Связь с подготовкой к ЕГЭ по информатике

• Инварианты и доказательства: формальный инвариант двухуказательного цикла – типовой ответ в разборе.
• Асимптотика: различение Θ(n) и Θ(n²) (наивный «сдвиг-вставка»), анализ памяти.
• Массивы и строки: аккуратная индексация, проверка границ, подотрезки.
• Композиция алгоритмов: реверс как кирпичик циклического сдвига, разворота стеков, разворота слов.
• Псевдокод: чистые процедуры без I/O, чёткие предусловия/постусловия – повышают оценку.

Пять упражнений – с подробными решениями

Упражнение 1. Доказательство корректности двухуказательного реверса
Условие. Сформулируйте инвариант и вариант завершения для процедуры:

L ← 1; R ← n

пока L < R делай

    обмен(A[L], A[R])

    L ← L + 1

    R ← R − 1

все

Решение.
Инвариант Inv(L,R): для всех i < L и i > R элементы уже стоят в обратном порядке: A[i] = A₀[n − i + 1]. Вариант – длина окна R − L + 1, убывающая на 2 каждую итерацию; при L ≥ R окно пусто/из одного элемента, значит реверс завершён корректно. QED.

Упражнение 2. Реверс подотрезка и сравнение с полным реверсом
Условие. Дан массив A длины n=10. Выполнен reverse_range(A, 3, 7). Сколько пар элементов будет обменено? Укажите индексы пар.
Решение. Длина окна r − ℓ + 1 = 5. Потребуются ⌊5/2⌋ = 2 обмена пар: (3,7) и (4,6). Индекс 5 остаётся на месте (середина окна). Вне окна элементы не меняются.

Упражнение 3. Циклический сдвиг через три реверса
Условие. Докажите, что процедура rotate_right(A, n, k) из §5 выполняет корректный циклический сдвиг вправо на k.
Решение.

Обозначим исходный массив как конкатенацию A = XY, где |Y| = k, |X| = n − k, а желаемый результат – YX.

1. reverse(XY) = reverse(Y) reverse(X) (свойство реверса конкатенации).
2. Далее reverse(reverse(Y)) = Y, reverse(reverse(X)) = X.
3. Выполнив поочерёдно reverse(Y), reverse(X), получим YX. Позиции элементов совпадают с циклическим сдвигом вправо на k. Время – Θ(n). QED.

Упражнение 4. Реверс строки в UTF-8: где ошибка?

Условие. Строку в UTF-8 реверсируют, меняя местами байты s[L] и s[R]. Пример строки: A«ё»B (буква ё – двухбайтовая в UTF-8). Что может пойти не так, и как исправить?
Решение. Меняя байты, мы можем порвать многобайтовую последовательность, получив невалидный UTF-8. Исправление:
(1) Декодировать в массив кодовых точек (или графемных кластеров),
(2) выполнить двухуказательный реверс на уровне этих единиц,
(3) закодировать обратно в UTF-8.

Упражнение 5. Сложность и нижняя граница

Условие. Покажите, что любой in-place алгоритм реверса, основанный на обменах, должен выполнить не менее ⌊n/2⌋ обменов.
Решение. Реверс – перестановка, разложенная в ⌊n/2⌋ независимых 2-циклов: (1 n)(2 n−1)…. Чтобы реализовать каждый 2-цикл, требуется по крайней мере один обмен. Следовательно, нижняя граница – ⌊n/2⌋. Алгоритм из §2.1 достигает её, значит оптимален по числу обменов.

Практические шаблоны (псевдокод в «экзаменационном» стиле)

Реверс слов в строке, не меняя порядок букв в словах (0-индексация):

процедура reverse_words(S: массив символов, n: цел)

    // общий реверс строки

    reverse(S, n)

    // реверс каждого слова обратно

    i ← 0

    пока i < n делай

        пока i < n и S[i] = ' ' делай i ← i + 1 все

        j ← i

        пока j < n и S[j] ≠ ' ' делай j ← j + 1 все

        reverse_range(S, i+1, j)  // если reverse_range 1-индексная, аккуратно сдвинуть

        i ← j

    все

конец

(В задачах ЕГЭ достаточно идеи: «общий реверс, затем реверс каждого слова».)

Чек-лист самопроверки

• Зафиксирована индексация и корректно реализованы границы цикла (L < R).
• Для подотрезка проверены условия 1 ≤ ℓ ≤ r ≤ n.
• В документации прописан инвариант и вариант завершения.
• Для строк с многобайтовыми символами выбран уровень реверса (кодовые точки/графемы).
• Оценены время Θ(n) и память Θ(1) (или стек для рекурсии).
• Реализация swap безопасна и читабельна (через временную переменную/кортеж).
• Для сдвига на k применён «три-рёвёрса» с k mod n.

Контрольные вопросы

1. Сформулируйте реверс как биекцию индексов и докажите, что он – инволюция.
2. Запишите инвариант двухуказательного реверса и объясните, зачем нужен вариант завершения.
3. Почему «три-рёвёрса» реализует циклический сдвиг?
4. Что сломается при реверсе UTF-8-строки по байтам и как это исправить?
5. Почему нижняя граница числа обменов равна ⌊n/2⌋?

Заключение

Реверсирование – небольшая по коду, но содержательная по методологии тема: на её примере последовательно отрабатываются инварианты, варианты и границы, а также аккуратная работа с индексами, окнами и представлениями данных. В связке с ЕГЭ это умение напрямую транслируется в качественные решения задач на массивы и строки, в корректные доказательства и верные оценки сложности. Придерживайтесь изложенных правил и шаблонов – и реверс станет надёжным строительным блоком для более сложных алгоритмов.