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

Основные сведения о массивах и их обработке в Python

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

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

Обращение к элементам и заполнение массива

Обращение к конкретному элементу в одномерном массиве (списке) осуществляется с помощью имени массива и индекса элемента, заключенного в квадратные скобки, например, \(A[i]\). Важной особенностью Python является то, что нумерация элементов всегда начинается с нуля, то есть первый элемент имеет индекс \(0\). Для одномерного массива \(A\) с \(N\) элементами, индексы варьируются от \(0\) до \(N-1\). Длина массива может быть получена с использованием встроенной функции \(len()\), например, \(N = len(A)\).

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

• перечислением элементов: \(A = [1, 2, -3, 5, 7]\);
• заполнением нулями (или другим значением): \(A = [0] * N\), что создает массив из \(N\) элементов, каждый из которых равен \(0\);
• вводом данных с клавиатуры: с использованием цикла \(for\) и функции \(input()\);
• заполнением случайными числами: с помощью функции \(randint()\) из модуля \(random\). Например, \(A[i] = randint(0, 99)\) присвоит элементу \(A[i]\) случайное целое число из отрезка \([0, 99]\).

Вывод массива и вычисление суммы элементов

Для отображения содержимого массива \(A\) на экран можно использовать простейший способ \(print(A)\), который выведет его элементы в квадратных скобках через запятую. Более контролируемый вывод, например, в строку или столбец, реализуется через цикл \(for\).

Задача вычисления суммы элементов массива \(A\) (длиной \(N\)) решается путем последовательного накопления слагаемых в специальной переменной-аккумуляторе \(s\). Алгоритм включает:

• Инициализацию переменной-аккумулятора: \(s = 0\).
• Циклическое сложение: в цикле, повторяющемся \(N\) раз (для индексов от \(0\) до \(N-1\)), к переменной \(s\) прибавляется значение текущего элемента массива: \(s = s + A[i]\).

Блок-схема этого алгоритма демонстрирует последовательность действий: начало \(\rightarrow\) ввод \(N\) и \(A[i]\) \(\rightarrow\) инициализация \(s = 0\) \(\rightarrow\) цикл по \(i\) от \(0\) до \(N-1\) \(\rightarrow\) \(s = s + A[i]\) \(\rightarrow\) вывод \(s\) \(\rightarrow\) конец.

Последовательный поиск в массиве

Последовательный поиск (sequential search) представляет собой фундаментальный алгоритм для решения невычислительных задач, часто встречающихся в программировании. Основные типы задач поиска включают:

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

Решение этих задач базируется на организации последовательного просмотра всех элементов массива и сравнении каждого элемента с неким образцом или условием.

Алгоритм поиска наибольшего элемента

Для нахождения наибольшего элемента (или его индекса \(imax\)) используется метод последовательного просмотра, основанный на инварианте цикла. Инвариант цикла — это логическое условие, которое остается истинным до начала выполнения цикла и после каждого шага его тела. В контексте поиска наибольшего элемента, инвариантом является: «значение, записанное на доске (или хранящееся в переменной, например \(A[imax]\)), является наибольшим среди всех просмотренных к текущему моменту элементов массива».

Алгоритм реализуется следующим образом:

1. Инициализация: Присвоить переменной \(imax\) индекс первого элемента массива (\(0\)): \(imax = 0\).
2. Цикл сравнения: Просматривать элементы массива, начиная со второго (\(i=1\)) до последнего (\(N-1\)).
3. Обновление максимума: Если текущий элемент \(A[i]\) больше элемента \(A[imax]\), то обновить индекс \(imax\): \(imax = i\).

В результате, после завершения цикла, \(A[imax]\) будет содержать значение наибольшего элемента, а \(imax\) — его индекс (в случае нескольких одинаковых максимальных элементов, будет найден индекс первого из них).

Поиск элемента, равного заданному значению

Для поиска элемента \(x\) в массиве \(A\) используется переменная \(nx\), инициализированная значением \(-1\), которая будет хранить индекс найденного элемента. Если после просмотра всего массива \(nx\) остается равным \(-1\), то элемент не найден. Для ускорения процесса, если требуется найти только первое вхождение элемента, после его нахождения используется оператор \(break\) для немедленного выхода из цикла.

Подсчет и суммирование элементов по условию

Для подсчета количества элементов, удовлетворяющих некоторому условию, используется переменная-счетчик \(k\), которая увеличивается на единицу каждый раз, когда элемент удовлетворяет условию. Для суммирования значений элементов, удовлетворяющих условию, используется переменная-аккумулятор \(s\).

Сортировка массива

Под сортировкой (упорядочением) массива понимается перераспределение его элементов в некотором определенном порядке. Массив может быть отсортирован по неубыванию (каждый следующий элемент не меньше предыдущего) или по невозрастанию (каждый следующий элемент не больше предыдущего). Целью сортировки является облегчение последующего поиска нужных элементов.

Одним из методов является сортировка выбором (Selection Sort). Она осуществляется следующим образом:

1. Находится максимальный (или минимальный) элемент в неотсортированной части массива.
2. Этот элемент меняется местами с первым неотсортированным элементом (который находится в начале неотсортированной части).
3. Повторение шагов, пока весь массив не будет отсортирован.

Массивы и последовательности

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