Алгоритмизация задач обработки массивов.

Массивом называется совокупность элементов с одинаковыми свойствами. Любой массив характеризуется:

· именем;

· размерностью;

· типом элементов.

Каждый элемент массива имеет определенное значение, координаты своего местоположения в массиве и обозначается при помощи переменной с индексами. Количество индексов зависит от размерности массива.

Массивы могут быть одномерные, двумерные и т. д. В данном разделе остановимся на изучении массивов числового вещественного типа обычной точности.

Обработка любого массива представляет собой циклический вычислительный процесс (как правило, цикл с параметром), в котором параметрами циклов яв­ляются индексы, а в теле циклов используются выражения с индексированными переменными.

Основными видами задач обработки массивов являются:

· определение суммы значений элементов, произведения значений элементов и среднего арифметического для всех элементов массива;

· определение суммы значений, произведения значений, количества элементов и среднего арифметического для элементов массива, удовлетворяющих определенным условиям;

· определение максимального (минимального) по значению элемента и его местоположения в массиве;

· упорядочение значений элементов в массиве.

Одномерный массив носит название вектора. Элементы одномерного массива имеют по одному индексу. Этот индекс соответствует номеру элемента в векторе.

Рассмотрим вектор A, состоящий из 7 элементов значениями: 30, 25, 18, 20, 7, 11, 9. Любой элемент этого вектора обозначается A(i), где i -индекс, 1 <= i <= 7.

При i=1 A(i) = 30 или A(1)= 30;

при i= 5 A (i) = 7 или A (5) = 7.

Элементы одномерного массива располагаются один за другим в последова­тельно расположенных байтах памяти. Рассмотрим типовые задачи обработки вектора.

Задача 5. Определить и вывести сумму значений элементов в массиве A, содержащем 7 элементов.

Блок-схема алгоритма решения данной задачи представлена на рис.40.

Как видно из схемы, процесс решения поставленной задачи включает в себя два последовательно расположенных цикла с параметром.

Блоки 2, 3, 4 и 5 описывают циклический процесс ввода элементов одномерного массива в память. Блоки 7, 8, 9, 10 предназначены для организации цикла накопления суммы элементов массива “нарастающим итогом”. При решении задач подсчета суммы значений элементов массива определяется “чистая“ область памяти, в которой должна накапливаться сумма (блок 6).

Задача 6. Определить количество и сумму значений отрицательных элементов в векторе.

Как видно, постановка задачи дана в общем виде. Блок-схема алго­ритма решения такой задачи приведена на рис.41. В блоке 2 осуществляется ввод количества элементов массива (в переменную n). Блоки 3, 4, 5, 6 описывают ввод в цикле n элементов массива с произвольно заданным именем V. В блоке 7 подготавливается область памяти для подсчета произведения значе­ний элементов (p = 1), а в блоке 8 - для подсчета количества элементов(k=0).

Блоки 9 - 14 организуют циклический процесс подсчета количества и произведения значений отрицательных элементов.

 

1 начало   i=1   ввод A (i)   i = i + 1     i £ 7     S = 0   i = 1 S = S + A (i)   i = i + 1   10 i £ 7     вывод S   конец

нет   да

начало ввод n   i = 1 ввод V (i)   i = i + 1   i £ n   нет P = 1   n = 0   i = 1   V (i) < 0         i = i + 1   i £ n вывод P, k   конец

да   P=P* V(i)   K = K+1

Рис. 40 Блок-схема алгоритма Рис. 41 Блок-схема алгоритма решения задачи 5. решения задачи 6

 

. Двухмерный массив носит название матрицы. Рассмотрим числовую матрицу B, состоящую из 4 строк и 3 столбцов (см. рис. 42).

 

 

3 2 8

1 6 9

1<= i<=4 10 4 7

5 2 1

1<=j<=3

Рис. 42. Пример числовой матрицы, состоящей из 4 строк и 3 столбцов.

 

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

Если номер строки обозначить буквой i, а номер столбца - буквой j, то для рассматриваемой нами матрицы B (см. рис. 42) будут справедливы следующие утверждения:

при i = 1 и j = 2 B(i,j)= 2; при i = 3 и j = 1 B(i,j)= 10 и т.д.

Рассмотрим типовые задачи обработки двухмерных массивов.

Задача 7. Определить и вывести среднее арифметическое для элементов матрицы B, состоящей из 4 строк и 3 столбцов.

Среднее арифметическое представляет собой отношение суммы значений элементов к количеству этих элементов. Количество в данной задаче определять не нужно, т.к. оно известно (4 * 3), поэтому основная обработка сводится к определению суммы значений элементов.

Блок - схема алгоритма решения этой задачи приведена на рис.43.

На схеме хорошо видны два последовательно расположенных циклических участка: один - для организации ввода данных (блоки 2- 8), другой - для организации вычисления суммы значений элементов матрицы (блоки 10 -16).

Каждый из этих циклических участков представляет собой вложенные циклы.

Вложенными называются циклы, расположенные один в другом. Цикл, являющийся внешним, включает в свое тело внутренний цикл полностью.

Так на схеме (рис. 43) можно различить заголовок внешнего цикла c параметром i (блоки 2,7,8), тело внешнего цикла (блоки 3, 4, 5, 6), которое представляет собой внутренний цикл с параметром j со своим заголовком (блоки 3, 5, 6) и телом цикла (блок 4).

 

1 начало   i=1   j = 1   ввод B (i, j)   j = j + 1   да 6 j £ 3   i = i + 1   ДА i £ 4   9 нет S = 0     i = 1   j = 1   S = S + B (i,j)   j = j + 1     да 14 j £ 3 нет i = i + 1   да 16 i £ 4 нет S = S/12   вывод S   конец

 

 

Рис.43. Блок-схема алгоритма решения задачи 7.

 

1 начало   ввод n, k   i = 1   j = 1   ввод A (i, j)   j = j + 1   да i £ k   8 нет i = i + 1     9 i £ n     M = A (1,1)     T = 1     L = 1   i = 1     j = 1     нет 15 да A (i, j) < M   M = A (i, j)     T = i   L = j     j = j + 1

A B C