Краткое содержание: Параграф § 1.4 / Информатика 9 класс

Обработка одномерных массивов целых чисел на языке Паскаль

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

Описание массива в Паскале происходит с использованием конструкции var <имя массива>: array [<нач. знач. индекса>..<кон. знач. индекса>] of <тип элементов>;. Например, var A: array [1..8] of integer; описывает массив A из 8 целых чисел с индексами от 1 до 8.

Обращение к элементу массива осуществляется по имени массива и индексу в квадратных скобках, например, A[i]. Индекс может быть константой, переменной или арифметическим выражением, результат которого должен находиться в диапазоне индексов массива.

Рассмотрены различные способы заполнения массива: ввод с клавиатуры, генерация случайных чисел, присвоение значений по формуле или константами в разделе const.

Вывод массива также выполняется в цикле, используя процедуры write или writeln, часто с указанием индекса элемента для наглядности.

Отдельное внимание уделяется вычислению суммы элементов массива. Алгоритм включает инициализацию переменной-аккумулятора (например, s := 0) и последовательное добавление к ней каждого элемента массива в цикле: s := s + A[i].

Последовательный поиск в массиве включает задачи нахождения наибольшего/наименьшего элемента, поиска элемента, равного заданному значению \( x \), и подсчета количества элементов, удовлетворяющих условию (например, if A[i] mod 2 = 0 then k := k + 1;). Обсуждается использование инварианта цикла для обоснования корректности циклических алгоритмов.

Новым и важным алгоритмом является сортировка массива (упорядочение) — перераспределение его элементов в определенном порядке (по возрастанию или невозрастанию). В качестве примера подробно рассмотрен алгоритм сортировки выбором, который осуществляется следующим образом:

• На каждой итерации в несортированной части массива ищется максимальный (или минимальный) элемент.
• Найденный максимальный элемент меняется местами с первым элементом несортированной части (или с последним в случае сортировки по убыванию).
• Этот процесс повторяется до тех пор, пока весь массив не станет отсортированным.

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

Также рассматриваются два основных подхода к обработке набора однотипных данных:

• Обработка массива: Все элементы сохраняются в памяти компьютера, что позволяет многократно обращаться к любому элементу по его индексу. Этот подход требует больше памяти.
• Обработка последовательности: Элементы считываются по одному (например, с клавиатуры или из файла), обрабатываются, и только текущий элемент может храниться в памяти. Ранее введенные элементы теряются. Этот подход экономичен по памяти, но не подходит для задач, требующих повторного доступа к данным или сортировки.

Вводится понятие линейного односвязного списка как альтернативной структуры данных, которая может использоваться вместо массивов в современных приложениях. Список — это последовательность связанных элементов, которые могут быть разбросаны в оперативной памяти. В отличие от массива, доступ к \( k \)-му элементу в списке осуществляется последовательно (пошагово), что называется последовательным доступом, а не произвольным (прямым) доступом по индексу. Элементы списка связаны через хранение адреса следующего элемента. Списки обеспечивают более эффективное использование оперативной памяти по сравнению с массивами, когда заранее неизвестен объем данных.