Алгоритмы со структурами вложенных циклов

Нередко при алгоритмическом решении задачи возникает необходимость создания цикла, содержащего в своем теле другой цикл. Такие вложенные друг в друга циклы относятся к структурам вложенных циклов. Порядок вложенности циклов, когда в теле внутреннего цикла содержатся другие циклы, может быть достаточно большим. Этот порядок определяется методом, с помощью которого достигается решение поставленной задачи. Так, при обработке одномерных массивов, как правило, удается построить алгоритмическую схему без вложения циклов. Однако в ряде случаев при решении таких задач без вложенных циклов не обойтись.

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

Структура вложенных циклов:

Рис. 19. Структура вложенных циклов

Пример 1. Рассмотрим задачу сортировки одномерного массива А длины N. Отсортировать массив – значит расположить его элементы в порядке возрастания или убывания.

Опишем метод сортировки массива в порядке возрастания. Сначала выполняется проход по массиву с целью определения в нем наименьшего элемента. Затем производится перестановка этого элемента с первым. Далее совершается второй проход по массиву, начиная со второго элемента. Найденный наименьший элемент переставляется со вторым и т. д. После (N-1)-го прохода с выполнением названных операций массив окажется отсортированным.

Замечание. Перестановка элементов осуществляется с помощью «буферного» элемента. Поставим задачу: поменять местами элементы A_i и A_j одномерного массива (последовательности) A₁, A₂, …. A_n. Пусть С - буферный элемент. Тогда последовательность действий С=A_i, A_i = A_j, A_j=С осуществляет перестановку этих элементов в массиве {A}.

Задание. Построить блок-схему алгоритма сортировки одномерного массива А длины N.

Входные данные: неупорядоченная последовательность элементов A₁, A₂, …. A_n.

Выходные данные: упорядоченная последовательность элементов A₁, A₂, …. A_n.

Промежуточные данные: буферный элемент С, индексы текущих элементов i и j.

Блок-схема приведена на рис.20.

Рис. 20. Блок-схема алгоритма сортировки одномерного массива А длины N

Алгоритмы со структурами вложенных циклов часто используют при решении задач обработки двумерных массивов. В таких алгоритмах счетчики циклов используются для манипуляции с индексами массивов.

Пример 2. Дан двумерный массив А ( матрица ), состоящий из N строк и М столбцов. Найти сумму положительных и произведение отрицательных элементов этого массива.

Входные данные: двумерный массив А с элементами A_ij, где i – номер строки, j – номер столбца элемента.

Выходные данные: сумма S и произведение P элементов массива. Начальное значение суммы считается равным нулю (S=0), начальное значение произведения – единице (Р=1).

Промежуточные данные: индексы текущих элементов i и j.

Блок-схема приведена на рис.21.

Рис. 21. Блок-схема алгоритма вычисления суммы S и произведения P элементов массива