Название: Алгоритмы и программы (Афанасьева Т. В.)

Жанр: Информационные системы и технологии

Просмотров: 1424

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