Модуль 7. Многомерные массивы

Многомерный массив хранит элементы в прямоугольной области фиксированного ранга. Положение элемента задаётся упорядоченным набором координат, причём каждая координата имеет собственную границу GetLength(d). Общее свойство Length сообщает число элементов во всей области, но не заменяет длины отдельных измерений и не определяет форму массива.

Форма является частью контракта алгоритма. Двумерная таблица различает строки и столбцы, трёхмерная область добавляет слои, а четырёхмерная — ещё одну независимую ось. Транспонирование, отражение, поворот, срез, проекция и перестановка осей задаются отображением координат между исходной и результирующей формами; корректность требует доказать допустимость каждой получаемой координаты и отсутствие потерь либо повторов.

Порядок посещения также является самостоятельным алгоритмом. Построчный и столбцовый обходы следуют прямым вложенным циклам, тогда как змейка, диагонали и спираль требуют разделить область на непересекающиеся части. Свёртка координат в линейную позицию и обратное восстановление должны быть взаимно обратны, а сложные обходы — посещать каждую требуемую ячейку ровно один раз.

Опора — Раздел 17: многомерные массивы. Дополнительно используются вложенные циклы, инварианты и классы роста из Раздела 12, методы, кортежи и рекурсия из Разделов 13–14, одномерные массивы и ссылочная семантика из Разделов 15–16.

Каждая задача оформляется отдельной консольной программой полным шаблоном курса и компилируется с <Nullable>enable</Nullable>. Разрешены только конструкции Разделов 1–17. Используются прямоугольные массивы T[,], T[,,], T[,,,] и изученные ранее одномерные массивы; зубчатые массивы, собственные struct, дополнительные классы, коллекции, LINQ, Index, Range, делегаты, лямбда-выражения и обработка исключений запрещены. Размер каждого измерения получается через GetLength; числовая константа не подменяет границу структуры. Каждый метод фиксирует ранг, форму результата, отображение координат, изменение либо сохранение входа и допустимость нулевых измерений. Потенциально аварийные обращения и намеренно некомпилируемые варианты исследуются только в отдельных копиях проекта.

---

База практических заданий

Уровень I. Базовый

Ранг, форма, порядок вложенных циклов, границы координат и отображение элементов заданы условием. Требуется точно реализовать готовую координатную модель, проверить минимальные и вырожденные формы и подтвердить указанный инвариант. Ученик не выводит преобразование самостоятельно: сложность возрастает от чтения формы к профилям осей, геометрическим областям, преобразованиям таблицы и срезам массивов рангов 3 и 4.

1. Паспорт ранга и формы: Создать:

int[,] table = new int[2, 3];
int[,,] volume = new int[2, 2, 3];
int[,,,] field = new int[2, 1, 2, 3];

Для каждого массива вывести Rank, Length и длину каждого измерения через GetLength. Подтвердить явными произведениями:

$$table.Length=table.GetLength(0)\cdot table.GetLength(1),$$ $$volume.Length= volume.GetLength(0)\cdot volume.GetLength(1)\cdot volume.GetLength(2),$$

и аналогичное равенство для ранга 4. Объяснить, почему аргумент GetLength является номером измерения, а не координатой элемента.

2. Заполнение и два порядка обхода: Даны rows >= 0 и columns >= 0. Создать int[,] формы rows × columns и заполнить:

$$a_{ij}=100i+j.$$

Выполнить построчный обход — сначала строки, затем столбцы — и постолбцовый обход в обратном порядке вложенности. Для каждого вывести координаты и значения, подсчитать посещения и сумму. Подтвердить, что оба обхода посещают Length элементов и дают одинаковую сумму, но различную последовательность координат.

3. foreach без координат: Заполнить таблицу формы 3 × 4 различными значениями и получить сумму двумя способами: вложенными индексированными циклами и foreach. Последовательность значений foreach сохранить в одномерный массив и сравнить с построчной свёрткой, в которой последнее измерение изменяется быстрее всего. Объяснить, почему foreach удобен для полного чтения значений, но не предоставляет координаты и не заменяет индексированный обход при работе со строками, столбцами и преобразованиями.

4. Профили строк и столбцов: Для непустой таблицы целых реализовать:

static (
    long[] rowSums,
    int[] rowMaxima,
    long[] columnSums,
    int[] columnMinima) BuildProfiles(int[,] data)

Экстремумы каждой оси инициализируются первым элементом соответствующей строки или столбца. Накопители строки создаются внутри цикла по строкам, накопители столбца — внутри цикла по столбцам. Проверить на неквадратной таблице и подтвердить, что сумма rowSums равна сумме columnSums.

5. Рамка и внутренняя область: Для таблицы формы m × n, где размеры могут быть нулевыми, одним полным обходом вычислить количество и сумму элементов рамки и внутренности. Ячейка принадлежит рамке, если

row == 0 ||
row == m - 1 ||
column == 0 ||
column == n - 1

При m == 0 || n == 0 обе области пусты. При положительных размерах число элементов рамки равно m * n, если m == 1 || n == 1, иначе

$$2m+2n-4.$$

Подтвердить, что суммы и количества двух областей дают общие значения таблицы.

6. Диагонали и треугольные области: Для квадратной таблицы n × n одним циклом получить суммы главной и побочной диагоналей. Полным обходом вычислить суммы строго выше и строго ниже главной диагонали. Подтвердить разбиение:

$$S_{\mathrm{all}} = S_{\mathrm{above}} + S_{\mathrm{main}} + S_{\mathrm{below}}.$$

Для нечётного n отдельно объяснить, почему центральный элемент принадлежит обеим диагоналям, но только главной диагонали в треугольном разбиении.

7. Транспонированная копия: Реализовать:

static int[,] Transpose(int[,] source)

Для формы m × n результат имеет форму n × m и удовлетворяет:

$$result_{ji}=source_{ij}.$$

Исходный массив сохраняется. Повторно транспонировать результат и подтвердить поэлементное равенство с источником, включая формы с нулевым измерением.

8. Два отражения: Реализовать новые таблицы той же формы:

static int[,] ReflectHorizontally(int[,] source)

static int[,] ReflectVertically(int[,] source)

При отражении слева направо:

$$(i,j)\mapsto(i,n-1-j),$$

при отражении сверху вниз:

$$(i,j)\mapsto(m-1-i,j).$$

Каждое преобразование применить дважды и подтвердить восстановление исходной таблицы.

9. Поворот на 90° по часовой стрелке: Реализовать:

static int[,] RotateClockwise(int[,] source)

Для исходной формы m × n результат имеет форму n × m; координатное отображение:

$$(i,j)\mapsto(j,m-1-i).$$

Проверить несколько угловых элементов и применить поворот четыре раза, подтверждая восстановление исходной формы и содержимого.

10. Трёхмерный массив и суммы слоёв: Создать int[,,] формы layers × rows × columns и заполнить:

$$v_{sij}=100s+10i+j.$$

Для каждого слоя по измерению 0 вычислить сумму всех элементов и записать её в long[]. Подтвердить, что сумма слоёв равна общей сумме массива. Инвариант внешнего цикла: законченные слои полностью обработаны, а текущий и последующие ещё не включены в общий итог.

11. Три координатных среза: Для int[,,] source формы A × B × C и допустимых фиксированных координат a0, b0, c0 построить:

• source[a0, j, k] формы B × C;
• source[i, b0, k] формы A × C;
• source[i, j, c0] формы A × B.

Формы и прямые отображения заданы условием. Требуется реализовать три отдельных метода и независимо проверить угловые и внутренние элементы каждого среза.

12. Четырёхмерная нумерация и проекция: Создать long[,,,] data формы A × B × C × D и заполнить линейными позициями:

$$p=(((iB)+j)C+k)D+l.$$

Затем построить long[,] projection формы B × C, где:

$$projection_{jk} = \sum_{i=0}^{A-1} \sum_{l=0}^{D-1} data_{ijkl}.$$

Подтвердить, что значения исходного массива лежат от 0 до Length - 1, каждое встречается один раз, а сумма проекции равна общей сумме исходного массива.

---

Уровень II. Продвинутый

Условие задаёт требуемую форму результата или геометрическое свойство, но не готовое отображение координат, порядок обхода и модель хранения промежуточных данных. Требуется самостоятельно вывести размеры, прямую и обратную формулы, выбрать преобразование на месте либо новый массив и доказать допустимость и полноту отображения. В отличие от Уровня I основная работа состоит в проектировании координатного алгоритма.

1. Свёртка таблицы и восстановление: Для таблицы формы m × n построить одномерную построчную копию и восстановить из неё новую таблицу той же формы. Самостоятельно вывести взаимно обратные формулы:

$$p=in+j,$$ $$i=\left\lfloor\frac{p}{n}\right\rfloor, \qquad j=p\bmod n.$$

При n == 0 линейный массив пуст и обратное восстановление выполняется только по сохранённой форме без деления. Проверить первую, последнюю и несколько внутренних координат.

2. Свёртка трёхмерного массива: Для формы A × B × C вывести формулы:

$$p=(iB+j)C+k,$$ $$i=\left\lfloor\frac{p}{BC}\right\rfloor,$$ $$r=p\bmod(BC), \qquad j=\left\lfloor\frac{r}{C}\right\rfloor, \qquad k=r\bmod C.$$

Реализовать перенос в одномерный массив и обратную сборку int[,,]. Для нулевого B или C линейный массив пуст; деление в обратной формуле не выполняется. Инвариант связывает линейный префикс с уже перенесёнными координатами в порядке, где последнее измерение изменяется быстрее всего.

3. Змеиная свёртка с восстановлением: Таблица выписывается в одномерный массив построчно, но чётные строки идут слева направо, нечётные — справа налево. Самостоятельно вывести отображение линейной позиции p в row и column:

$$row=\left\lfloor\frac{p}{n}\right\rfloor, \qquad offset=p\bmod n,$$

а столбец зависит от чётности строки. Затем восстановить таблицу без сохранения отдельного массива направлений. Проверить формы 1 × n, m × 1 и неквадратную таблицу.

4. Транспонирование квадратной таблицы на месте: Для n × n вывести область обменов, достаточную для транспонирования без дополнительной таблицы. Реализовать обмен только для пар column > row. Доказать, что диагональ остаётся на месте, каждая внедиагональная пара обрабатывается один раз, а полный обход обменял бы элементы дважды. Сравнить результат с чистой транспонированной копией.

5. Поворот квадратной таблицы на месте: Для n × n реализовать поворот на 90° по часовой стрелке с памятью $O(1)$. Самостоятельно выбрать один из двух подходов:

• транспонирование на месте и отражение слева направо;
• послойная перестановка четырёх ячеек каждого кольца.

Для выбранной схемы сформулировать инвариант обработанных строк либо колец и подтвердить совпадение с чистым поворотом из Уровня I.

6. Семейство преобразований прямоугольника: Спроектировать чистые методы для транспонирования, поворотов на 90°, 180°, 270° и двух отражений. Для каждого самостоятельно вывести форму и координатное отображение. Проверить тождества:

• четыре поворота на 90° дают исходную таблицу;
• два одинаковых отражения дают исходную;
• два отражения по разным осям эквивалентны повороту на 180°;
• транспонирование, выполненное дважды, даёт исходную.

7. Перестановка осей трёхмерного массива: Для source формы A × B × C построить результат формы C × A × B:

$$result_{kij}=source_{ijk}.$$

Самостоятельно вывести обратную перестановку, восстановить исходный массив и подтвердить равенство всех элементов. Объяснить, почему перестановка осей меняет форму, но сохраняет Length.

8. Умножение матриц: Спроектировать:

static bool TryMultiply(
    double[,] left,
    double[,] right,
    out double[,] product)

Если число столбцов left не равно числу строк right, вернуть false и пустую таблицу. Иначе результат имеет форму m × n:

$$c_{ij} = \sum_{t=0}^{k-1} a_{it}b_{tj}.$$

Самостоятельно определить порядок трёх циклов и область жизни накопителя одной ячейки. При k == 0 результат допустим и состоит из нулей. Проверить умножение на единичную матрицу и один элемент независимым ручным расчётом.

9. Сглаживание ортогональной окрестностью: Для double[,] source построить новый массив той же формы, где каждая ячейка равна среднему исходной ячейки и существующих ортогональных соседей. Число участников зависит от положения: угол, сторона или внутренность. Исходный массив сохраняется. Самостоятельно организовать проверку допустимости соседей и доказать, что ни один сосед не учитывается дважды.

10. Седловые точки: Для непустой таблицы целых найти все координаты элементов, которые одновременно минимальны в своей строке и максимальны в своём столбце. Повторяющиеся значения разрешены, каждое подходящее положение считается отдельно. Поскольку количество результатов неизвестно, сначала определить его, затем создать два массива rows и columns точного размера. Самостоятельно выбрать между прямой проверкой каждой ячейки и предварительными профилями осей, оценив время и память.

11. Двумерные префиксные суммы: Для int[,] data формы m × n построить long[,] prefix формы (m + 1) × (n + 1):

$$prefix_{i+1,j+1} = data_{ij} + prefix_{i,j+1} + prefix_{i+1,j} - prefix_{i,j}.$$

Спроектировать сумму прямоугольника [top, bottom) × [left, right):

$$S= prefix_{bottom,right} - prefix_{top,right} - prefix_{bottom,left} + prefix_{top,left}.$$

Зафиксировать предусловия координат, доказать формулу включений и исключений и объяснить цену $O(mn)$ подготовки против $O(1)$ одного запроса.

12. Общая перестановка четырёх осей: Дан int[,,,] source и одномерный массив permutation длины 4, содержащий каждое значение 0, 1, 2, 3 ровно один раз. Координата результата по оси d соответствует исходной оси permutation[d]. Самостоятельно:

• проверить перестановку до создания результата;
• определить четыре размера результата;
• для каждой координаты результата восстановить четыре координаты источника;
• построить обратную перестановку;
• восстановить исходный массив.

Подтвердить сохранение Length, формы после обратного преобразования и всех элементов.

---

Уровень III. Экспертный

Исследуется не отдельное вычисление, а полнота координатной модели, граница допустимых индексов или механизм выигрыша сложного обхода. До сборки и запуска требуется предсказать форму, допустимые координаты, траекторию границ, число посещений и возможный отказ; после — объяснить результат через инвариант необработанной области, взаимную обратимость отображений и соответствие индекса измерению.

1. Нулевые измерения и ошибки ранга: В отдельных копиях проекта исследовать:

new int[0, 5]
new int[4, 0, 3]

а также:

• Length, Rank и каждый допустимый GetLength;
• полный вложенный обход;
• обращение data[0, 0] к таблице с нулевой строкой;
• GetLength(-1) и GetLength(data.Rank);
• попытку обратиться к int[,] одним индексом;
• цикл, использующий GetLength(1) как границу первой координаты.

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

2. Порядок foreach и линейная позиция: Для форм 2 × 3, 2 × 2 × 3 и 2 × 1 × 2 × 3 заполнить массивы линейной формулой, в которой последнее измерение изменяется быстрее всего. Сохранить последовательность foreach в одномерный массив и сопоставить каждую позицию с обратным восстановлением координат. До запуска предсказать порядок. Объяснить, почему порядок перечисления можно использовать для полной свёртки значений, но код, которому нужны координаты, должен либо восстанавливать их, либо применять индексированные циклы.

3. Спиральный обход прямоугольника: Построить одномерный результат в порядке спирали по часовой стрелке от левого верхнего угла. Состояние состоит из границ top, bottom, left, right необработанного прямоугольника. После верхнего и правого проходов необходимо проверять, существуют ли ещё нижняя строка и левый столбец. До запуска выписать порядок для 1 × 1, 1 × n, m × 1, 2 × n, m × 2. Доказать, что после каждого кольца необработанная область строго уменьшается, а каждая ячейка посещается ровно один раз.

4. Диагональный обход прямоугольной таблицы: Вывести элементы по диагоналям постоянной суммы координат:

$$row+column=d, \qquad 0\le d\le m+n-2.$$

Для каждой диагонали вывести допустимый диапазон строк:

$$\max(0,d-(n-1)) \le row \le \min(m-1,d),$$

а столбец вычислять как d - row. Построить одномерный результат и bool[,] visited. Подтвердить Length посещений, отсутствие повторов и заполнение всей таблицы для квадратных и прямоугольных форм.

5. Лестничный поиск в монотонной таблице: Дана непустая таблица, в которой строки и столбцы не убывают. Начать с правого верхнего угла. Если значение больше цели, исключить текущий столбец; если меньше — текущую строку. Вернуть координаты либо (-1, -1) и число сравнений. До запуска получить верхнюю границу:

$$m+n-1.$$

Сформулировать инвариант оставшейся прямоугольной области и сравнить $O(m+n)$ с полным обходом $O(mn)$.

6. Цена прямоугольных запросов: Для одной таблицы и массива из q прямоугольных запросов реализовать:

1. прямое суммирование каждого прямоугольника;
2. одну таблицу двумерных префиксных сумм и ответы четырьмя обращениями.

Подсчитать сложения и вычитания, не измеряя время. Для квадратной таблицы n × n и запросов, способных охватывать всю область, сопоставить:

$$T_{\mathrm{direct}}=O(qn^2),$$ $$T_{\mathrm{prefix}}=O(n^2+q).$$

Определить, при каком числе повторных запросов предварительная обработка становится содержательно оправданной, и учесть память $O(n^2)$.

7. Лаборатория линейного индекса четырёх измерений: Для формы A × B × C × D реализовать прямую и обратную свёртку:

$$p=(((iB)+j)C+k)D+l.$$

Полным обходом отмечать позиции в bool[] seen, проверяя допустимость, отсутствие повторов и заполнение всех Length позиций. Затем намеренно заменить один множитель неверным размером измерения. До запуска предсказать, почему дефект может быть скрыт при равных размерах и проявиться пропусками, повторами либо выходом за диапазон на несимметричной форме. Объяснить роль каждого множителя как произведения более быстрых измерений.

8. Граница трёхмерного параллелепипеда: Для формы A × B × C, где A, B, C >= 3, классифицировать координату по числу граничных компонентов:

• 3 — угол;
• 2 — внутренняя точка ребра;
• 1 — внутренняя точка грани;
• 0 — внутренность.

До запуска вывести:

$$N_{\mathrm{corners}}=8,$$ $$N_{\mathrm{edges}} = 4\bigl((A-2)+(B-2)+(C-2)\bigr),$$ $$N_{\mathrm{faces}} = 2\bigl( (A-2)(B-2) + (A-2)(C-2) + (B-2)(C-2) \bigr),$$ $$N_{\mathrm{inside}} = (A-2)(B-2)(C-2).$$

Полным обходом подтвердить каждую формулу и равенство суммы категорий произведению A * B * C. Затем исследовать размеры 1 и 2 и объяснить, почему геометрические категории начинают пересекаться и формулы требуют указанного предусловия.

---

Обязательные контрольные наборы

---

Итог модуля

Ученик создаёт и обходит прямоугольные массивы рангов 2, 3 и 4, различает Rank, общее Length и длины отдельных измерений и выводит допустимость каждой координаты через GetLength. Он строит профили строк и столбцов, диагонали, рамки, слои, срезы и проекции, выполняет транспонирование, отражения, повороты и перестановки осей как явные отображения между формами. Построчный, столбцовый, foreach-, змеиный, диагональный и спиральный обходы сопровождаются инвариантом и доказательством однократного посещения. Ученик сворачивает и восстанавливает координаты, применяет матричное умножение, окрестности и двумерные префиксные суммы и обосновывает решения по корректности индексов, числу посещений, дополнительной памяти и классам роста.

Покрытие опоры и границы

• Синтаксис T[,], T[,,], T[,,,], Rank, Length, GetLength и нулевые измерения: I.1–I.3, III.1–III.2.
• Отдельный индекс и граница для каждого измерения: I.2–I.12, II.1–II.12.
• Построчный, столбцовый и foreach-обходы: I.2–I.4, III.2.
• Строки, столбцы, рамка, главная и побочная диагонали, треугольные области: I.4–I.6.
• Слои, двумерные и трёхмерные срезы и проекции: I.10–I.12, II.7, II.12.
• Свёртка и восстановление координат рангов 2, 3 и 4: II.1–II.3, III.2 и III.7.
• Транспонирование, отражение и поворот: I.7–I.9, II.4–II.6.
• Перестановка осей: II.7 и II.12.
• Матричное умножение и алгоритмы окрестности: II.8–II.9.
• Седловые точки и координатные результаты неизвестного размера: II.10.
• Двумерные префиксные суммы и повторные прямоугольные запросы: II.11, III.6.
• Змеиный, спиральный и диагональный порядки: II.3, III.3–III.4.
• Лестничный поиск в монотонной таблице: III.5.
• Полнота, отсутствие повторов, геометрические категории и ошибки соответствия измерений: III.1–III.8.
• Классы $O(mn)$, $O(m+n)$, $O(mnk)$, $O(1)$ на запрос и цена дополнительной памяти: II.8–II.11, III.5–III.6.

За границей: зубчатые массивы и nullable-строки рассматриваются в Модуле 8. Собственные структуры, классы, обобщённые коллекции, LINQ, Span<T>, специализированные матричные библиотеки, разреженные матрицы, тензорные фреймворки и аппаратно-зависимая оптимизация обхода относятся к последующим модулям и курсам. Фактическая производительность разных порядков обхода не измеряется до Раздела 21; в этом модуле сравниваются только число операций, форма доступа и асимптотика.