Алгоритмизация задач обработки массивов
Массивом называется упорядоченная совокупность элементов с одинаковыми свойствами. Любой массив характеризуется:
· именем;
· размерностью;
· типом элементов.
Каждый элемент массива имеет определенное значение и один или несколько индексов, определяющих его местоположение в массиве. Индексы образуют упорядоченные последовательности. Количество индексов зависит от размерности массива.
Массивы могут быть одномерные, двумерные и т. д. В данном разделе остановимся на рассмотрении типовых алгоритмов обработки числовых массивов.
Обработка любого массива представляет собой циклический вычислительный процесс (как правило, цикл с параметром), в котором параметрами циклов являются индексы, а в теле циклов используются выражения с индексированными переменными.
К основным видами задач обработки массивов относятся:
· определение суммы значений элементов, произведения значений элементов и среднего арифметического для всех элементов массива;
· определение суммы значений, произведения значений, количества элементов и среднего арифметического для элементов массива, удовлетворяющих определенным условиям;
· поиск максимального (минимального) по значению элемента и определение его местоположения в массиве;
· упорядочение значений элементов в массиве.
Одномерный массив носит название вектора. Элементы одномерного массива имеют по одному индексу. Этот индекс соответствует номеру элемента в векторе.
Рассмотрим вектор 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 элементов.
Блок-схема алгоритма решения данной задачи представлена на рис.6.13. Как видно из схемы, процесс решения поставленной задачи включает в себя два последовательно расположенных цикла с параметром.
Блоки 2, 3, 4 и 5 описывают циклический процесс ввода элементов одномерного массива в память. Блоки 7, 8, 9, 10 предназначены для организации цикла накопления суммы элементов массива “нарастающим итогом”. При решении задачи подсчета суммы значений элементов массива определяется “чистая“ область памяти, в которой должна накапливаться сумма (блок 6).
                                                             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
k = 0
i = 1
V ( i ) < 0
i = i + 1
вывод P, k
конец
| P=P* V(i) k = k +1 |
|
В каждом из циклов выполняется последовательная обработка элементов массива, так как параметром цикла является индексированная переменная, принимающая значения от 1 до 7 с шагом +1.
Задача 6.Определить количество и произведение значений отрицательных элементов в векторе.
Как видно, постановка задачи дана в общем виде, размер массива не задан. Блок-схема алгоритма решения такой задачи приведена на рис.6.14. В блоке 2 осуществляется ввод количества элементов массива (в переменную n). Блоки 3, 4, 5, 6 описывают ввод в цикле n элементов массива с произвольно заданным именем V. В блоке 7 подготавливается область памяти для подсчета произведения значений элементов (p = 1), а в блоке 8 - для подсчета количества элементов (k=0). Блоки 9 - 14 организуют циклический процесс подсчета количества и произведения значений отрицательных элементов.
Оба цикла выполняют последовательную обработку элементов массива, однако во втором цикле в расчетах (блоки 11,12) участвуют только те элементы, значения которых удовлетворяют условию, заданному в блоке 10.
Задача 7.Упорядочить по возрастанию значений элементы числового массива A, содержащего 10 элементов.
Процесс упорядочивания информации по определенному признаку называется сортировкой. Цель сортировки – облегчение последующего поиска элементов. Существует много методов сортировки, соответственно и алгоритмов их реализации. Для решения задачи используем один из наиболее простых метод обменов (или пузырьковый метод). Данный метод основывается на сравнении пары соседних элементов. Если расположение элементов не удовлетворяет условиям сортировки, то их меняют местами. Сравнение и перестановки продолжаются до тех пор, пока не будут упорядочены все элементы. Определить, что элементы упорядочены можно фиксируя факт перестановки присваиванием некоторой переменной (n) значения, например true. До начала сравнения элементов эта переменная должна иметь другое значение, например false. Если после сравнения всех элементов, значение переменной остается равной false, то это означает, что все элементы упорядочены.
Блок-схема алгоритма решения задачи 7 приведена на рис. 6.15. Блоки 2, 3, 4 и 5 описывают циклический процесс ввода элементов одномерного массива в память. В блоке 6 переменной n присваивается значение false. Блоки с 7 по 12 предназначены для организации цикла, в котором выполняется парное сравнение элементов массива (блок 8). Так как условием является сравнение элемента с индексом i и элемента с индексом i+1, то индексированная переменная (параметр цикла) изменяет свое значение от 1 до 9 с шагом +1. Если условие выполнится хотя бы для одной пары элементов, то после операции обмена значениями двух элементов массива (блок 9), переменной n присваивается значение true (блок 10). Блок 11 является инвариантом цикла с постусловием. Если условие истинно, то выполняется тело цикла с постусловием (блоки с 6 по 12). Блоки 14,15,16 и 17 описывают циклический процесс вывода элементов одномерного массива.
| 
|
| Рис. 6.15. Блок-схема алгоритма решения задачи 7. |
Двумерный массив носит название матрицы. Рассмотрим числовую матрицу B,состоящую из4 строк и 3 столбцов (см. рис. 6.16).
3 2 8