Название: Алгоритмы и программы (Афанасьева Т. В.) Жанр: Информационные системы и технологии Просмотров: 1366 |
2.7. алгоритмы обработки одномерных числовых массивов
Под структурой данных типа массив понимают однородную структуру однотипных данных, одновременно хранящихся в последо- вательных ячейках оперативной памяти. Эта структура должна иметь имя и определять заданное количество данных (элементов). Однотипность данных определяет возможность использования циклических алгоритмов для обработки всех элементов массива. Количество итераций цикла определяется количеством элементов массива. Одновременное хранение в памяти всех элементов массива позволяет многократно обращаться к элементу массива и решать большой набор задач, таких как поиск элементов, упорядочение и изменение порядка следования элементов. Доступ к любому элементу массива осуществляется по его номеру (индексу). Поэтому для обращения к элементу массива используют имя массива (номер элемента), например, А(5). элементам достаточно одной индексной переменной. Рассмотрим простой алгоритм ввода элементов одномерного числового массива A из 9 элементов. В этом циклическом алгоритме условие выхода из цикла определяется значением специальной пере- менной К, которая называется счетчиком элементов массива А (рис. 16). Эта же переменная К определяет количество итераций циклического алгоритма ввода элементов массива. На каждом шаге итерации переменная К (значение номера элемента массива А) изменяется на 1, то есть происходит переход к новому элементу массива. В дальнейшем, при рассмотрении алгоритмов обработки одномерных массивов в целях устранения дублирования алгоритм ввода элементов массива будем заменять одним блоком, подразумевая, что он реализуется по схеме циклического алгоритма, представленного на рис. 16.
Пример 9. Составить алгоритм определения в одномерном числовом массиве А из N элементов суммы положительных элементов. Решение. Алгоритм представлен на рисунке 17. В этом алгоритме переменная К является счетчиком элементов массива, S – сумма элементов массива, она вычисляется по рекуррентной формуле S=S+A(K). Ввод количества и значений элементов массива осуществляется сначала в отдельном блоке ввода, который реализуется по схеме алгоритма ввода элементов массива, изображенного на рис. 16.
НАЧАЛО
N, A(N)
K:=1
K:= 1
– K<=9
+
Ввод А(к)
К:=К+1
КОНЕЦ
K <= N
+
A(K) > 0
– Вывод S
КОНЕЦ
+ S:= S+A(k)
Рис. 16. Алгоритм ввода элементов
K:= K + 1
Рис. 17. Алгоритм вычисления суммы положительных элементов массива Пример 10. Составить алгоритм поиска элемента с максимальным значением в одномерном массиве А(1..n) и его таблицу трассировки для значений (3, 7, 0, 9). Решение. Введем обозначения: K – текущий номер элемента, A[K] – текущее значение элемента массива, N=4 – количество элементов одномерного массива, M – номер максимального элемента массива, A[M] – значение максимального элемента массива. Основной идеей алгоритма является выполнение сравнения текущего элемента массива A[K] и элемента с максимальным значением A[М], определенным на предыдущем шаге итерации. По алгоритму, изображенному на рис. 18, получено максимальное значение для массива (3, 7, 0, 9), процесс и правильный результат поиска которого показаны в табл. 3.
Таблица трассировки алгоритма примера 10 Таблица 3
|
|