Циклические алгоритмические структуры.

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

· цикл с параметром (арифметический цикл или цикл со счетчиком);

· цикл с предусловием;

· цикл с постусловием.

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

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

Выделяют два типа циклов с условием: цикл с предусловием и цикл с постусловием.

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

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

Цикл с условием называют также итерационным циклом.

Для изображения циклов с предусловием и постусловием можно использовать символ «Граница цикла» (рис. 4):

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

На каждом шаге по внешнему циклу внутренний цикл выполняется несколько раз. Количество внутренних циклов на каждом внешнем цикле зависит от параметра внутреннего цикла.

Пусть, например, задано, что параметр внешнего цикла меняется от 1 до 5 с шагом 1, а параметр внутреннего цикла – от 1 до 10 с шагом 1.

Это означает, что на каждом шаге по внешнему циклу внутренний цикл будет выполняться 10 раз. Так как внешний цикл должен выполнится 5 раз, то внутренний цикл выполнится при этом 50 раз.

 

Основные операторы циклов и ветвления.

Если в программе возникает необходимость неоднократного выполнения некоторых операторов, то используются операторы повтора (цикла). В языке Паскаль различают три вида операторов цикла: while, repeat, for. Они используются для организации циклов различных типов. Выражение, управляющее повторениями, должно иметь булевский тип.

Если число повторений оператора (составного оператора) заранее неизвестно, а задано лишь условие его повторения (или окончания), используются операторы while, repeat. Оператор for используется, если число повторений заранее известно.

Оператор while

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

Форма записи:

While < условие продолжения повторений> do

<тело цикла>

Условие - булевское выражение, тело цикла - простой или составной оператор. Перед каждым выполнением тела цикла вычисляется значение выражения условия. Если результат равен True, тело цикла выполняется и снова вычисляется выражение условия. Если результат равен False, происходят выход из цикла и переход к первому после while оператору.

Оператор повтора repeat

Оператор повтора repeat аналогичен оператору while, но отличается от него, во-первых, тем, что условие проверяется после очередного выполнения операторов тела цикла (очередной итерации) и таким образом гарантируется хотя бы однократное выполнение цикла, а во-вторых, тем, что критерием прекращения цикла является равенство выражения константе True. За это цикл repeat часто называют циклом с постусловием, или циклом "ДО", так как он прекращает выполняться, как только значение выражения условия, записанного после слова until, равно True (истина).

Оператор повтора repeat состоит из заголовка repeat, тела и условия окончания until.

Формат записи:

Repeat

<оператор>

…

<оператор>

Until

<условие окончания цикла>

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

Оператор повтора for

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

Оператор повтора for состоит из заголовка и тела цикла.

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

Заголовок оператора повтора for определяет:

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

• направление изменения значения параметра цикла (возрастание -to или убывание - downto).

 

37. Типовые алгоритмы. (+ вопрос №34,35)

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

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

 

Процедуры и функции.

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

Procedure<имя_процедуры> (<список формальных параметров>);

Function<имя_функции> (<список формальных параметров>): <тип результата>;

 

Программирование графики.

 

Рекурсивные алгоритмы.

Рекурсия – это одна из фундаментальных концепций в математике и программировании. Это одна из форм мышления, это мощное средство, позволяющее строить элегантные и выразительные алгоритмы. Объект называется рекурсивным, если он содержит сам себя или определен с помощью самого себя.

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

 

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

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