4. Циклический алгоритм
В жизни, однако, часто встречаются инструкции, в которых требуется один и тот же набор действий выполнять много раз подряд: «Иди, пока не придешь», «Закручивай гайку, пока не завернешь до отказа» и так далее. Используя только ветвление, такие алгоритмы записать не удастся. Для этого нужна новая форма организации действий – цикл. Если какие-либо операторы необходимо выполнить несколько раз, то их не переписывают каждый раз заново, а организуют цикл.
Циклический алгоритм – это алгоритм, в котором некоторая последовательность действий повторяется несколько раз.
Алгоритм заточки карандашей 2. Алгоритм просмотра телевизора
5.Виды циклов
Цикл с предусловием (цикл пока)
Телом цикла называются команды, многократно повторяющиеся в процессе его выполнения. Перед выполнением цикла происходит присваивание начальных значений переменным, меняющимся в ходе его выполнения. Собственно выполнение цикла Пока начинается с проверки условия его окончания. Поэтому такую разновидность цикла называют еще циклом с предусловием. Переход к выполнению тела цикла, включающего в себя рабочий блок и изменение значений аргументов, осуществляется только в том случае, если условие выполняется. В противном случае происходит выход из цикла. В частности, может оказаться, что тело цикла не будет выполнено ни разу (если с самого начала условие не выполняется). С другой стороны, для того чтобы цикл не повторялся бесконечно, необходимо в теле цикла осуществлять действия, приводящие к ситуации, когда условие перестанет быть истинным. Этой цели и служит блок изменения значений аргументов.
2. Цикл с постусловием (цикл до)
Цикла с заранее неизвестным числом повторений. Здесь условие выполнения цикла проверяется в конце выполнения тела цикла, то есть в любом случае тело цикла будет выполнено хотя бы один раз. Цикл До называют циклом с постусловием потому что выполняется тело цикла а потом проверяется условие.
3. Арифметический цикл (цикл для) – цикл с параметром.
В том случае, когда количество повторений заранее известно, используется цикл Для. Здесь само условие выполнения цикла содержит информацию о том, сколько раз надо повторить его выполнение, например, в виде диапазона изменения цикловой переменной. Цикл для называют арифметическим циклом
Цикл с предусловием (цикл ПОКА)
Цикл с постусловием (цикл ДО)
Цикл с параметром (цикл ДЛЯ)
пока условие, повторять
до условие
для параметр
от начзнач до конзнач
шаг значение
Выполнение тела цикла повторяется, пока условие цикла истинно. Когда условие становится ложным, цикл заканчивает выполнение. Служебные слова нц и кц обозначают начало цикла и конец цикла соответственно.
Здесь используется условие окончания цикла. Когда оно становится истинным, цикл заканчивает работу.
Цикл выполняется последовательно от начального значения до конечного с указанным шагом.
Пример 1. Дана последовательность, общий член которой определяется формулой
Вычислить при n 2 сумму тех ее членов, которые больше заданного числа .
Решение: При решении задачи находится очередной член последовательно и, если он больше , добавляется к сумме.
Цикл (программирование)
Цикл — разновидность управляющей конструкции в высокоуровневых языках программирования, предназначенная для организации многократного исполнения набора инструкций. Также циклом может называться любая многократно исполняемая последовательность инструкций, организованная любым способом (например, с помощью условного перехода).
Содержание
Определения
Последовательность инструкций, предназначенная для многократного исполнения, называется телом цикла. Единичное выполнение тела цикла называется итерацией. Выражение определяющее, будет в очередной раз выполняться итерация, или цикл завершится, называется условием выхода или условием окончания цикла (либо условием продолжения в зависимости от того, как интерпретируется его истинность — как признак необходимости завершения или продолжения цикла). Переменная, хранящая текущий номер итерации, называется счётчиком итераций цикла или просто счётчиком цикла. Цикл не обязательно содержит счётчик, счётчик не обязан быть один — условие выхода из цикла может зависеть от нескольких изменяемых в цикле переменных, а может определяться внешними условиями (например, наступлением определённого времени), в последнем случае счётчик может вообще не понадобиться.
Исполнение любого цикла включает первоначальную инициализацию переменных цикла, проверку условия выхода, исполнение тела цикла и обновление переменной цикла на каждой итерации. Кроме того, большинство языков программирования предоставляют средства для досрочного управления циклом, например, операторы завершения цикла, то есть выхода из цикла независимо от истинности условия выхода (в языке Си — break ) и операторы пропуска итерации (в языке Си — continue ).
Виды циклов
Безусловные циклы
Иногда в программах используются циклы, выход из которых не предусмотрен логикой программы. Такие циклы называются безусловными, или бесконечными. Специальных синтаксических средств для создания бесконечных циклов, ввиду их нетипичности, языки программирования не предусматривают, поэтому такие циклы создаются с помощью конструкций, предназначенных для создания обычных (или условных) циклов. Для обеспечения бесконечного повторения проверка условия в таком цикле либо отсутствует (если позволяет синтаксис, как, например, в цикле LOOP…END LOOP языка Ада), либо заменяется константным значением (while true do … в Паскале). В языке С используется цикл for(;;) с незаполненными секциями.
Цикл с предусловием
Цикл с предусловием — цикл, который выполняется пока истинно некоторое условие, указанное перед его началом. Это условие проверяется до выполнения тела цикла, поэтому тело может быть не выполнено ни разу (если условие с самого начала ложно). В большинстве процедурных языков программирования реализуется оператором while, отсюда его второе название — while-цикл. На языке Pascal цикл с предусловием имеет следующий вид:
Цикл с постусловием
Цикл с постусловием — цикл, в котором условие проверяется после выполнения тела цикла. Отсюда следует, что тело всегда выполняется хотя бы один раз. В языке Паскаль этот цикл реализует оператор repeat..until; в Си — do…while.
На языке Pascal цикл с постусловием имеет следующий вид::
В трактовке условия цикла с постусловием в разных языках есть различия. В Паскале и языках, произошедших от него, условие такого цикла трактуется как условие выхода (цикл завершается, когда условие истинно, в русской терминологии такие циклы называют ещё «цикл до»), а в Си и его потомках — как условие продолжения (цикл завершается, когда условие ложно, такие циклы иногда называют «цикл пока»).
Цикл с выходом из середины
Цикл с выходом из середины — наиболее общая форма условного цикла. Синтаксически такой цикл оформляется с помощью трёх конструкций: начала цикла, конца цикла и команды выхода из цикла. Конструкция начала маркирует точку программы, в которой начинается тело цикла, конструкция конца — точку, где тело заканчивается. Внутри тела должна присутствовать команда выхода из цикла, при выполнении которой цикл заканчивается и управление передаётся на оператор, следующий за конструкцией конца цикла. Естественно, чтобы цикл выполнился более одного раза, команда выхода должна вызываться не безусловно, а только при выполнении условия выхода из цикла.
Принципиальным отличием такого вида цикла от рассмотренных выше является то, что часть тела цикла, расположенная после начала цикла и до команды выхода, выполняется всегда (даже если условие выхода из цикла истинно при первой итерации), а часть тела цикла, находящаяся после команды выхода, не выполняется при последней итерации.
Легко видеть, что с помощью цикла с выходом из середины можно легко смоделировать и цикл с предусловием (разместив команду выхода в начале тела цикла), и цикл с постусловием (разместив команду выхода в конце тела цикла).
Часть языков программирования содержат специальные конструкции для организации цикла с выходом из середины. Так, в языке Ада для этого используется конструкция LOOP…END LOOP и команда выхода EXIT или EXIT WHEN:
Здесь внутри цикла может быть любое количество команд выхода обоих типов. Сами команды выхода принципиально не различаются, обычно EXIT WHEN применяют, когда проверяется только условие выхода, а просто EXIT — когда выход из цикла производится в одном из вариантов сложного условного оператора.
В тех языках, где подобных конструкций не предусмотрено, цикл с выходом из середины может быть смоделирован с помощью любого условного цикла и оператора досрочного выхода из цикла (такого, как break в Си, exit в Турбо Паскале т. п.), либо оператора безусловного перехода goto.
Цикл со счётчиком
Цикл со счётчиком — цикл, в котором некоторая переменная изменяет своё значение от заданного начального значения до конечного значения с некоторым шагом, и для каждого значения этой переменной тело цикла выполняется один раз. В большинстве процедурных языков программирования реализуется оператором for, в котором указывается счётчик (так называемая «переменная цикла»), требуемое количество проходов (или граничное значение счётчика) и, возможно, шаг, с которым изменяется счётчик. Например, в языке Оберон-2 такой цикл имеет вид:
(здесь v — счётчик, b — начальное значение счётчика, e — граничное значение счётчика, s — шаг).
Неоднозначен вопрос о значении переменной по завершении цикла, в котором эта переменная использовалась как счётчик. Например, если в программе на языке Паскаль встретится конструкция вида:
возникает вопрос: какое значение будет в итоге присвоено переменной k: 9, 10, 100, может быть, какое-то другое? А если цикл завершится досрочно? Ответы зависят от того, увеличивается ли значение счётчика после последней итерации и не изменяет ли транслятор это значение дополнительно. Ещё один вопрос: что будет, если внутри цикла счётчику будет явно присвоено новое значение? Различные языки программирования решают данные вопросы по-разному. В некоторых поведение счётчика чётко регламентировано. В других, например, в том же Паскале, стандарт языка не определяет ни конечного значения счётчика, ни последствий его явного изменения в цикле, но не рекомендует изменять счётчик явно и использовать его по завершении цикла без повторной инициализации. Программа на Паскале, игнорирующая эту рекомендацию, может давать разные результаты при выполнении на разных системах и использовании разных трансляторов.
Радикально решён вопрос в языке Ада: счётчик считается описанным в заголовке цикла, и вне его просто не существует. Даже если имя счётчика в программе уже используется, внутри цикла в качестве счётчика используется отдельная переменная. Счётчику запрещено явно присваивать какие бы то ни было значения, он может меняться только внутренним механизмом оператора цикла. В результате конструкция
внешне аналогичная вышеприведённому циклу на Паскале, трактуется однозначно: переменной k будет присвоено значение 100, поскольку переменная i, используемая вне данного цикла, не имеет никакого отношения к счётчику i, который создаётся и изменяется внутри цикла. Подобное обособление счётчика удобно и безопасно: не требуется отдельное описание для него и минимальна вероятность случайных ошибок, связанных со случайным разрушением внешних по отношению к циклу переменных. Если программисту требуется включить в готовый код цикл со счётчиком, то он может не проверять, существует ли переменная с именем, которое он выбрал в качестве счётчика, не добавлять описание нового счётчика в заголовок соответствующей процедуры, не пытаться использовать один из имеющихся, но в данный момент «свободных» счётчиков. Он просто пишет цикл с переменной-счётчиком, имя которой ему удобно, и может быть уверен, что никакой коллизии имён не произойдёт.
Цикл со счётчиком всегда можно записать как условный цикл, перед началом которого счётчику присваивается начальное значение, а условием выхода является достижение счётчиком конечного значения; к телу цикла при этом добавляется оператор изменения счётчика на заданный шаг. Однако специальные операторы цикла со счётчиком могут эффективнее транслироваться, так как формализованный вид такого цикла позволяет использовать специальные процессорные команды организации циклов.
В некоторых языках, например, Си и других, произошедших от него, цикл for, несмотря на синтаксическую форму цикла со счётчиком, в действительности является циклом с предусловием. То есть в Си конструкция цикла:
фактически представляет собой другую форму записи конструкции [1] :
То есть в конструкции for сначала пишется произвольное предложение инициализации цикла, затем — условие продолжения и, наконец, выполняемая после каждого тела цикла некоторая операция (это не обязательно должно быть изменение счётчика; это может быть правка указателя или какая-нибудь совершенно посторонняя операция). Для языков такого вида вышеописанная проблема решается очень просто: переменная-счётчик ведёт себя совершенно предсказуемо и по завершении цикла сохраняет своё последнее значение.
Совместный цикл
Ещё одним вариантом цикла является цикл, задающий выполнение некоторой операции для объектов из заданного множества, без явного указания порядка перечисления этих объектов. Такие циклы называются совместными (а также циклами по коллекции, циклами просмотра) и представляют собой формальную запись инструкции вида: «Выполнить операцию X для всех элементов, входящих во множество M». Совместный цикл, теоретически, никак не определяет, в каком порядке операция будет применяться к элементам множества, хотя конкретные языки программирования, разумеется, могут задавать конкретный порядок перебора элементов. Произвольность даёт возможность оптимизации исполнения цикла за счёт организации доступа не в заданном программистом, а в наиболее выгодном порядке. При наличии возможности параллельного выполнения нескольких операций возможно даже распараллеливание выполнения совместного цикла, когда одна и та же операция одновременно выполняется на разных вычислительных модулях для разных объектов, при том что логически программа остаётся последовательной.
Совместные циклы имеются в некоторых языках программирования (C#, Eiffel, Java, JavaScript, Perl, Python, PHP, LISP, Tcl и др.) — они позволяют выполнять цикл по всем элементам заданной коллекции объектов. В определении такого цикла требуется указать только коллекцию объектов и переменную, которой в теле цикла будет присвоено значение обрабатываемого в данный момент объекта (или ссылка на него). В различных языках программирования синтаксис оператора различен:
Perl (строгий порядок «от первого до последнего»):
Досрочный выход и пропуск итерации
Многие языки программирования, имеющие в своём синтаксисе циклические конструкции, имеют также специфические команды, позволяющие нарушить порядок работы этих конструкций: команду досрочного выхода из цикла и команду пропуска итерации.
Досрочный выход из цикла
Команда досрочного выхода применяется, когда необходимо прервать выполнение цикла, в котором условие выхода ещё не достигнуто. Такое бывает, например, когда при выполнении тела цикла обнаруживается ошибка, после которой дальнейшая работа цикла не имеет смысла.
Команда досрочного выхода обычно называется EXIT или break , а её действие аналогично действию команды безусловного перехода ( goto ) на команду, непосредственно следующую за циклом, внутри которого эта команда находится. Так, в языке Си два нижеприведённых цикла работают совершенно одинаково:
В обоих случаях, если в теле цикла выполнится условие <ошибка>, будет произведён переход на операторы, обозначенные как «продолжение программы». Таким образом, оператор досрочного выхода из цикла, по сути, просто маскирует безусловный переход, однако использование break предпочтительнее, чем goto, поскольку поведение break чётко задано языком, потенциально менее опасно (нет, например, вероятности ошибиться с положением или названием метки). Кроме того, явный досрочный выход из цикла не нарушает принципов структурного программирования.
Обычный оператор досрочного выхода прерывает работу того цикла, в котором он непосредственно находится. В ряде языков программирования функциональность этого оператора расширена, он позволяет выходить из нескольких вложенных циклов (см. ниже). В таких случаях цикл, из которого требуется выйти, помечается меткой, а в операторе досрочного выхода указывается эта метка.
Пропуск итерации
Данный оператор применяется, когда в текущей итерации цикла необходимо пропустить все команды до конца тела цикла. При этом сам цикл прерываться не должен, условия продолжения или выхода должны вычисляться обычным образом.
В языке Си и его языках-потомках в качестве команды пропуска итерации используется оператор continue в конструкции цикла. Действие этого оператора аналогично безусловному переходу на строку внутри тела цикла, следующую за последней его командой. Например, код на Си, находящий сумму элементов массива и сумму всех положительных элементов массива, может иметь следующий вид:
Из второго фрагмента ясно видно, как работает continue : он просто передаёт управление за последнюю команду тела цикла, пропуская выполнение команды суммирования, если очередной элемент массива не удовлетворяет условию. Таким образом, в sum_pos накапливается сумма лишь положительных элементов массива.
Необходимость
С точки зрения структурного программирования команды досрочного выхода из цикла и продолжения итерации являются избыточными, поскольку их действие может быть легко смоделировано чисто структурными средствами. Более того, по мнению ряда теоретиков программирования (в частности, Эдсгера Дейкстры), сам факт использования в программе неструктурных средств, будь то классический безусловный переход или любая из его специализированных форм, таких как break или continue, является свидетельством недостаточно проработанного алгоритма решения задачи.
Однако на практике код программы часто является записью уже имеющегося, ранее сформулированного алгоритма, перерабатывать который нецелесообразно по чисто техническим причинам. Попытка заменить в таком коде команду досрочного выхода на структурные конструкции часто оказывается неэффективной или громоздкой. Например, вышеприведённый фрагмент кода с командой break может быть записан так:
Легко убедиться, что фрагмент будет работать аналогично предшествующим, разница лишь в том, что в месте проверки на ошибку вместо непосредственного выхода из цикла устанавливается флаг досрочного выхода, который проверяется позже в штатном условии продолжения цикла. Однако для отказа от команды досрочного выхода пришлось добавить в программу описание флага и вторую ветвь условного оператора, к тому же произошло «размытие» логики программы (решение о досрочном выходе принимается в одном месте, а выполняется в другом). В результате программа не стала ни проще, ни короче, ни понятнее.
Несколько иначе обстоит дело с командой пропуска итерации. Она, как правило, очень легко и естественно заменяется на условный оператор. Например, приведённый выше фрагмент суммирования массива можно записать так:
Как видим, достаточно было заменить проверяемое условие на противоположное и поместить заключительную часть тела цикла в условный оператор. Можно заметить, что программа стала короче (за счёт удаления команды пропуска итерации) и одновременно логичнее (из кода непосредственно видно, что суммируются положительные элементы).
Кроме того, использование команды пропуска итерации в цикле с условием (while-цикле) может также спровоцировать неочевидную ошибку: если тело цикла, как это часто бывает, завершается командами изменения переменной (переменных) цикла, то команда пропуска итерации пропустит и эти команды тоже, в результате чего (в зависимости от условия, по которому происходит пропуск) может произойти зацикливание или не соответствующий алгоритму повтор итерации. Так, если заменить в вышеприведённом примере цикл for на while, получится следующее:
Несмотря на свою ограниченную полезность и возможность замены на другие языковые конструкции, команды пропуска итерации и, особенно, досрочного выхода из цикла в отдельных случаях оказываются крайне полезны, именно поэтому они сохраняются в современных языках программирования.
Вложенные циклы
Существует возможность организовать цикл внутри тела другого цикла. Такой цикл будет называться вложенным циклом. Вложенный цикл по отношению к циклу в тело которого он вложен будет именоваться внутренним циклом, и наоборот цикл в теле которого существует вложенный цикл будет именоваться внешним по отношению к вложенному. Внутри вложенного цикла в свою очередь может быть вложен еще один цикл, образуя следующий уровень вложенности и так далее. Количество уровней вложенности, как правило, не ограничивается.
Полное число исполнений тела внутреннего цикла не превышает произведения числа итераций внутреннего и всех внешних циклов. Например взяв три вложенных друг в друга цикла, каждый по 10 итераций, получим 10 исполнений тела для внешнего цикла, 100 для цикла второго уровня и 1000 в самом внутреннем цикле.
Одна из проблем, связанных с вложенными циклами — организация досрочного выхода из них. Во многих языках программирования есть оператор досрочного завершения цикла (break в Си, exit в Турбо Паскале, last в Perl и т. п.), но он, как правило, обеспечивает выход только из цикла того уровня, откуда вызван. Вызов его из вложенного цикла приведёт к завершению только этого внутреннего цикла, внешний же цикл продолжит выполняться. Проблема может показаться надуманной, но она действительно иногда возникает при программировании сложной обработки данных, когда алгоритм требует немедленного прерывания в определённых условиях, наличие которых можно проверить только в глубоко вложенном цикле.
Решений проблемы выхода из вложенных циклов несколько.
- Простейший — использовать оператор безусловного перехода goto для выхода в точку программы, непосредственно следующую за вложенным циклом. Этот вариант критикуется сторонниками структурного программирования, как и все конструкции, требующие использования goto. Некоторые языки программирования, например, Модула-2, просто, не имеют оператора безусловного перехода, и в них подобная конструкция невозможна.
- Альтернатива — использовать штатные средства завершения циклов, в случае необходимости устанавливая специальные флаги, требующие немедленного завершения обработки. Недостаток — усложнение кода, снижение производительности.
- Размещение вложенного цикла в процедуре. Идея состоит в том, чтобы всё действие, которое может потребоваться прервать досрочно, оформить в виде отдельной процедуры, и для досрочного завершения использовать оператор выхода из процедуры (если такой есть в языке программирования). В языке Си, например, можно построить функцию с вложенным циклом, а выход из неё организовать с помощью оператора return. Недостаток — выделение фрагмента кода в процедуру не всегда логически обосновано, и не все языки имеют штатные средства досрочного завершения процедур.
- Воспользоваться механизмом генерации и обработки исключений (исключительных ситуаций), который имеется сейчас в большинстве языках высокого уровня. В этом случае в нештатной ситуации код во вложенном цикле возбуждает исключение, а блок обработки исключений, в который помещён весь вложенный цикл, перехватывает и обрабатывает его. Недостаток — реализация механизма обработки исключений в большинстве случаев такова, что скорость работы программы уменьшается. Правда, в современных условиях это не особенно важно: практически потеря производительности столь мала, что имеет значение лишь для очень немногих приложений.
- Наконец, существуют специальные языковые средства для выхода из вложенных циклов. Так, в языке Ада программист может пометить цикл (верхний уровень вложенного цикла) меткой, и в команде досрочного завершения цикла указать эту метку. Выход произойдёт не из текущего цикла, а из всех вложенных циклов до помеченного, включительно [2] . Язык PHP предоставляет возможность указать число прерываемых циклов после команды break — так break 2 прервёт сам цикл и вышестоящий над ним, а break 1 эквивалентно простой записи команды break [3] .
Циклы с несколькими охраняемыми ветвями
Цикл Дейкстры
В теории программирования известна ещё одна, принципиально отличающаяся от «классических», форма циклической конструкции, получившая название «цикл Дейкстры», по имени Эдсгера Дейкстры, впервые её описавшего. В классическом дейкстровском описании такой цикл выглядит следующим образом:
Здесь do — маркер начала конструкции цикла, od — маркер завершения конструкции цикла, Pi — i-тое охраняющее условие (логическое выражение, которое может иметь значение «истинно» или «ложно»), Si — i-я охраняемая команда. Цикл состоит из одной или нескольких ветвей (охраняемых выражений), каждая из которых представляет собой пару из охраняющего условия (или, коротко, «охраны») и охраняемой команды (понятно, что в реальности команда может быть сложной).
При выполнении цикла Дейкстры в каждой итерации происходит вычисление охраняемых условий. Если хотя бы одно из них истинно, выполняется соответствующая охраняемая команда, после чего начинается новая итерация (если истинны несколько охраняемых условий, выполняется только одна охраняемая команда). Если все охраняемые условия ложны, цикл завершается. Нетрудно заметить, что цикл Дейкстры с одним охраняющим условием и одной охраняемой командой представляет собой, по сути, обычный цикл с предусловием (цикл «пока»).
Хотя цикл Дейкстры был изобретён ещё в 1970-х годах, специальных конструкций для его создания в языках программирования не содержится. Единственным исключением стал недавно созданный Оберон-07 — первый реальный язык программирования, явно поддерживающий цикл с несколькими охраняемыми ветвями. Впрочем, цикл Дейкстры может быть без больших затруднений смоделирован с помощью традиционных конструкций структурных языков программирования. Вот пример его реализации одним из возможных способов на языке Ада:
Здесь P1-Pn — охраняющие условия, а S1-Sn — соответствующие охраняемые команды.
Цикл Дейкстры удобен при реализации некоторых специфических повторяющихся вычислений, которые неудобно описывать с помощью более традиционных циклических конструкций. Например, этим циклом естественно представляется конечный автомат — каждая ветвь соответствует одному состоянию автомата, охраняемые условия строятся так, чтобы в текущей итерации выбиралась ветвь, соответствующая текущему состоянию автомата, а код охраняемой команды обеспечивает выполнение вычислений в текущем состоянии и переход в следующее (то есть такое изменение переменных, после которого на следующей итерации будет истинным охраняющее условие нужной ветви).
Цикл «паук»
Легко видеть, что цикл Дейкстры не содержит явного условия продолжения или выхода, что не всеми теоретиками программирования рассматривается как благо. Поэтому была предложена усложнённая конструкция цикла Дейкстры, получившая название «цикл-‘паук’». В той же нотации она выглядит следующим образом:
Здесь после маркера out добавлены ветви завершения, состоящие из условий выхода Qi и команд завершения Ti. Кроме того, добавлена ветвь альтернативного завершения else с командой E.
Цикл-‘паук’ выполняется так:
- Вычисляются охраняющие условия. Если существует истинное охраняющее условие, выполняется соответствующая охраняемая команда.
- Вычисляются условия выхода. Если существует истинное условие выхода, выполняется соответствующая команда завершения, после чего выполнение цикла заканчивается. Если все условия выхода ложны, начинается следующая итерация, но только в том случае, если в текущей итерации было истинным хотя бы одно из охраняющих условий.
- Если в данной итерации оказались ложными и все охраняющие условия, и все условия выхода, выполняется команда альтернативного завершения E, после чего выполнение цикла прерывается.
Структура цикла-‘паука’ позволяет предельно строго описать условия выполнения цикла. Согласно теоретическим положениям, ветвь альтернативного завершения не должна использоваться в качестве одного из вариантов корректного прекращения работы цикла (все такие варианты должны быть оформлены в виде соответствующих ветвей завершения с явным условием), она служит только для того, чтобы отследить ситуацию, когда по каким-то причинам цикл начал выполняться нештатно. То есть команда альтернативного завершения может лишь анализировать причины ошибки и представлять результаты анализа.
Хотя явной поддержки на уровне синтаксиса для этого цикла не существует ни в одном языке программирования, цикл-‘паук’, как и цикл Дейкстры, может быть смоделирован с помощью традиционных структурных конструкций.
Программирование. Циклы Pascal-Паскаль
При решении подавляющего большинства задач (в том числе и весьма несложных) в программе практически невозможно задать в явном виде все операции, которые необходимо выполнить. В самом деле, пусть необходимо вычислить сумму первых n членов гармонического ряда:
Очевидно, что с использованием только рассмотренных выше типов операторов можно составить программу лишь для фиксированного значения n. Например, при n=5 требуемые вычисления можно задать с помощью оператора присваивания вида:
Если же значение n не фиксируется, а является исходным данным, вводимым в процессе выполнения программы (и даже константой, описанной в программе), то аналогичный оператор присваивания записать невозможно. Ибо запись вида Y:= 1+1/2+1/3+…+1/ n в языках программирования недопустима.
Для устранения возникающих трудностей служат операторы цикла. Они позволяют повторять выполнение отдельных частей программы. Можно выделить четыре ператора цикла, присутствующих в том или ином виде во всех языках программирования: простой арифметический оператор цикла (цикл с параметром с шагом 1), сложный арифметический оператор цикла (цикл с параметром произвольного шага), итерационный оператор цикла с предусловием, итерационный оператор цикла с постусловием.
Простой арифметический оператор цикла Паскаля (цикл с параметром)
Вернемся к рассмотренной выше задаче вычисления суммы первых n членов гармонического ряда, правила которой невозможно задать в виде арифметического выражения, если значение n заранее не фиксировано.
На самом деле вычисление этой суммы можно осуществить по очень простому и компактному алгоритму: предварительно положим y=0 (с помощью оператора присваивания y:=0), а затем выполним оператор присваивания y:= y+1/ i для последовательных значений i= 1,2,…, n. При каждом очередном выполнении этого оператора к текущему значению y будет прибавляться очередное слагаемое. Как видно, в этом случае процесс вычислений будет носить циклический характер: оператор y:= y+1/i должен выполняться многократно, т.е. циклически, при различных значениях i.
Этот пример циклического вычислительного процесса является весьма типичным; его характерные особенности состоят в том, что
- число повторений цикла известно к началу его выполнения (в данном случае оно равно значению n, которое предполагается заданным к этому времени);
- управление циклом осуществляется с помощью переменной порядкового типа, которая в этом циклическом процессе принимает последовательные значения от заданного начального до заданного конечного значений (в нашем случае – это целочисленная переменная i, принимающая последовательные значения от 1 до n).
Для компактного задания подобного рода вычислительных процессов и служит оператор цикла с параметром. Чаще всего используется следующий вид этого оператора В Паскале:
где for (для), to (увеличиваясь к) и do (выполнять, делать) – служебные слова, V – переменная порядкового типа, называемая параметром цикла, Е1 и Е2 – выражения того же типа, что и параметр цикла, S – оператор, который и выполняется многократно в цикле, называемый телом цикла.
Заметим, что в Паскале после do должен стоять один оператор, если необходимо выполнить несколько действий, то они должны быть объединены в один составной оператор путем заключения в операторные скобки.
Этот оператор цикла Паскаля предусматривает присваивание параметру цикла V последовательных значений от начального значения, равного значению выражения Е1, до конечного значения, равного значению выражения Е2, т.е. при каждом повторении выполняется оператор присваивания V:= succ( V), и выполнение оператора S при каждом значении параметра цикла V. При этом значения выражений Е1 и Е2 вычисляются один раз, при входе в оператор цикла, а значение параметра цикла V не должно изменяться в результате выполнения оператора S. Если заданное конечное значение меньше начального значения (что допустимо), то оператор S не выполняется ни разу.
В Паскале считается, что при нормальном завершении выполнения оператора цикла значение параметра цикла не определено.
С использованием оператора цикла с параметром алгоритм вычисления суммы первых n членов гармонического ряда может быть задан следующим образом:
Пример кода программы для суммирования первых n членов гармонического ряда
В некоторых случаях бывает удобно, чтобы параметр цикла Паскаля принимал последовательные, но не возрастающие, а убывающие значения. Для таких случаев в Паскале предусмотрен оператор цикла с параметром следующего вида:
где downto (уменьшаясь к) – служебное слово, а все остальные слова и выражения имеют прежний смысл. Изменение параметра цикла от большего значения к меньшему происходит при выполнении присваивания V:=pred( V). Заметим, что начальное значение может быть меньше конечного значения. В этом случае оператор S не выполнится ни разу. Значение параметра цикла по завершении выполнения такого цикла так же считается неопределенным.
Следует запомнить и то, что для обоих вариантов записи цикла с параметром справедливо: если начальное и конечное значения равны, то тело цикла (оператор S) выполнится один раз.
Заметим так же, что параметр цикла может и не использоваться в теле цикла, так что основное его назначение – это управление числом повторений цикла. Например, значение y= x n, где n>=0 – целое, можно вычислить по следующему алгоритму: предварительно положить y=1, а затем n раз домножить это значение на x:
Пример кода программы цикла Паскаля
Как видно, здесь параметр цикла i служит лишь для того, чтобы тело цикла (оператор y:= y* x) выполнилось нужное число раз.
Арифметический оператор цикла Паскаля с произвольным шагом
Естественным усложнением простого арифметического цикла Паскаля, является цикл, в котором параметр цикла изменяется не на 1, а на произвольную величину – шаг приращения. При этом в процессе выполнения цикла шаг изменяется по заданному закону. Стандартные операторы для реализации такого цикла есть в Форте, в других языках их приходится организовывать из простейшего арифметического цикла.
Итерационные операторы цикла Паскаля
Итерационные циклы отличаются от циклов с параметром тем, что в них заранее неизвестно число повторений.
Пусть мы отправляемся за грибами и возвращаемся домой, когда корзина наполнится. Все грибники делятся на 2 категории:
- Смотрят, есть ли место в корзине, а уже потом срывают грибы, если их можно поместить в корзину. (Правда, в жизни таких грибников встречать не приходилось)
- Сначала срывают грибы, а уже потом думают, как их положить в корзину.
Отсюда получаются два варианта реализации итерационных циклов:
с предусловием и с постусловием.
В цикле с предусловием сначала проверяется условие, а потом делается шаг. Грибник придет с полной или почти полной корзиной. В цикле с постусловием – сначала шаг, а потом проверка. Как всякий нормальный грибник, этот принесет полную или слегка переполненную корзину.
Какой алгоритм выбрать? Это зависит от конкретной задачи.
Если, сделав шаг без проверки, можно свалиться в яму, то лучше проверка вначале (как слепой с палочкой). Ну, а если шаг без проверки вас не пугает, то можно отложить ее до завершения шага.
Нужно также проанализировать событие, которого мы ожидаем. Если оно может случиться до первого шага, то нужен цикл с предусловием. А если событие не может случиться до первого шага, то нужен цикл с постусловием.
Оператор цикла Паскаля с постусловием
Рассмотрим теперь математическую задачу. Пусть нам необходимо вычислить сумму первых членов гармонического ряда, удовлетворяющих условию 1/i>= e, где 0< e<1, а i=1,2,3…. Эту задачу можно решить по следующему алгоритму: положить предварительно y=0 и i=0, а затем в цикле увеличивать i на 1, к значению y добавлять очередное слагаемое 1/ i до тех пор, пока текущее значение 1/ i впервые окажется больше заданного значения 0< e<1.
Очевидно, что число повторений этого цикла заранее не известно. В подобного рода случаях мы можем лишь сформулировать условие, при выполнении которого процесс добавления к сумме очередного слагаемого должен завершиться.
Для задания таких вычислительных процессов и служит оператор цикла Паскаля с постусловием. Этот оператор имеет вид:
где repeat (повторять) и until (до) – служебные слова, через Si обозначен любой оператор Паскаля, а через В – логическое выражение.
При выполнении этого оператора цикла последовательность операторов, находящихся между словами repeat и until, выполнится один или более раз. Этот процесс завершается, когда после очередного выполнения заданной последовательности операторов логическое выражение В примет (впервые) значение true. Таким образом, с помощью логического выражения В задается условие завершения выполнения оператора цикла. Поскольку в данном случае проверка условия производится после выполнения последовательности операторов (тела цикла), этот оператор цикла и называется оператором цикла с постусловием.
С использованием этого вида оператора цикла Паскаля задача о суммировании первых членов гармонического ряда, удовлетворяющих заданному условию, может быть реализована следующим образом:
Пример кода оператора цикла Паскаля с постусловием
Заметим, что оператор цикла с постусловием является более общим, чем оператор цикла с параметром — любой циклический процесс, задаваемый с помощью цикла с параметром можно представить в виде цикла с постусловием. Обратное утверждение неверно. Например, задача о суммировании первых n членов гармонического ряда, рассмотренная ранее, с оператором цикла с постусловием будет выглядеть так:
Пример кода оператора цикла Паскаля с постусловием
Оператор цикла Паскаля с предусловием
В случае оператора цикла Паскаля с постусловием входящая в него последовательность операторов заведомо будет выполняться хотя бы один раз. Между тем довольно часто встречаются такие циклические процессы, когда число повторений цикла тоже неизвестно заранее, но при некоторых значениях исходных данных предусмотренные в цикле действия вообще не должны выполняться, и даже однократное выполнение этих действий может привести к неверным или неопределенным результатам.
Пусть, например, дано вещественное число М. Требуется найти наименьшее целое неотрицательное число k, при котором 3 k> M. Эту задачу можно решить по следующему алгоритму: предварительно положить y=1 и k=0; затем в цикле домножать значение y на 3 и увеличивать значение k на 1 до тех пор, пока текущее значение y впервые окажется больше значения М. На первый взгляд, здесь можно воспользоваться оператором цикла с постусловием:
Пример кода оператора цикла Паскаля с постусловием
Однако нетрудно убедиться в том, что при M<1 будет получен неправильный результат k=1, тогда как должно быть получено k=0: в этом случае предварительно сформированное значение k=0 является окончательным результатом и действия, предусмотренные в цикле, выполняться не должны.
Для задания подобного рода вычислительных процессов, когда число повторений цикла заранее неизвестно и действия, предусмотренные в цикле, могут вообще не выполняться, и служит оператор цикла с предусловием. Этот оператор цикла имеет в Паскале следующий вид:
где while (пока), do (делать, выполнять) – служебные слова, В – логическое выражение, S – оператор. Здесь оператор S выполняется ноль или более раз, но перед каждым очередным его выполнением вычисляется значение выражения В, и оператор S выполняется только в том случае, когда значение выражения В true. Выполнение оператора цикла завершается, когда выражение В впервые принимает значение false. Если это значение выражение В принимает при первом же его вычислении, то оператор S не выполнится ни разу.
В рассматриваемой нами задаче правильное значение k при любом значении М может быть получено следующим образом:
Пример кода оператора цикла Паскаля с предусловием
Исходники Pascal (127)
Справочник
Справочник по паскалю: директивы, функции, процедуры, операторы и модули по алфавиту
Различные варианты программирования циклического алгоритма
В жизни людей очень часто встречаются циклы. Будь то жизнь маленького ребёнка или взрослого человека, а то и пожилых людей. Эти циклы можно расписать как выполнение одних и тех же действий, пока выполняется определённое условие. К примеру, взрослый человек находится на работе до момента, когда наступит время его ухода. И так изо дня в день, однако, есть и исключения в виде выходных. В жизни детей можно привести такой пример, как обязанность каждый день ходить в школу до момента, когда наступят выходные или каникулы.
Циклические алгоритмы – это алгоритмы, в которых некоторая часть операций повторяется многократно.
Цикл – конструкция с оператором, который повторяется определённое или неопределённое заранее количество раз. Действия, выполняющиеся последовательно внутри цикла, называют телом цикла.
В разных средах программирования циклические конструкции могут быть реализованы по-разному, но неизменным остается главный признак, отличающий циклы от линейных операций и ветвлений – возможность перемещения по программе не только «сверху-вниз», но и «снизу-вверх», для возврата к уже выполненным ранее действиям.
Циклы разделяют на три типа в зависимости от метода организации повторений:
- Цикл, в котором задано условие окончания работы;
- Когда известно условие продолжения работы цикла;
- Когда известно число повторений цикла.
Программирование циклического алгоритма
Выбрав среду программирования Паскаль необходимо познакомиться с операторами, с помощью которых можно разработать программу с циклом. Ими являются while, repeat, for. Оператор while был разобран ещё на прошлом уроке, однако забывать о нём нельзя.
Цикл с предусловием
Цикл с предусловием реализует циклический алгоритм, записанный на языке программирования, с использованием определённого условия, истинность которого проверяется перед каждой итерацией цикла. Выполнение цикла прекращается, когда условие становится ложным.
Цикл с постусловием
Цикл с постусловием – это алгоритм циклической структуры, в котором проверка условия продолжения осуществляется после выполнения тела цикла.
Тело цикла с постусловием всегда выполняется как минимум один раз, независимо от истинности или ложности условия. Это его ключевое отличие от цикла с предусловием.
Такие циклы удобны, когда в условии используется результат выполнения тела цикла. Например, если мы хотим найти в тексте слово «стоп», мы должны сначала прочитать очередное слово, и только потом проверить, является ли оно искомым или следует продолжить поиск.
Цикл с заданным числом повторений
Этот вид цикла вместо логического условия выполнения использует параметр (счетчик) – специальную переменную, которая на каждом шаге цикла получает очередное значение из определенного диапазона. Цикл повторяется до тех пор, пока не будут перебраны все элементы диапазона. Таким образом, определяя диапазон, мы определяем заранее заданное число повторений.
Операторы цикла
Для программирования циклических алгоритмов и корректного выполнения программ с их использованием, необходимо знать операторы цикла. Чаще всего, в языке Паскаль используют операторы цикла: for, repeat и while. Разберем их подробнее.
Оператор while
Оператор while используется, когда нужно создать цикл с предусловием. Его схема в циклическом алгоритме выглядит следующим образом:
Если переводить его дословно, то можно сказать, что он работает по принципу «пока <условие> выполнять действие <оператор 1>», а заканчивается при переходе программы на слово end. Перед выполнением операторов внутри цикла условие обязательно проверяется и уже дальше, в зависимости от его истинности, программа либо выполняет тело цикла, либо переходит к последующим операторам.
Решение задач с использованием оператора while
Для более чёткого понимания решения задач нужно разобрать циклические алгоритмы, примеры которых приведены в решениях.
Задача 1. На вход подаются целые числа. До тех пор, пока не будет введено число, которое больше 17, программа должна вывести сумму полученного числа и числа 8. Когда вводимое число будет больше 17, то после выполнения программы цикл завершается.
Шаг 1. Для начала необходимо дать программе название.
Шаг 2. Учитывая, что на вход подаётся целое число, указать тип данных, в данном случае – integer.
Шаг 3. Запись командного блока. Нужно написать слово, обозначающее начало, begin.
Шаг 4. Нужно дать переменной a значение 1, чтобы цикл начался автоматически.
Шаг 5. Запись цикла. Поскольку известно условие окончания работы, для этой задачи необходимо написать «пока a меньше или равно 17» и сделать переход к последующим операторам путём написания составного цикла.
Шаг 6. Первоначальный вывод программы. Необходимо написать то, что программа будет выдавать в первую очередь. В данном случае, она будет запрашивать целое число, запрос так и пишется: «Введите целое число: » .
Шаг 7. Запись необходимых операторов. Используя оператор readln программа считывает данные и переводит курсор на новую строку. Далее она производит операции над поступившими данными.
Шаг 8. Запись суммы. Исходя из условия задачи необходимо сделать так, чтобы программа выводила сумму входящего числа и числа 8. Осуществить это можно используя оператор writeln.
Шаг 9. Запись вывода программы после цикла. После того, как программа выполнит свою работу в цикле, необходимо показать, что она из него вышла. Можно просто попрощаться, как в данном случае.
Шаг 10. Проверка правильности записи алгоритма. В конце программного блока, после слова end нельзя забывать точку, её обязательно нужно поставить.
Оператор repeat
Оператор цикла repeat until используется для создания циклического алгоритма с постусловием. Его схема выглядит так:
Дословно оператор Паскаля repeat можно перевести как «повторяй <оператор 1>, до <условие>». В зависимости от истинности условия, либо происходит переход на повторение «оператора 1», либо осуществляется выход из цикла к последующим операторам.
Оператор repeat имеет два важных отличия от оператора while:
- в операторе repeat сначала выполняется тело, а затем проверяется условие;
- в операторе repeat прописывается условие завершения цикла, тогда как в операторе while – условие его продолжения.
Решение задач с использованием оператора repeat
Задача 1. Придумать алгоритм и написать по нему программу, результатом выполнения которой будет вывод последовательности натуральных чисел от 1 до введенного пользователем числа.
Шаг 1. Название программы. В данном случае — «задача 1».
Шаг 2. Учитывая, что на вход подаются целые числа, требуется указать тип данных – integer.
Шаг 3. Командный блок. Запись начального слова begin.
Шаг 4. Вывод запроса программы. Поскольку программе необходимо целое число, нужно попросить пользователя ввести его. Осуществляется это с помощью процедуры writeln и текста «Введите целое число, которое больше 1: ».
Шаг 5. Необходимо присвоить переменной i значение 1 для того, чтобы последовательность начиналась с натурального числа.
Шаг 6. Запись цикла. Учитывая, что используется цикл с постусловием, необходимо сначала записать оператор, который будет повторяться, затем увеличить i на 1, чтобы образовывалась последовательность, и уже после этого прописать условие повторения. В данной задаче цикл перестаёт повторяться тогда, когда переменная i принимает значение больше введённого числа, которое является последним членом последовательности.
Шаг 7. Проверка программы на правильность в выводе. В результате своей работы программа должна вывести последовательность натуральных чисел от 1 до n, через пробел.
Оператор for
Используя оператор for можно задать нужное количество повторений одних и тех же действий. По-другому его называют оператором циклов с известным числом повторений. Он имеет два соединительных слова – это to и downto. Различие между ними в том, что при использовании первого к предыдущему значению переменной цикла прибавляется единица, а при написании второго – вычитается единица. Схемы оператора имеют следующий вид:
Дословно его можно перевести как «для переменной в значении от начального к конечному выполнять <оператор 1> ».
Решение задач с использованием оператора for
Рассмотреть пример с оператором for можно при написании короткого алгоритма для следующей задачи.
Задача 1. Напишите на одном из языков программирование алгоритм, который выводит квадраты чисел от 1 до 10.
Шаг 1. Необходимо дать программе название.
Шаг 2. Поскольку на вход числа не подаются, тип указывается в зависимости от данных, которые изначально находятся в программе. В данном случае – это целые числа.
Шаг 3. Запись блока с командами алгоритма.
Шаг 4. Перебор последовательности чисел осуществляется в цикле for, в котором счетчик i пробегает значения от 1 до 10, а расчет и вывод квадратов осуществляется в процедуре write.
Решение задач с использованием операторов while, repeat, for
Задача 1 Разработать алгоритм программы, которая выведет таблицу умножения чисел от 1 до 10 на 9.
Для решения можно написать два вида кода. Однако, этапы разработки программы, задачи, которые ей необходимо выполнить, очень похожи на прошлые примеры, и она ничем не отличается от решения обычной задачи. Поскольку различие в этих двух кодах лишь в использованном операторе while и for, то рассматривать их по-отдельности нет смысла. Последовательность написания первого кода выглядит так:
Шаг 1. Нужно назвать программу.
Шаг 2. Так как пользователь не вводит никаких данных, то их можно ввести в сам код программы. Тип используемых данных в данном случае – это integer.
Шаг 3. Написание команд. Изначально нужно сделать так, чтобы программа вывела название того, для чего она предназначена. В данной задаче это «Таблица умножения на 9».
Шаг 4. Запись цикла for. С помощью него программа будет последовательно умножать числа от 1 до 10 на 9 и составлять таблицу умножения путём вывода каждого значения по схеме «9x, i, =, p», где i – умножаемое на 9 число, p – результат произведения 9 и i.
Шаг 6. Программа завершает свою работу. Необходимо проверить правильность выведенных данных и, если это необходимо, поправить код для более корректной работы.