Обработка матрицы

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

Формальная модель и индексация

Пусть задана матрица A размера m×n с нумерацией с нуля:

A[i][j],  где  0 ≤ i < m  и  0 ≤ j < n.

• i – индекс строки (row),

• j – индекс столбца (column).

1. Диагонали (для квадратных матриц, m = n = n)
   

   Главная диагональ:      i = j

   Побочная диагональ:     i + j = n - 1

   Верхний треугольник:    i < j

   Нижний треугольник:     i > j

   Эти предикаты часто используются в ЕГЭ для выборки подмножеств элементов.

2. Адресация в памяти (для анализа локальности)
   

   При построчном размещении (row-major, как в C/С++/Python):

   offset(A[i][j]) = base(A) + (i * n + j) * sizeof(T)

   При постолбцовом (column-major, как в Fortran/Matlab):

   offset(A[i][j]) = base(A) + (j * m + i) * sizeof(T)

Вывод: последовательный обход по «быстрому» индексу (соответствующему смежным адресам) улучшает локальность кэша.

Базовые схемы обхода и инварианты

1. Полный перебор элементов (row-major)
   

   for i := 0..m-1:

       for j := 0..n-1:

           visit(A[i][j])

   Инвариант внешнего цикла: к началу итерации i полностью обработаны строки 0..i-1.
   Инвариант внутреннего цикла: к началу итерации j обработаны элементы строки i на префиксе 0..j-1.

2. Полный перебор (column-major)
   

   for j := 0..n-1:

       for i := 0..m-1:

           visit(A[i][j])

   Используется, когда важен помстрочный или помстолбцовый агрегат/локальность.

3. Ограниченные области
   

   • Верхний треугольник (i < j), нижний (i > j), диагонали (i = j, i + j = n - 1).

   • Прямоугольный подотрезок R = [r1..r2] × [c1..c2]:

   • for i := r1..r2:

   •     for j := c1..c2:

   •         visit(A[i][j])

   Правило границ: каждый полузамкнутый интервал записывать явно; не смешивать стиль [0..n-1] и [1..n].
   

Алгоритмические примитивы обработки

1. Агрегирование (сумма, минимум, максимум, счёт)
   

   sum := 0; mn := +∞; mx := -∞; cnt := 0

   for i := 0..m-1:

       for j := 0..n-1:

           x := A[i][j]

           sum := sum + x

           if x < mn then mn := x

           if x > mx then mx := x

           if P(x) then cnt := cnt + 1

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

2. Построчные и постолбцовые суммы/экстремумы
   

   rowSum[i] := Σ_{j=0..n-1} A[i][j]

   colSum[j] := Σ_{i=0..m-1} A[i][j]

   Реализация: два вложенных цикла с обнулением сумм перед накоплением.

3. Поиск координат экстремума
   

   best := A[0][0]; bi := 0; bj := 0

   for i := 0..m-1:

       for j := 0..n-1:

           if A[i][j] > best then

               best := A[i][j]; bi := i; bj := j

4. Транспонирование
   

   • Для квадратной n×n in-place:

   • for i := 0..n-1:

   •     for j := i+1..n-1:

   •         swap(A[i][j], A[j][i])

   • Для прямоугольной m×n → n×m:

   • B[j][i] := A[i][j]

5. Повороты (для n×n)
   

   Поворот на 90° по часовой:       B[i][j] = A[n-1-j][i]

   Поворот на 90° против часовой:   B[i][j] = A[j][n-1-i]

   Отражение по вертикали:          B[i][j] = A[i][n-1-j]

   Отражение по горизонтали:        B[i][j] = A[n-1-i][j]

6. 2D-префиксные суммы (быстрые запросы на подматрицу)
   

   Определим S размера (m+1)×(n+1):

   S[i+1][j+1] = A[i][j] + S[i][j+1] + S[i+1][j] - S[i][j]

   Сумма на подпрямоугольнике R = [r1..r2] × [c1..c2]:

   Sum(R) = S[r2+1][c2+1] - S[r1][c2+1] - S[r2+1][c1] + S[r1][c1]

   Построение S: Θ(mn), ответ на запрос: Θ(1).

Корректность: контракты и инварианты

1. Хоаровская форма записи
   

   Пусть F – алгоритм, вычисляющий сумму всех элементов.

   {P: m>0 ∧ n>0 ∧ A определена}  F(A,m,n)  {Q: result = Σ_{i=0..m-1} Σ_{j=0..n-1} A[i][j]}

   Инвариант внешнего цикла: после обработки строк 0..i-1 частичная сумма равна сумме их элементов.
   Инвариант внутреннего: после обработки столбцов 0..j-1 частичная сумма соответствует префиксу строки i.

2. Завершимость
   Вариант функции спуска – число необработанных ячеек. На каждой итерации уменьшается на 1 ⇒ алгоритм конечен.
   

3. Типовые ловушки и профилактика
   

   • Off-by-one: неверные границы j := 0..n-2 вместо 0..n-1.

   • Перепутанные индексы: обращение A[j][i] вместо A[i][j].

   • Смешение стилей индексации: часть кода 0-based, часть 1-based.

   • Неправильная инициализация агрегатов (mn := +∞, а не 0).

   • Нарушение локальности при интенсивной обработке – выбирайте порядок обхода, соответствующий физическому размещению в памяти, чтобы не потерять производительность.

Оценка трудоёмкости и ресурсоёмкости

• Полный односканерный проход: Θ(mn).

• Транспонирование n×n: ≈ n(n-1)/2 обменов, время Θ(n^2), память Θ(1).

• Построчные/постолбцовые агрегаты: Θ(mn) и Θ(m + n) дополнительной памяти при сохранении всех сумм.

• Префиксные суммы: построение Θ(mn), ответы Θ(1), память Θ(mn).

Правила «чистой» реализации

Правило 1. Всегда явно фиксируйте модель индексации и придерживайтесь её по всему решению.
Правило 2. Перед входом в вложенные циклы инициализируйте аккумуляторы в корректных границах (например, обнуляйте rowSum[i] перед обходом столбцов).
Правило 3. При работе с диагоналями проверяйте квадратность (m = n) до вычислений.
Правило 4. Для операций «на месте» (in-place) фиксируйте область обмена, чтобы не «перезаписать» ещё не использованные данные (например, j > i при транспонировании).
Правило 5. Отдельно тестируйте краевые случаи: m=1, n=1, нули/отрицательные значения, равные элементы, пустые множества (если допускаются).

Связь с подготовкой к ЕГЭ

• Точные условия отбора (диагонали/треугольники) регулярно встречаются в заданиях на анализ кода.

• Подсчёты и агрегаты требуют безошибочной инициализации и корректных границ.

• Транспонирование/повороты – типичные задачи на аккуратную индексацию.

• Оценка сложности и осознание Θ(mn) – обязательный элемент аргументации в разборе.

• Префиксные суммы позволяют мгновенно отвечать на запросы по подматрицам – продвинутый приём, повышающий эффективность решений.

Мини-шпаргалка (копируемые формулы)

Главная диагональ:    i = j

Побочная диагональ:   i + j = n - 1

Row-major offset:     offset = (i * n + j) * sizeof(T)

2D-префикс:           S[i+1][j+1] = A[i][j] + S[i][j+1] + S[i+1][j] - S[i][j]

Сумма подматрицы:     Sum = S[r2+1][c2+1] - S[r1][c2+1] - S[r2+1][c1] + S[r1][c1]

Транспонирование nxn: swap(A[i][j], A[j][i]) для j > i

Поворот 90° cw:       B[i][j] = A[n-1-j][i]

Пять упражнений 

Упражнение 1. Построчные и постолбцовые агрегаты

Дана матрица A размера m×n.
a) Составьте алгоритм вычисления массивов rowSum[0..m-1] и colSum[0..n-1].
b) Запишите инварианты внутренних циклов.
c) Оцените трудоёмкость и укажите, как изменится порядок обхода для улучшения локальности в модели row-major.

Упражнение 2. Диагональные выборки и корректность условий

Пусть A – квадратная n×n.
a) Сформулируйте алгоритм вычисления S1 = Σ_{i=0..n-1} A[i][i] и S2 = Σ_{i=0..n-1} A[i][n-1-i].
b) Докажите, что для нечётного n центральный элемент не должен учитываться дважды (укажите исправленную формулу).
c) Приведите контрпример, демонстрирующий ошибку при смешении 0-based и 1-based индексаций.

Упражнение 3. Транспонирование и повороты

a) Запишите in-place транспонирование n×n с доказательством отсутствия перезаписи данных (поясните, почему достаточно j > i).
b) Выведите формулы преобразования индексов для поворотов на 90°/180°/270° и отражений.
c) Оцените, когда требуется дополнительная матрица и почему.

Упражнение 4. 2D-префиксные суммы и быстрые запросы

Для A размера m×n постройте S по формуле префиксов.
a) Выведите формулу Sum(R) для подматрицы R = [r1..r2] × [c1..c2].
b) Докажите корректность по индукции по i,j.
c) Оцените выигрыш по времени при множестве запросов и приведите оценки по памяти.

Упражнение 5. Выбор максимума с координатами и устойчивость к равным значениям

a) Напишите алгоритм поиска максимума и его первых по порядку координат (bi, bj) в случае наличия нескольких максимумов.
b) Сформулируйте инвариант: после обработки префикса строк 0..i и столбцов 0..j переменная (best, bi, bj) корректно описывает максимум на просмотренной части.
c) Обсудите влияние порядка обхода на «стабильность» выбора координат при равных значениях.

Заключение

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