Лабораторная работа №7
Линейные алгоритмы
Теоретические основы
Циклические структуры
Реализация на ЭВМ линейных и разветвляющихся программ не дает большого выигрыша во времени по сравнению, например, с использованием простого калькулятора. Настоящие преимущества вычислительной машины становятся очевидными лишь при решении тех задач, где возникает необходимость многократного повторения одних и тех же фрагментов алгоритмов.
Считается, что если бы в программах не было возможности организовать циклы, то применять ЭВМ для решения многих задач не имело бы смысла.
Циклическими называются алгоритмы, у которых выполнение некоторых операторов (групп операторов) осуществляется многократно с одними и теми же или модифицированными данными.
Циклические алгоритмы находят самое широкое применение в программировании, так как при этом человек составляет программу один раз, а ЭВМ выполняет ее многократно. Циклические алгоритмы часто называют циклами.
В зависимости от способа организации числа повторений различают три типа циклов: цикл с заданным условием продолжения работы, цикл с заданным условием окончания работы и цикл с заданным числом повторений.
Цикл с заданным условием продолжения работы
(цикл-ПОКА)
Логика работы такой структуры описывается схемой, показанной на рис. 1, а.
Рис. 1. Структура цикл-ПОКА: а – развернутая схема цикла;
б – запись в псевдокодах; в – компактная схема цикла
Тело цикла может включать в себя группу операторов любой степени сложности. При выполнении условия продолжения работы выполняется тело цикла, если же условие не выполняется, то работа циклической структуры заканчивается и начинает выполняться следующая структура основного алгоритма.
|
|
Цикл с заданным условием окончания работы
(цикл-ДО)
Структура цикл-ПОКА предусматривает вариант, когда тело цикла не выполняется ни разу. Такое возможно, если условие, стоящее в начале цикла, сразу же не выполняется. Когда на практике возникает необходимость использовать структуру, у которой тело цикла выполняется хотя бы один раз, то в этом случае применяется структура цикла, приведенная на рис. 2.
С помощью такой структуры обычно составляют алгоритмы итерационных вычислительных процессов, то есть процессов, в которых для определения последующих значений переменной используется ее предыдущее значение. Итерационный процесс положен, например, в основу метода последовательных приближений.
Выход из конструкции цикл-ДО осуществляется по достижении заданной точности или по какому-либо другому признаку.
Рис. 2. Структура цикл-ДО: а – развернутая схема цикла;
б – запись в псевдокодах; в – компактная схема цикла
Цикл с заданным числом повторений
Рассмотренные типы циклических структур имеют один недостаток: при ошибочном задании исходных данных может произойти зацикливание, т.е. возникает неприятная ситуация, когда происходит бесконечное повторение операторов, входящих в тело цикла. В этом случае приходится принудительно завершать работу программы, иногда это связано с потерей не сохраненных данных и самой программы.
В практических инженерных задачах обычно известны начальные значения изменяемых величин, закон изменения и конечное число повторений. Переменная, изменение которой организуется в ходе реализации цикла, называется параметром цикла, или управляющей переменной. Алгоритм работы цикла с заданным числом повторений (иногда его называют циклом с параметром) приведен на рис. 3.
|
|
 |
Рис. 3. Развернутая схема цикла с заданным числом повторений
Следует подчеркнуть, что цикл с заданным числом повторений представляет собой соединение линейной структуры (начало цикла), структуры цикл-ПОКА (условие в нем заменено на противоположное) и снова линейной (последовательной) структуры в теле цикла.
Прочитать этот алгоритм можно следующим образом: «Меняя параметр от начального значения до конечного значения, повторять тело цикла».
Алгоритм, приведенный на рис. 9, принято называть развернутой схемой цикла с заданным числом повторений. Такая схема является удобной для анализа алгоритма и поиска ошибок. Однако при написании алгоритма можно использовать и компактную запись. В псевдокодах она выглядит так:
Цикл по параметр от начальное значение
до конечное значение шаг приращение;
операторы тела цикла;
Конец-цикла.
Необходимо особо подчеркнуть, что развернутая и компактная записи после реализации в машине дают один и тот же результат. Компактная запись менее громоздкая за счет того, что в ней не задаются в явном виде связи между отдельными элементами структуры.
Для изображения компактной графической схемы цикла с параметром могут быть использованы символы “Подготовка” или “Граница цикла” (см. табл. 1), как показано на рис. 4.
|
|
 |
Рис. 4. Компактная запись цикла с параметром: а – с использованием символа “Подготовка”; б – с использованием символа “Граница цикла”
На рисунке обозначено: i – параметр цикла; iн – начальное значение параметра; iк – конечное значение параметра; Di – приращение (шаг). Если величина шага в цикле с параметром равна единице, то в заголовке цикла шаг можно не указывать.
В заключение приведем для сравнения развернутые графические схемы циклов с заданным числом повторений с возрастающим и убывающим параметром.
 |
Рис. 5. Развернутая схема цикла с заданным числом повторений:
а – с возрастающим параметром; б – с убывающим параметром
Схемы отличаются знаками в блоке проверяемого логического условия и в блоке изменения параметра цикла.
Пример 1. Определить значение переменной M, которое будет получено в результате выполнения фрагмента алгоритма:
........
M:=A;
Цикл по Т от А до В шаг С;
М:=М+1;
Конец-Цикла;
М:=М+В;
........
при условии, что переменные имеют следующие значения: А=1; В=5; С=1.
Данный фрагмент алгоритма содержит цикл с заданным числом повторений. Параметр Т изменяется от 1 до 5 с шагом 1. Сначала в таблицу состояния записывается содержимое ячеек памяти перед выполнением цикла: А=1; В=5; С=1; М=1 (табл. 1).
Таблица 1
Таблица значений
 |
В соответствии с развернутой схемой цикла с заданным числом повторений, параметру цикла присваивается начальное значение: Т=1. Затем проверяется условие: «Значение параметра больше конечного значения?»; в нашем случае: 1>5? Данное условие не выполняется, поэтому далее следуют операторы тела цикла. В рассматриваемом примере в теле цикла стоит один оператор присваивания: М:=М+1. В ячейку М записывается число 2. Затем к параметру добавляется шаг, и Т принимает значение, равное 2. После проверки условия 2 > 5 снова выполняется оператор, стоящий в теле цикла, происходит увеличение параметра на величину шага и, цикл повторяется в очередной раз. Последний раз тело цикла будет выполняться, когда параметр равен конечному значению, т.е. Т=5.
По окончании цикла: М=6, Т=6. Следующим за циклом стоит оператор присваивания М:=М+В, поэтому после выполнения всего фрагмента алгоритма М=11 (табл. 1).
Пример 2. Разработать алгоритм, обеспечивающий вычисление суммы элементов:
Данная задача может быть решена с помощью ЭВМ следующим образом. В памяти машины выделяется ячейка С, в которую первоначально записывается 0. Затем, используя цикл с заданным числом повторений, к содержимому ячейки С прибавляют значение очередного элемента ХI. Математическая модель решаемой задачи имеет вид:
Ввод: N – число элементов;
Х(I:N) – значения элементов.
Расчет:
Вывод: Х, С.
Схема алгоритма решения задачи приведена на рисунке.
 | |||
 |
Решение задач
ЗАДАЧА 1. Определить, что выводится на печать при выполнении фрагмента алгоритма:
г) Y:=0;
Цикл-ДО Y ³ 5;
Вывод(Y);
Y:=Y+1;
Конец-Цикла;
РЕШЕНИЕ
Составим таблицу значений:
| Память | Условие | Вывод |
ЗАДАЧА 2. Разработать алгоритм, обеспечивающий вычисление и печать значений функции Y=f(X) в точках X1, X2,…,XN:
