Алгоритмы обмена значениями переменных

Обмен значениями переменных (swap) – элементарная, но принципиально важная операция, лежащая в основе сортировок, перестановок, алгоритмов выбора и структурных преобразований массивов/графов. При внешней простоте обмен критически зависит от семантики присваивания, типов, ограничений памяти, порядка вычисления выражений и инвариантов корректности. В учебной и экзаменационной практике (ЕГЭ по информатике) умение формально описывать и доказывать корректность обмена – фундамент для задач на массивы, сортировки, комбинаторику и работы с битами.

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

1. Состояние памяти и операция обмена
   

   Пусть M – состояние памяти, отображение имён переменных в значения:

   M : Vars → Values

   Для двух различных адресуемых переменных x, y ∈ Vars, операция swap – это биекция τ_{x,y} на множестве состояний, меняющая местами M(x) и M(y) и оставляющая прочие значения неизменными:

   (τ_{x,y}(M))(x) = M(y)

   (τ_{x,y}(M))(y) = M(x)

   (τ_{x,y}(M))(z) = M(z)  для всех z ≠ x, y

   Требования корректности: (i) после выполнения x = old(y) ∧ y = old(x); (ii) отсутствуют побочные изменения других переменных; (iii) операция завершается за конечное число шагов.

2. Типы и домены значений
   Обмен корректен при совместимости типов (одно и то же множество значений или приводимые типы) и при соблюдении семантики: для арифметических приёмов – кольцевая алгебра без переполнений (или с контролируемым модулем), для XOR – битовые строки равной длины.
   

Семантика присваивания и области видимости

• Присваивание по значению: x ← expr – вычислить expr в текущем окружении, записать копию результата в ячейку x.
• Присваивание по ссылке (или параметр по ссылке): операция воздействует на исходную ячейку вызывающей стороны.
• Порядок вычисления аргументов в множественном присваивании важен: корректная семантика требует сначала вычислить все правые части, затем одновременно обновить левые.

Инвариант корректности обмена (для любой реализации):

Inv: x ⊕ y = const

где ⊕ – подходящая бинарная операция, сохраняющаяся на всех промежуточных шагах:

• для обмена через временную переменную: multiset{x, y} сохраняется;
• для арифметики: x + y (и/или x − y) сохраняется;
• для XOR: x XOR y сохраняется.

Базовые реализации обмена

1. С использованием временной переменной (надёжный стандарт)
   

   Псевдокод:

   процедура swap_temp(ссылка x, ссылка y)

       t ← x

       x ← y

       y ← t

   конец

   Сложность: время Θ(1), память Θ(1) дополнительная (одна временная ячейка).
   Достоинства: типобезопасность, отсутствие переполнений, читабельность.
   Инвариант: мультисет значений {x, y, t} на каждом шаге равен {old(x), old(y), t}; по завершении {x, y} = {old(y), old(x)}.

2. Множественное присваивание (кортежный swap)
   

   В языках с параллельной семантикой присваивания:

   (x, y) ← (y, x)

   Семантика: сначала вычислить правую кортежную часть (y, x) в старом состоянии, затем одновременно записать в (x, y).
   Эквивалентность: функционально тождественно swap_temp, часто транслируется компилятором в него.

3. Арифметические обмены (без временной переменной)
   

   Сложение/вычитание (для числовых типов без переполнения):

   x ← x + y

   y ← x − y    // стало old(x)

   x ← x − y    // стало old(y)

   или сумма/разность с минимизацией переприсваиваний:

   s ← x + y

   y ← s − y    // old(x)

   x ← s − y    // old(y)

   Ограничения: риск переполнений, требования к замкнутости операции, уязвимость к нецелым типам/NaN. В учебных задачах не рекомендуется без оговорки «нет переполнений».

4. Побитовый XOR (для целых без знакового UB)
   

   x ← x XOR y

   y ← x XOR y    // old(x)

   x ← x XOR y    // old(y)

   Свойства: не требует временной переменной, сохраняет инвариант x XOR y.
   Ограничения:

   • x и y должны ссылаться на разные ячейки (иначе зануление).

   • Должна быть единая битность и представление (без UB).

   • Читабельность ниже, чем у swap_temp.

5. Обмен ссылочных значений (указатели/ссылки)
   

   В языках со ссылочной семантикой, когда нужно поменять содержимое объектов по адресам (а не сами ссылки):

   процедура swap_ref(ссылка x, ссылка y)

       t ← значение_по(x)

       значение_по(x) ← значение_по(y)

       значение_по(y) ← t

   конец

   Важно: корректно различать «обмен указателей» (меняем адреса) и «обмен содержимого по адресам».

Расширенные приёмы

1. Обмен элементов массива
   

   процедура swapA(ссылка A: массив, i, j: цел)

       треб: 1 ≤ i, j ≤ |A|

       если i = j то вернуть

       t ← A[i]; A[i] ← A[j]; A[j] ← t

   конец

   Инвариант: мультисет элементов массива не меняется; меняются только позиции i и j.

2. Множественные обмены и циклические перестановки
   

   Циклическая ротация трёх переменных x, y, z:

   (x, y, z) ← (z, x, y)   // цикл вправо

   Через временную:

   t ← z; z ← y; y ← x; x ← t

   Общее правило: для перестановки π на k позициях разложите π в циклы и применяйте поцикловые ротации; число перемещений = k − #циклов.

3. Обмен структур/записей
   Если типы – записи/структуры, корректнее использовать присваивание всего объекта (язык обязан корректно копировать поля), либо move-семантику (перемещение) там, где она определена.
   

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

1. Совместимость типов. Обмен допустим, если type(x) = type(y) или предусмотрен безопасный явный каст: x ← cast(type(x), y) и наоборот.
2. Отсутствие переполнений. Арифметические методы требуют гарантии, что промежуточные значения лежат в допустимом диапазоне.
3. Различные адреса. Для XOR/арифметики переменные должны адресовать разные ячейки: &x ≠ &y.
4. Порядок вычисления. Для кортежного присваивания все правые части вычисляются до записи в левые.
5. Исключения/ошибки. Обмен – атомарная операция на уровне логики; при реальных исключениях (ошибка копирования) используйте безопасные примитивы языка (например, std::swap с гарантией отсутствия утечек).
6. Неизменяемые/константные объекты. Если x или y – константы/литералы/результаты выражений, обмен невозможен – требуется изменяемая память.
7. Побочные эффекты в выражениях. Правые части не должны иметь побочных эффектов, зависящих от порядка (особенно в кортежном присваивании).

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

С временной переменной (рекомендуется): 
t ← x;  x ← y;  y ← t

Кортежный swap (если язык поддерживает):  
(x, y) ← (y, x)

Арифметический (при отсутствии переполнений):  
x ← x + y

y ← x − y

x ← x − y

XOR-swap (только для целых, &x ≠ &y):

x ← x XOR y

y ← x XOR y

x ← x XOR y

Массив:
t ← A[i];  A[i] ← A[j];  A[j] ← t

Ротация тройки:
(x, y, z) ← (z, x, y)

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

• Переполнение в арифметике. Если x + y выходит за диапазон – результат неопределён. → Используйте swap_temp или большие типы/проверки.
• Самообмен для XOR. Если x и y указывают на одну ячейку – после x ← x XOR x получим 0. → Добавляйте проверку если адреса равны → вернуть.
• Смешение обмена ссылок и содержимого. Замена указателей ≠ обмен данных по адресам. → Чётко фиксируйте семантику.
• Порядок вычисления в (x, y) ← (y, f(x)). Если f использует уже изменённый x – получите ошибку. → Гарантируйте вычисление правых частей до записи.
• Константность/иммутабельность. Нельзя присвоить в const. → Убирайте константность только при необходимости и законно.
• Нарушение инварианта мультисета. Любое «улучшение» с изменением других переменных ломает корректность. → Поддерживайте строгий инвариант.

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

• Массивы и сортировки. Любая обменная сортировка (пузырёк, выбор, быстрая сортировка) опирается на корректный swap.
• Битовые операции. XOR-swap тренирует работу с таблицами истинности и законами булевой алгебры.
• Псевдокод и инварианты. Доказательство корректности обмена – типовой пример обоснования цикла/процедуры.
• Сложность и память. Сравнение реализаций по дополнительной памяти и устойчивости – часть анализа алгоритмов.
• Граничные случаи. Проверки i = j, &x = &y, «все равны» – культура работы с краями.

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

Упражнение 1. Докажите корректность swap с временной переменной
Условие. Дана процедура:

t ← x

x ← y

y ← t

Докажите, что после её выполнения x = old(y) и y = old(x) и никакие другие переменные не изменились.

Решение. Пусть старое состояние M₀, новое – M₁. После первой строки t = M₀(x), x, y неизменны. Вторая строка присваивает x := M₀(y). Третья – y := M₀(x) через сохранённое t. Остальные переменные не затрагиваются. Следовательно, M₁(x)=M₀(y), M₁(y)=M₀(x), а для z ≠ x, y, t – M₁(z)=M₀(z). QED. 

Упражнение 2. Найдите ошибку в XOR-обмене
Условие. Рассмотрите фрагмент:

если &x = &y то

    x ← x XOR y

иначе

    x ← x XOR y

    y ← x XOR y

    x ← x XOR y

все

Корректен ли он? Обоснуйте.

Решение. При &x = &y первая строка даёт x ← x XOR x = 0 → значение теряется. Правильно: при &x = &y ничего не делать:

если &x = &y то вернуть

иначе

    x ← x XOR y

    y ← x XOR y

    x ← x XOR y

все

Только так сохраняется инвариант x XOR y. 

Упражнение 3. Арифметический обмен и переполнение
Условие. Пусть x и y – 32-битные знаковые целые. Применили:

x ← x + y

y ← x − y

x ← x − y

Приведите условие, при котором переполнение невозможно, и объясните, почему этот метод ненадёжен в общем случае.

Решение. Переполнение исключено, если x + y принадлежит диапазону [-2³¹, 2³¹−1]. Например, при |x|,|y| ≤ 10⁶ метод безопасен. В общем случае гарантировать отсутствие переполнений нельзя (особенно при суммах, близких к границам диапазона). Поэтому арифметический обмен не рекомендуется без явной проверки или использования более широкого типа. 

Упражнение 4. Обмен в массиве: доказательство инварианта перестановочной сортировки
Условие. В сортировке выбором на шаге i меняют местами A[i] и A[pos], где pos – индекс минимального на суффиксе A[i..n]. Докажите, что после обмена префикс A[1..i] отсортирован по неубыванию.
Решение. По индукции: предположим, A[1..i−1] отсортирован и содержит i−1 наименьших элементов. На шаге находим минимум суффикса A[i..n] и ставим его на позицию i обменом. Тогда A[1..i] содержит i наименьших элементов в порядке неубывания (минимум суффикса не меньше всех в префиксе и не больше любого на суффиксе). Инвариант сохранён. 

Упражнение 5. Кортежный swap и порядок вычисления
Условие. Рассмотрите кортежное присваивание:
(x, y) ← (y, f(x))
Предположим, f – чистая функция. При какой семантике операция корректна и чему равны итоговые x и y?
Решение. Корректно при параллельной семантике кортежного присваивания: сначала вычисляются обе правые части в старом состоянии: R₁ = y_old, R₂ = f(x_old), затем одновременно записываются: x := R₁, y := R₂. Итог: x = y_old, y = f(x_old). При последовательной семантике (сначала x ← y) вторая правая часть могла бы зависеть от уже изменённого x, что ломает корректность.

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

• Типы совместимы; для арифметики проверены границы/переполнения.
• Для XOR/арифметики гарантировано &x ≠ &y.
• Псевдокод фиксирует порядок вычисления правых частей для кортежного присваивания.
• В массивах корректны индексы и обработан случай i = j.
• Инвариант корректности обмена сформулирован и проверен.
• Нет побочных изменений других переменных/элементов.
• В задачах ЕГЭ аргументация опирается на инварианты и строгое следование формальным правилам.

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

1. Сформулируйте обмен как биекцию над состояниями памяти и укажите необходимые свойства корректности.
2. Чем кортежный swap отличается от поэтапного с временной переменной на уровне семантики?
3. Почему XOR-обмен недопустим при &x = &y и как это обнаружить?
4. В чём риск арифметического обмена на целых и как его нивелировать?
5. Как доказать инвариант сортировки выбором, в основе которой лежит обмен?

Заключение

Операция обмена – не просто «три строки кода», а строгое преобразование состояния, требующее учёта типов, семантики присваивания, инвариантов и краевых случаев. В учебной и экзаменационной практике корректный, типобезопасный и читаемый обмен – кирпичик любой перестановочной процедуры, от сортировок до генераторов комбинаций. Следуйте изложенным правилам: используйте временную переменную или кортежное присваивание как стандарт, прибегайте к арифметике/XOR только при формально гарантированных условиях. Это повысит надёжность решений и качество аргументации на ЕГЭ.