ЗАНЯТИЕ 23. Циклические алгоритмы

Прежде чем приступить к основной теме параграфа, следует рассмотреть основные определения:
 цикл — повторение одних и тех же действий (шагов).
 тело цикла — последовательность действий, которые повторяются в цикле
 итерация — однократное исполнение тела цикла;
 условие выхода (условие окончания) — выражение, которое определяет, станет ли в очередной раз выполняться итерация либо произойдёт завершение цикла;
 счётчик цикла — переменная, которая сохраняет номер итерации.
Счётчик не обязательно должен содержаться в цикле и счётчик совсем не обязательно должен быть один, то есть условие выхода порой зависит от нескольких изменяемых переменных. Вдобавок к этому, условие выхода иногда зависит от внешних условий (как пример — наступление определённого времени).
Работа любого цикла вне зависимости от его вида включает в себя:
 первоначальную инициализацию циклических переменных;
 проверку условия выхода из цикла;
 выполнение тела;
 обновление циклической переменной на каждой итерации.
11.1 Виды циклических алгоритмов
Существует несколько типов алгоритмов циклической структуры.
 Циклы со счетчиком или по параметру, в которых какие-то действия выполняются определенное число раз;
 Циклы с условием, в которых тело цикла выполняется, в зависимости от какого-либо условия.
Циклы со счетчиком используют, когда заранее известно какое число повторений тела цикла необходимо выполнить
Циклы в которых сначала проверяется условие, а затем, возможно, выполняется тело цикла называют циклы с предусловием (рис 10 ). Если условие проверяется после первого выполнения тела цикла, то циклы называются циклы с постусловием (рис 11 ).

Цикл с предусловием — это основная, но не единственная форма организации циклических алгоритмов. Другим вариантом является цикл с постусловием. Вернемся к алгоритму решения квадратного уравнения. К нему можно подойти с такой позиции: если a = 0, то это уже не квадратное уравнение и его можно не рассматривать. В таком случае будем считать, что пользователь ошибся при вводе данных, и следует предложить ему повторить ввод. Иначе говоря, в алгоритме будет предусмотрен контроль достоверности исходных данных с предоставлением пользователю возможности исправить ошибку. Наличие такого контроля — еще один признак хорошего качества программы.
В общем виде структурная команда цикл с постусловием или цикл—до. Здесь используется условие окончания цикла. Когда оно становится истинны, цикл заканчивает работу.
Рассмотрим следующую задачу: дано целое положительное число n. Требуется вычислить n! (n-факториал).
На рисунке приведена блок-схема алгоритма. В нем используются три переменные целого типа: n — аргумент; i — промежуточная переменная; F— результат. Для проверки правильности алгоритма построена трассировочная таблица. В такой таблице для конкретных значений исходных данных по шагам прослеживается изменение переменных, входящих в алгоритм. Данная таблица составлена для случая n = 3. Трассировка доказывает правильность алгоритма.

Выполнение серии команд (тела цикла) повторяется, пока условие цикла истинно. Когда условие становится ложным, цикл заканчивает выполнение.
И так циклические алгоритмы многократно используют часть действий для формирования результата решения задачи.
11.2 Массивы и матрицы
Массивы, как и циклы, — величайшее изобретение программирующего человечества. Массивы приходят на помощь тогда, когда приходится иметь дело с наборами однотипных и однородных данных (например, координаты точки в двумерном, трехмерном пространстве).
Массив – это упорядоченная последовательность однотипных элементов определенной длины, имеющая общее имя. Номер элемента в последовательности называется индексом. Количество элементов в массиве не может быть изменено в процессе выполнения программы. Элементы массива размещаются в памяти последовательно и нумеруются от 1 до n, где n – их количество в массиве. К каждому элементу массива имеется прямой доступ. Это означает, что для того чтобы обратиться к какому-либо элементу массива, нет нужды перебирать все его предыдущие элементы, достаточно указать номер этого элемента.
Массивы могут быть одномерными и многомерными.
Одномерные массивы – массивы, в которых элементы пронумерованы последовательно по порядку: первый элемент, второй, третий и т.д. Для обозначения элементов одномерного массива используется один индекс.
Двумерные массивы – массивы, в которых данные условно организованы в виде таблицы (матрицы), где положение каждого элемента определяется номером строки т номером столбца. Для обозначения элементов двумерного массива используются два индекса: первый индекс для обозначения номера строки, второй индекс для обозначения номера столбца.
По аналогии с математикой одномерные числовые массивы часто называют векторами, а двумерные – матрицами.
Значения индексов можно задать непосредственно числом (прямая адресация) – A(1), A(4,2) или косвенно, указав в индексе идентификатор переменной, которая позволит вычислить индекс (косвенная адресация) – A(i), A(i, j+2).
11.3 Алгоритмы обработки одномерных массивов
Пример 1. Пусть дан массив A, состоящий из n элементов: a1, a2, a3, …, an. Нужно найти их сумму, т.е. S=a1+a2+a3+…+an.
Нахождение суммы есть последовательное нахождение суммы по формулам:
S=0 S=S+a1 S=S+a2 S=S+a3 … S=S+ ai S=S+an
Алгоритм вычисления суммы удобно организовать циклом, взяв за параметр цикла переменную i, которая меняется от 1 до n с шагом 1, и записав в цикле формулу S=S+ai один раз. Схема алгоритма приведена на рис. 12.
В схеме блок 4 присваивает S нулевое значение, блок 5 счетчику i присваивает начальное значение, блок 6 выполняет накопление суммы, блок 7 изменяет значение i на 1, блок 8 осуществляет проверку условия повторения цикла. При выполнении этого условия управление передается в начало цикла, а при невыполнении – осуществляется выход из цикла, т.к. при i=n+1 суммировать не нужно. n – в схеме предполагается число, но n может быть и переменной, значение которой равно числу элементов массива A, которое нужно вводить перед описанием массива.
Пример 2 Определить максимальный элемент массива
Для получения максимального числа введем переменную M и ей присвоим значение первого элемента массива a1, а затем необходимо сравнить M с текущим элементом массива ai и если текущий элемент будет больше M, то значение M заменить на значение этого элемента. Схема алгоритма на Рис. 13. Очень важно обратить внимание учащихся на начальное значение переменной M. Почему, например нельзя переменной M присвоить значение равное нулю? (Ответ: Для массива с отрицательными значениями элементов максимум не будет найден.)

11.4 Алгоритмы обработки двумерных массивов
Двумерный массив – это структура однотипных элементов, расположенных в виде таблицы значений. Такое представление значений соответствует математическому понятию двумерного массива.
Каждый элемент в двумерном массиве идентифицируется номером строки и номером столбца, на пересечении которых он расположен.
Например, в двумерном массиве А, изображенном на рис. 14, элемент со значением 5 расположен на пересечении третьей строки и второго столбца.

Этот элемент будет обозначаться как А(3, 2). А элемент А(1, 4) имеет значение, равное нулю. Такое представление набора значений позволяет выполнять обработку как отдельных значений в двумерном массиве, так и последовательности значений, расположенных в строках или столбцах.
В дальнейшем будем считать, что для двумерного массива A(N, М) в обозначении элемента А(i, j) первое значение i соответствует номеру строки и изменяется от 1 до N, а j – номеру столбца и изменяется от 1 до М. В отличие от одномерного массива, в котором использовался только один номер для определения местоположения элемента и требовался только один цикл для ввода элементов, в двумерном массиве для обработки элементов необходимы два вложенных друг в друга цикла. Внешний цикл предназначен для изменения номера строки i, а второй, внутренний, – для изменения номера столбца j в текущей строке i.
На рис. 15 представлен простой алгоритм ввода элементов, построенный в виде структуры из вложенных циклов. В дальнейшем при рассмотрении алгоритмов обработки элементов двумерного массива в целях сокращения их размера фрагмент ввода элементов будем заменять отдельным блоком ввода.

Пример 3. Составить алгоритм поиска максимального значения в двумерном массиве.
Поиск максимального элемента в двумерном массиве осуществляется аналогично поиску в одномерном массиве. Отличие состоит в том, что для обработки двумерного массива используем два вложенных цикла. Обозначим максимальный элемент переменной МАХ. Значение этой переменной будет меняться на каждой итерации цикла, если очередное значение элемента массива окажется больше МАХ (рис. 16).