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

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

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

Упорядоченность является отдельным предусловием и ресурсом алгоритма. Простая процедурная сортировка может быть устойчивой или неустойчивой и обычно требует квадратичного числа сравнений либо перемещений; сортировка слиянием и Array.Sort имеют порядок $O(n\log n)$ при разных гарантиях и затратах памяти. Бинарный поиск сокращает диапазон кандидатов вдвое, но остаётся корректным только при согласованном отношении порядка и точном соблюдении инварианта границ.

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

Каждая задача оформляется отдельной консольной программой полным шаблоном курса и компилируется с <Nullable>enable</Nullable>. Разрешены только конструкции Разделов 1–15. Используются только одномерные массивы; многомерные и зубчатые массивы, собственные struct, коллекции, LINQ, Index, Range, делегаты, лямбда-выражения, пользовательские компараторы и обработка исключений запрещены. Все пользовательские методы объявляются как static. Каждый массив-параметр считается ненулевым по предусловию; необходимость непустого массива фиксируется отдельно. Контракт метода явно указывает, изменяет ли он элементы входного массива, использует ли логическую длину либо возвращает новый массив. Array.Sort применяется только там, где это прямо разрешено условием; в остальных задачах алгоритм реализуется вручную. Для связанных данных без struct разрешены параллельные массивы одинаковой длины, согласованность которых является отдельным инвариантом.

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

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

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

1. Создание, инициализация и значения по умолчанию: Реализовать

static int[] BuildSequence(int length)

для length >= 0. Метод создаёт массив заданной длины и заполняет его по правилу

В Main дополнительно создать массив через new int[length], массив с явным инициализатором new int[] { 4, -1, 7 } и массив с выведенным типом new[] { 4, -1, 7 }. Для первого подтвердить нулевые значения элементов до заполнения. Вывести Length, а первый и последний элементы — только при ненулевой длине. Инвариант BuildSequence: перед итерацией i позиции [0, i) уже содержат значения формулы, а [i, length) сохраняют значения по умолчанию.

2. Аргументы командной строки и params: Реализовать

static void PrintArguments(string[] arguments)

с индексированным выводом всех элементов args и

static long Sum(params int[] values)

с суммированием через foreach. Вызвать Sum() без значений, с отдельными аргументами и с готовым массивом. Объяснить, почему пустой вызов передаёт корректный массив длины 0, почему params должен быть последним параметром и почему внутри метода он обрабатывается как обычный int[].

3. Накопители с нейтральным началом: Реализовать

static (
    long sum,
    int positiveCount,
    int evenCount,
    double? mean) Summarize(int[] data)

одним foreach. Сумма и счётчики начинаются с нейтральных значений. Для пустого массива mean равен null; для непустого вычисляется как вещественное отношение суммы к Length. Исходный массив не изменяется. Инвариант после обработки очередного префикса: накопители точно описывают все уже прочитанные элементы.

4. Экстремумы непустого массива: Реализовать

static (
    int min,
    int minIndex,
    int max,
    int maxIndex) FindExtremes(int[] data)

с предусловием data.Length > 0. Минимум и максимум инициализируются data[0]; при повторении экстремума сохраняется первая позиция. Использовать индексированный проход от 1 до Length - 1. Объяснить, почему искусственные начальные пределы слабее затравки первым элементом и почему метод не должен молча придумывать результат для пустого входа.

5. Первое, последнее и число вхождений: Реализовать

static (
    int firstIndex,
    int lastIndex,
    int count) FindOccurrences(
        int[] data,
        int target)

за один проход. Отсутствие кодируется тройкой (-1, -1, 0). Первое вхождение записывается только при первом совпадении, последнее обновляется при каждом. Инвариант после обработки [0, i): кортеж полностью описывает все вхождения target в этом префиксе.

6. Преобразование в новый массив: Реализовать

static long[] Transform(
    int[] data,
    int multiplier,
    int offset)

по правилу

Произведение расширять до long до умножения. Результат имеет ту же длину, исходный массив не изменяется. После вызова вывести оба массива и проверить каждый элемент равенством формуле. Сформулировать различие контрактов «изменить вход» и «вернуть новый результат».

7. Разворот на месте: Реализовать

static void Reverse(int[] data)

двумя индексами left и right, движущимися навстречу. Дополнительная память — $O(1)$. Инвариант: элементы вне интервала [left, right] уже находятся на окончательных зеркальных позициях. Проверить пустую, одноэлементную, чётную и нечётную длину.

8. Циклический сдвиг вправо на одну позицию: Реализовать

static void RotateRightOne(int[] data)

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

9. Фильтрация в массив точного размера: Реализовать

static int[] NonNegativeOnly(int[] data)

Первый проход подсчитывает неотрицательные элементы, второй заполняет новый массив точного размера в исходном порядке. Пустой результат является корректным массивом длины 0. Инвариант второго прохода: префикс результата [0, write) содержит все подходящие элементы уже просмотренного префикса входа и только их.

10. Слияние двух упорядоченных массивов: Реализовать

static int[] MergeSorted(
    int[] left,
    int[] right)

для двух неубывающих массивов. Два индекса выбирают меньший текущий элемент; при равенстве первым переносится элемент из left. После исчерпания одного входа остаток другого копируется отдельным циклом. Инвариант: заполненный префикс результата неубывает и содержит все уже потреблённые элементы обоих входов. Время — $O(n+m)$, дополнительная память — $O(n+m)$.

11. Устойчивая сортировка вставками по ключу: Даны параллельные массивы int[] keys и int[] originalOrder одинаковой длины. Реализовать

static void StableInsertionSort(
    int[] keys,
    int[] originalOrder)

на месте. На шаге i префикс [0, i) уже упорядочен по key; ключ и связанную метку позиции i сохранить, большие ключи сдвигать вправо, затем вставить сохранённую пару. Для равных ключей использовать строгое сравнение >, чтобы сохранить порядок меток. Подсчитать сравнения ключей и записи в массивы. Проверить устойчивость отдельным проходом: внутри группы равных ключей originalOrder должен возрастать.

12. Копия, Array.Sort и бинарный поиск: Реализовать поэлементный

static int[] CopyOf(int[] source)

и

static (
    int index,
    int comparisons) BinarySearch(
        int[] sorted,
        int target)

Бинарный поиск работает на полуинтервале [lo, hi) и может вернуть любое найденное вхождение. В Main создать копию исходного массива, отсортировать только копию через Array.Sort, подтвердить сохранность исходного порядка и выполнить поиск присутствующей и отсутствующей цели. Инвариант поиска: если цель существует, хотя бы одно её вхождение находится в текущем полуинтервале; при lo == hi область кандидатов пуста.

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

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

1. Самая длинная возрастающая серия: Для непустого массива найти первую самую длинную непрерывную строго возрастающую серию. Вернуть (start, end, length), где границы включительны. Один проход поддерживает начало и длину текущей серии и лучший результат. При равной длине сохраняется более ранняя серия. Разобрать полностью возрастающий массив, массив без возрастающей соседней пары и несколько максимумов одинаковой длины.

2. Максимальный непустой подмассив: Для непустого массива целых найти непрерывный участок максимальной суммы за $O(n)$ и вернуть (long sum, int start, int end). Для массива из отрицательных значений выбирается наибольший отдельный элемент. При равенстве сумм предпочитается более раннее начало, затем меньшая длина. Самостоятельно вывести состояние алгоритма Кадане и инвариант: после позиции i известен лучший участок, оканчивающийся в i, и лучший участок всего префикса [0, i].

3. Префиксные суммы и запросы: Реализовать

static long[] BuildPrefixSums(int[] data)

с результатом длины data.Length + 1:

Спроектировать

static long RangeSum(
    long[] prefix,
    int left,
    int right)

для суммы полуинтервала [left, right) одной разностью. Зафиксировать предусловие 0 <= left <= right < prefix.Length, инвариант построения и цену $O(n)$ подготовки против $O(1)$ одного запроса.

4. Все индексы равновесия: Индекс $i$ называется равновесным, если сумма элементов слева от него равна сумме справа. Вернуть массив всех таких индексов точного размера. Общая сумма вычисляется заранее; при движении по массиву поддерживается сумма слева, а сумма справа выводится без повторного прохода. Поскольку длина ответа заранее неизвестна, спроектировать подсчёт количества и заполнение либо другой способ без коллекций. Общая сложность должна быть $O(n)$.

5. Устойчивое уплотнение на месте: Перенести все ненулевые элементы в начало массива, сохранив их относительный порядок, вернуть логическую длину заполненного префикса и записать нули в освободившийся хвост. Дополнительный массив запрещён. Самостоятельно вывести индексы чтения и записи. Инвариант: [0, write) содержит ровно ненулевые элементы просмотренной области в исходном порядке, а [write, read) не содержит ещё нужных для результата значений.

6. Циклический сдвиг на произвольное число позиций: Реализовать сдвиг массива вправо на целое $k$ на месте и с памятью $O(1)$. Для непустого массива нормализовать $k$ в диапазон [0, Length) с учётом отрицательных значений, затем применить три разворота диапазонов. Пустой массив обрабатывается до операции %. Вспомогательный метод разворота получает две включительные границы. Доказать, как последовательность разворотов меняет порядок двух блоков.

7. Пара с заданной суммой в упорядоченном массиве: Для неубывающего массива найти индексы left < right, для которых

Использовать два индекса с концов и вычислять сумму в long. Вернуть первую пару, обнаруженную каноническим двухиндексным проходом, либо (-1, -1). Сформулировать инвариант отброшенных пар и доказать $O(n)$ по сравнению с полным перебором $O(n^2)$.

8. Удаление повторов на месте: Для неубывающего массива перенести каждое различное значение в начало ровно один раз и вернуть логическую длину. Хвост после логического результата заполнить нулями. Дополнительный массив запрещён. Инвариант: [0, write) содержит все различные значения просмотренного префикса в возрастающем порядке, а последний записанный элемент равен последнему различному значению этого префикса.

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

и строгое возрастание values.

10. Объединение без повторов: Даны два неубывающих массива, каждый может содержать повторы. Построить новый неубывающий массив всех значений, встречающихся хотя бы в одном входе, причём каждое значение присутствует один раз. Array.Sort и коллекции запрещены. Самостоятельно спроектировать двухиндексный проход, пропуск серий равных значений и получение точного размера результата. Время — $O(n+m)$.

11. Нижняя и верхняя границы: Для неубывающего массива реализовать:

static int LowerBound(
    int[] data,
    int target)

static int UpperBound(
    int[] data,
    int target)

Первый метод возвращает минимальный индекс элемента >= target, второй — минимальный индекс элемента > target; при отсутствии такой позиции возвращается data.Length. Оба поиска работают на полуинтервале [lo, hi) за $O(\log n)$. По разности границ получить число вхождений, а при ненулевом количестве — первый и последний индексы цели.

12. Вставка в упорядоченный массив фиксированной ёмкости: Массив длины capacity заполнен только на префиксе [0, count), который неубывает; выполняется 0 <= count < capacity. Вставить значение после всех равных элементов, сохранив порядок. Позицию определить бинарным поиском по логическому префиксу, затем сдвинуть хвост справа налево и увеличить count. Вернуть новую длину и позицию. Доказать инвариант поиска позиции и отдельный инвариант безопасного сдвига.

13. Устойчивая сортировка слиянием: Даны параллельные массивы keys и originalOrder одинаковой длины. Спроектировать рекурсивную сортировку слиянием с одним заранее созданным вспомогательным массивом для каждого из двух входов. Полуинтервал [left, right) делится пополам до длины 0 или 1, затем две упорядоченные части устойчиво сливаются; при равных ключах выбирается левая часть. Подсчитать сравнения и записи, доказать глубину $O(\log n)$, время $O(n\log n)$ и дополнительную память $O(n)$. После сортировки отдельно проверить порядок ключей и устойчивость меток.

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

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

1. Границы массива и пустой вход: В отдельных копиях проекта исследовать:

• new int[0];
• чтение data[0] из пустого массива;
• чтение data[data.Length - 1] при Length == 0;
• цикл с условием i <= data.Length;
• обращение по индексу -1;
• затравку минимума через data[0] без предусловия непустоты;
• создание массива с отрицательной длиной из переменной времени выполнения.

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

2. for, foreach и изменение элементов: Для массива [1, 2, 3, 4] сравнить:

1. чтение и суммирование через foreach;
2. попытку присвоить новое значение переменной цикла foreach;
3. изменение data[i] через индексированный for;
4. foreach с отдельным индексом, который во время текущей итерации изменяет следующий элемент массива.

До сборки и запуска предсказать диагностику и последовательность наблюдаемых значений. Объяснить, почему переменная foreach для элемента типа int не является записываемым местом массива, почему индексированный проход естественен для преобразования и почему изменение ещё не прочитанных элементов меняет вход последующих итераций.

3. Достаточность состояния максимального подмассива: Реализовать три версии:

• полный перебор всех границ с повторным суммированием $O(n^3)$;
• перебор начала с накапливаемой суммой $O(n^2)$;
• алгоритм Кадане $O(n)$.

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

4. Устойчивость как независимое свойство: Для ключей [2, 2, 1, 2] и меток ["A", "B", "C", "D"] реализовать устойчивую сортировку вставками и обычную сортировку выбором, переставляя параллельные элементы согласованно. До запуска предсказать порядок меток среди ключей 2. Затем применить Array.Sort(keys, labels) к отдельной копии и объяснить, почему наблюдаемый на одном входе порядок не является гарантией устойчивости. Разделить два свойства: корректная неубывающая последовательность ключей и сохранение относительного порядка равных ключей.

5. Инвариант, прогресс и арифметика бинарного поиска: Сравнить корректный поиск на [lo, hi) с ошибочными вариантами:

• lo = mid вместо mid + 1;
• смешение закрытой и полуоткрытой правой границы;
• запуск на неупорядоченном массиве.

Потенциально незавершающуюся версию ограничить отдельным аварийным счётчиком. Для малых входов выписать трассы lo, mid, hi. Затем без создания огромного массива исследовать вычисление середины для виртуального диапазона около int.MaxValue формулами (lo + hi) / 2 и lo + (hi - lo) / 2. Объяснить потерю прогресса, нарушение локализации цели, выход за границы и переполнение суммы индексов.

6. Цена предварительного упорядочивания: Для неизменяемого массива длины $n$ и $q$ запросов принадлежности сравнить:

1. $q$ линейных поисков;
2. поэлементную копию, одну сортировку через Array.Sort и $q$ бинарных поисков.

Для $n=16,64,256,1024$ и нескольких $q$ считать сравнения собственных поисков; стоимость сортировки учитывать асимптотически как $O(n\log n)$. Сопоставить

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

7. Бинарная вставка не делает сортировку линейно-логарифмической: Реализовать две устойчивые сортировки вставками параллельных массивов:

1. линейный поиск позиции вставки;
2. бинарный поиск позиции после всех равных ключей.

Для обеих считать сравнения ключей и перемещения элементов. До запуска предсказать поведение на упорядоченном, обратном и случайном входах. Показать, что бинарный поиск уменьшает число сравнений до $O(n\log n)$, но сдвиги массива по-прежнему могут иметь суммарную стоимость $O(n^2)$; следовательно, общий класс сортировки остаётся квадратичным.

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

Итог модуля

Ученик создаёт и безопасно обходит одномерные массивы, выводит допустимые границы из Length, различает нейтральное начало накопителя и затравку первым элементом и строит инварианты обработанного префикса, суффикса или интервала. Методы над массивами имеют явный контракт изменения на месте, логической длины либо создания нового результата; массивы передаются как аргументы, возвращаются из методов и принимаются через params. Ученик реализует линейный поиск, статистику, разворот, сдвиг, фильтрацию, слияние, префиксные суммы, двухиндексные и однопроходные алгоритмы, устойчивые сортировки и бинарные границы. Корректность и выбор решения обосновываются предусловием упорядоченности, отношением порядка, устойчивостью, числом проходов, дополнительной памятью и классами $O(n)$, $O(\log n)$, $O(n^2)$ и $O(n\log n)$.

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

• Создание, инициализация, значения по умолчанию, Length, допустимые индексы и пустой массив: I.1, III.1.
• Индексированный обход, foreach, нейтральные накопители и затравка первым элементом: I.2–I.5, III.2.
• Линейный поиск, подсчёт, сумма, минимум, максимум и однопроходное состояние: I.3–I.5, II.1–II.4.
• Сдвиг, разворот и согласованное движение двух индексов: I.7–I.8, II.5–II.8.
• Фильтрация, слияние, логическая длина и массив точного размера: I.9–I.10, II.4–II.10.
• Изменение на месте, сохранение входа, новый результат и дополнительная память: I.6–I.12, II.3–II.13.
• Массив как аргумент и результат, изменение элементов и params: I.2–I.12, II.1–II.13.
• Простая процедурная сортировка, сортировка по ключу и устойчивость: I.11, II.13, III.4 и III.7.
• Array.Sort, его цена и отсутствие предполагаемой устойчивости: I.12, III.4 и III.6.
• Бинарный поиск, нижняя и верхняя границы, сокращение диапазона и предусловие порядка: I.12, II.11–II.12, III.5–III.7.
• Классы $O(n)$, $O(\log n)$, $O(n^2)$, $O(n\log n)$ и сравнение альтернатив: I.10–I.12, II.2–II.3, II.7, II.10–II.13, III.3–III.7.

За границей: точная семантика копирования ссылки, идентичность массивов, несколько ссылок на один объект, поверхностная и глубокая копия относятся к Модулю 6 и Разделу 16. Многомерные и зубчатые массивы рассматриваются в следующих модулях. Index, Range, Span<T>, обобщённые коллекции, LINQ, пользовательские компараторы, делегаты и лямбда-выражения относятся к Курсу II. Профессиональные сортировки, внешняя память и доказательство общей нижней границы сравнительной сортировки в модуль не входят.