Оглавление:
Урок: Одномерные массивы целых чисел: заполнение, вычисление, поиск, сортировка
Одномерные массивы целых чисел
Мы будем рассматривать одномерные массивы.
Решение разнообразных задач, связанных с обработкой массивов, базируется на решении таких типовых задач, как:
- суммирование элементов массива;
- поиск элемента с заданными свойствами;
- сортировка массива.
Здесь oписан массив a из десяти целочисленных значений. При выполнении этого оператора в памяти компьютера будет выделено десять ячеек целого типа.
Небольшой массив с постоянными значениями может быть описан в разделе описания констант:
В этом случае не просто выделяются последовательные ячейки памяти — в них сразу же заносятся соответствующие значения.
Заполнение массива и вывод массива
Заполнение массива
Во многих случаях бывает полезно вывести значения элементов массива на экран. Так, если значения массива генерировались случайным образом, то необходимо знать, каков исходный массив. Также нужно знать, каким стал массив после обработки. Элементы массива можно вывести в строку, разделив их пробелом:
Более наглядным является следующий вариант вывода с комментариями:
Вычисление суммы элементов массива
Последовательный поиск в массиве
В программировании поиск — одна из наиболее часто встречающихся задач невычислительного характера.
Можно выделить следующие типовые задачи поиска:
- найти наибольший (наименьший) элемент массива;
- найти элемент массива, значение которого равно заданному значению.
Компьютер не может сравнить разом весь ряд объектов. На каждом шаге он может сравнивать только два объекта. Поэтому в программе необходимо организовать последовательный просмотр элементов массива и сравнение значения очередного просматриваемого элемента с неким образцом.
Рассмотрим подробно решение задач первого типа (нахождение наибольшего (наименьшего) элемента). Представим себе одномерный массив в виде стопки карточек, на каждой из которых написано число. Тогда идея поиска наибольшего элемента массива может быть представлена следующим образом:
- возьмём верхнюю карточку (первый элемент массива), запомним имеющееся на карточке число (запишем его мелом на доске) как наибольшее из просмотренных; уберём карточку в сторону;
- возьмём следующую карточку; сравним числа, записанные на карточке и на доске; если число на карточке больше, то сотрём число, записанное на доске, и напишем там то же число, что и на карточке; если же новое число не больше, то на доске оставим имеющуюся запись; уберём карточку в сторону;
- повторим действия, описанные в пункте 2, для всех оставшихся карточек в стопке.
В итоге на доске будет записано самое большое значение просмотренного массива.
Так как доступ к значению элемента массива осуществляется по его индексу, то при организации поиска наибольшего элемента в одномерном массиве правильнее искать его индекс.
Результатом решения задачи второго типа (нахождение элемента массива, значение которого равно заданному значению) может быть:
- n — индекс элемента массива такой, что a[n]=x, где x — заданное число;
- сообщение о том, что искомого элемента в массиве не обнаружено.
Алгоритм поиска в сформированном нами массиве a значения, равного 50, может выглядеть так:
n:=0; for i:=1 to 10 do if a[i]=50 then n:=i; if n=0 then write ('Нет') else write (i)
В этой программе последовательно просматриваются все элементы массива. Если в массиве несколько элементов, значения которых равны заданному числу, то программа найдет последний из них.
Во многих случаях требуется найти первый из элементов, имеющих соответствующее значение, и дальнейший просмотр массива прекратить. Для этой цели можно использовать следующую программу:
i:=0; repeat i:=i+1; until(a[i]=50) or (i=10); if a[i]=50 then write (i) else write ('Нет');
Здесь выполнение алгоритма будет прервано в одном из двух случаев:
- в массиве найден первый из элементов, равный заданному;
- все элементы массива просмотрены.
Зачастую требуется определить количество элементов, удолетворяющих некоторому условию. В этом случае вводится переменная, значение которой увеличивается на единицу каждый раз, когда найден нужный элемент.
Сортировка массива
- В массиве выбирается максимальный элемент;
- Максимальный и первый элементы меняются местами (первый элемент считается отсортированным);
- В неотсортированной части массива снова выбирается максимальный элемент; он меняется местами с первым неотсортированным элементом массива;
- Действия, описанные в пункте 3, повторяются с неотсортированными элементами массива до тех пор, пока не останется один неотсортированный элемент (его значение будет минимальным).
Рассмотрим процесс сортировки выбором на примере массива a={0,1,9,2,4,3,6,5}.
В этом массиве из восьми элементов операцию выбора максимального элемента мы проводили 7 раз. В массиве из n элементов такая операция будет проводиться n−1 раз.
Рекомендованный список литературы
Босова Л.Л. Информатика — Учебник для 8 класса. – М.: БИНОМ. Лаборатория знаний