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

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

• • именем;
• • размерностью;
• • типом элементов.

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

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

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

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

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

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

Рассмотрим вектор Л, состоящий из семи элементов со значениями: 3, 25, 18, 2, 7, 11,9.

Первый элемент вектора Л обозначается Л (1), второй — Л (2) и т. д. Любой элемент вектора обозначается Л (/), где i — индекс, который может принимать значения диапазона 1 < i < 7.

При i = 1 Л (г) = 30 или Л (1) = 30; при i = 5 А (/) = 7 или Л (5) = 7.

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

Задача 5.

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

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

Блоки 2—5 описывают циклический процесс ввода элементов одномерного массива в память. Блоки 7—10 предназначены для организации цикла накопления суммы элементов массива «нарастающим итогом». В блоке 6 для хранения суммы значений элементов массива определяется «чистая» область памяти.

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

В каждом из циклов выполняется последовательная обработка элементов массива, так как параметром цикла является индексированная переменная, принимающая значения от 1 до 7 с шагом +1.

Задача 6.

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

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

Оба цикла выполняют последовательную обработку элементов массива, однако во втором цикле в расчетах (блоки 11, 12) участвуют только те элементы, значения которых удовлетворяют условию, заданному в блоке 10.

Задача 7.

Упорядочить по возрастанию значений элементы числового массива Л, содержащего 10 элементов.

Процесс упорядочивания информации по определенному признаку называется сортировкой. Как правило, алгоритм сортировки используется с целью облегчения последующего поиска нужного значения в массиве. Существует много методов сортировки, соответственно и алгоритмов их реализации. Для решения задачи используем один из наиболее простых — метод обменов (или пузырьковый метод). Он основывается на сравнении пары соседних элементов. Если расположение элементов не удовлетворяет условиям сортировки, то их меняют местами. Сравнение и перестановки продолжаются до тех пор, пока не будут упорядочены все элементы. Определить, что элементы упорядочены, можно, фиксируя факт перестановки присваиванием некоторой переменной (п) значения, например true. До начала сравнения элементов эта переменная должна иметь другое значение, например false. Если после сравнения всех элементов значение переменной остается равным false, то это означает, что все элементы упорядочены.

Блок-схема алгоритма решения задачи 7 приведена на рис. 4.15. Блоки 2—5 описывают циклический процесс ввода элементов одномерного массива в память. В блоке 6 переменной п присваивается значение false. Блоки с 7 по 12 предназначены для организации цикла, в котором выполняется парное сравнение элементов массива (блок 8). Так как условием является сравнение элемента с индексом i и элемента с индексом i + 1, то индексированная переменная (параметр цикла) изменяет свое значение от 1 до 9 с шагом +1. Если условие выполнится хотя бы для одной пары элементов, то после операции обмена значениями двух элементов массива (блок 9) переменной п присваивается значение true (блок 10). Блок 11 является инвариантом цикла с постусловием. Если условие истинно, то выполняется тело цикла с постусловием (блоки с 6 по 12). Блоки 14—17 описывают циклический процесс вывода элементов одномерного массива.

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

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

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

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

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

• • при i = 1 wj = 2: В (i_yj) = 2;
• • при i = 3 иу = 1: В (i_yj) = 10 и т. д.

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

Задача 8.

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

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

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

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

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

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

Задача 9.

В произвольной матрице определить значение максимального элемента и его координаты (номер строки и номер столбца).

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

Для определения произвольной матрицы необходимо организовать по запросу ввод количества строк (п) и столбцов матрицы (к). Блок-схема алгоритма решения этой задачи показана на рис. 4.18.

Поиск максимального элемента выполним следующим образом. Запомним в качестве максимального (переменная М) первый элемент матрицы (блок 10) и сохраним значения его индексов (блоки 11 и 12).

Затем с помощью вложенных циклов в блоках с 13 по 22 последовательно просматриваем элементы матрицы, сравнивая их с максимальным значением. Если очередной элемент A (i, j) больше ранее найденного максимального значения (переменная М), то сохраняем его (блок 16) и его индексы (блоки 17, 18).

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

Вопросы и задания для самоконтроля

• 1. Какие существуют этапы подготовки задач к решению на компьютере?
• 2. Что представляет собой этап постановки задачи?
• 3. Что представляет собой этап алгоритмизации?
• 4. Что представляет собой этап программирования?
• 5. Что представляет собой этап отладки программы?
• 6. Что такое алгоритм?
• 7. Каковы основные свойства алгоритмов?
• 8. Какие способы изображения алгоритмов вам известны?
• 9. Что называется блок-схемой алгоритма?
• 10. Какие виды вычислительных процессов вам известны?
• 11. Какой вычислительный процесс называется линейным?
• 12. Какой вычислительный процесс называется ветвящимся?
• 13. Какой вычислительный процесс называется циклическим?
• 14. Какие виды циклов вам известны?
• 15. Что такое массив? Какие характеристики массива вы знаете?
• 16. Что такое размерность массива?
• 17. В чем отличие двумерного массива от одномерного массива?
• 18. Какие типовые операции можно выполнять над элементами массива?
• 19. Что такое сортировка?