Для чего нужен циклический алгоритм
Презентация к уроку
Цель: изучение алгоритмической структуры циклы, создание моделей и алгоритмов для решения практических задач.
Ход урока
I. Актуализация знаний
II. Теоретический материал урока
Большинство практических задач требует многократного повторения одних и тех же действий, т. е. повторного использования одного или нескольких операторов. (Презентация)
Пусть требуется ввести и обработать последовательность чисел. Если чисел всего пять, можно составить линейный алгоритм. Если их тысяча, записать линейный алгоритм можно, но очень утомительно и нерационально. Если количество чисел к моменту разработки алгоритма неизвестно, то линейный алгоритм принципиально невозможен.
Другой пример. Чтобы найти фамилию человека в списке, надо проверить первую фамилию списка, затем вторую, третью и т.д. до тех пор, пока не будет найдена нужная или не будет достигнут конец списка. Преодолеть подобные трудности можно с помощью циклов.
Циклом называется многократно исполняемый участок алгоритма (программы). Соответственно циклический алгоритм — это алгоритм, содержащий циклы.
Различают два типа циклов: с известным числом повторений и с неизвестным числом повторений. При этом в обоих случаях имеется в виду число повторений на стадии разработки алгоритма.
Существует 3 типа циклических структур:
Иначе данные структуры называют циклами типа «Пока», «До», «Для».
Графическая форма записи данных алгоритмических структур:
Цикл с предусловием (иначе цикл пока) имеет вид:
| Форматы записи операторов алгоритма | Блок-схема | Форматы записи операторов на Паскале |
| Пока (условие) нц серия команд кц |  | while условие do begin серия команд; end; |
условие – выражение логического типа.
Цикл может не выполняться ни разу, если значение логического выражения сразу же оказывается ложь.
Серия команд, находящихся между begin и end, выполняются до тех пор, пока условие истинно.
Для того чтобы цикл завершился, необходимо, чтобы последовательность инструкций между BEGIN и END изменяла значение переменных, входящих в условие.
Цикл с постусловием (иначе цикл до) имеет вид:
| Форматы записи операторов алгоритма | Блок-схема | Форматы записи операторов на Паскале |
| В алгоритмическом языке нет команды которая могла бы описать данную структуру, но ее можно выразить с помощью других команд (Например, ветвления). |  | repeat серия команд until условие |
условие – выражение логического типа.
Последовательность инструкций между repeat и until всегда будет выполнено хотя бы один раз;
Для того чтобы цикл завершился, необходимо, чтобы последовательность операторов между repeat и until изменяла значения переменных, входящих в выражение условие.
Инструкция repeat, как и инструкция while, используется в программе, если надо провести некоторые повторяющиеся вычисления (цикл), однако число повторов заранее не известно и определяется самим ходом вычисления.
Цикл с параметром (иначе цикл для) имеет вид:
i – параметр цикла;
a – начальное значение цикла;
b – конечное значение цикла;
h – шаг изменения параметра.
Структура данного цикла иначе называют циклом i раз.
Эта команда выполняется таким образом: параметру i присваивается начальное значение а, сравнивается с конечным значением b и, если оно меньше или равно конечному значению b, выполняется серия команд. Параметру присваивается значение предыдущего, увеличенного на величину h – шага изменения параметра и вновь сравнивается с конечным значением b.
На языке программирования Паскаль шаг изменения параметра может быть равным одному или минус одному.
Если между begin и end находится только один оператор, то операторные скобки можно не писать. Это правило работает для цикла типа «Пока» и «Для».
Рассмотрим пример решения задач с использованием данных структур
Пример.
Вычислить произведение чисел от 1 до 5 используя различные варианты цикла
Составим алгоритм в виде блок-схемы.
Для проверки правильности алгоритма заполним трассировочную таблицу.
Циклические алгоритмы
На этом уроке мы рассмотрим организацию повторений в алгоритмах с помощью циклических конструкций, а также примеры их применения.
На предыдущих уроках мы познакомились с алгоритмами двух типов: линейными и разветвляющимися. Легко заметить, что все алгоритмы, которые мы составляем, обладают общим свойством: при их выполнении каждое действие совершается один раз (или вообще не совершается). В жизни, однако, часто встречаются инструкции, в которых требуется один и тот же набор действий выполнять много раз подряд: “Иди, пока не придешь” и т.д. Используя только ветвление, такие алгоритмы записать не удастся.
Для этого нужна новая форма организации действий – цикл. Повторение действий в алгоритмах называется циклом.
Алгоритм, который предусматривает многократное повторение одного и того же действия, называется циклическим. В отличие от линейных алгоритмов, в которых команды выполняются последовательно одна за другой, в циклические алгоритмы входит последовательность команд, выполняемая многократно. Такая последовательность команд называется телом цикла.
Существуют три основных типа циклов – пока, до и для. Отличие первых двух циклов состоит в том, что в них количество повторений заранее определено. В первом случае, если препятствие никогда не встретится, движение будет продолжаться бесконечно долго. Такие явления при выполнении алгоритмов называются “зацикливанием”.
Любой цикл состоит из нескольких этапов. Это:
Цикл называется арифметическим, если число повторений цикла известно заранее или может быть вычислено.
Цикл, как и любая другая алгоритмическая структура, может быть:
Блок-схемы базовых структур
Цикл, для которого нельзя указать число повторения, и проверка окончания которого происходят по достижению нужного условия, называется итерационным.
 |  |
Рассмотрим алгоритм движения для трех типов циклов.
Цикл ПОКА (число шагов не известно)
Пока нет препятствия
сделать шаг вперед
Завершить цикл;
Цикл ДО (число шагов неизвестно)
Сделать шаг вперед
до встречи с препятствием
Завершить цикл.
Цикл ДЛЯ (число шагов известно)
Для количества шагов менее 100
сделать шаг вперед
Завершить цикл.
Задание № 1: Нужно исправить неверно составленный алгоритм:
На перемене школьник зашел в столовую съесть пирожков, и некто посоветовал ему воспользоваться алгоритмом
Какие строки алгоритма надо поменять местами, чтобы школьник ушел сытым?
Выполнение цикла ПОКА начинается с проверки условия его окончания. Эту разновидность цикла называют циклом с предусловием.
Если условие выполняется, то осуществляется изменение значений аргументов. В противном случае происходит выход из цикла. Может оказаться, что тело цикла не будет выполнено ни разу (если с самого начала условие не выполняется).
Условие выполнения цикла проверяется в конце выполнения тела цикла, то есть в любом случае тело цикла будет выполнено хотя бы один раз.
При выполнении алгоритма последовательность команд в теле цикла повторяется указанное число раз. Правила алгоритмического языка допускают задание любого целого числа повторений. Оно может быть нулевым и даже отрицательным. Эти случаи не считаются ошибочными, просто тело цикла не будет выполнено ни разу, а компьютер сразу перейдет к выполнению команд, записанных после цикла. Среди команд, составляющих тело цикла, могут быть и другие циклы. Программисты часто пользуются циклами, в том числе многократно вложенными.
Задача № 1: Ученик в первый день выучил 5 английских слов. В каждый следующий день он выучивал на 2 слова больше, чем в предыдущий. Сколько английских слов выучит ученик в 10-ый день занятий? Составьте словесный алгоритм и блок-схему (тремя способами).
Задачи по теме: “Циклические алгоритмы” находятся в Приложении1.
Блок-схемы. Графическая реализация алгоритмов
Занятие 4. Графическая реализация циклического алгоритма
В рассмотрении циклического алгоритма следует выделить несколько понятий.
Тело цикла – это набор инструкций, предназначенный для многократного выполнения.
Итерация – это единичное выполнение тела цикла.
Переменная цикла – это величина, изменяющаяся на каждой итерации цикла.
Каждый цикл должен содержать следующие необходимые элементы:
Циклы бывают двух видов – с предусловием и с постусловием. В цикле с предусловием сначала проверяется условие входа в цикл, а затем выполняется тело цикла, если условие верно. Цикл с предусловием представлен на рис. 2.9. Цикл с предусловием также может быть задан с помощью счетчика. Это удобно в тех случаях, когда точно известно количество итераций. В общем виде блок-схема, реализующая цикл с предусловием, представлена ниже. Сначала задается начальное значение переменной цикла, затем условие входа в цикл, тело цикла и изменение переменной цикла. Выход из цикла осуществляется в момент проверки условия входа в цикл, когда оно не выполняется, т.е. условие ложно. Цикл с предусловием может ни разу не выполниться, если при первой проверке условия входа в цикл оно оказывается ложным.
В цикле с постусловием сначала выполняется тело цикла, а потом проверяется условие. Циклический алгоритм с постусловием представлен на рис. 2.10.
Если условие верно, то итерация повторяется, если же неверно, то осуществляется выход из цикла. В отличие от цикла с предусловием, любой цикл с постусловием всегда выполнится хоть раз.
Примечание. Как видно из представленных блок-схем для циклов с предусловием и постусловием, условие записывается внутри блока условия (формы ромба), как и в разветвляющемся алгоритме. Принципиальная разница между разветвляющимся и циклическим алгоритмами при графической реализации состоит в том, что в циклическом алгоритме в обязательном порядке присутствует стрелка, идущая наверх. Именно эта стрелка обеспечивает многократный повтор тела цикла.
Приведем простейшие примеры, соответствующие циклическому алгоритму.
Пример 7. Вася звонит Пете, но у Пети может быть занята линия. Составить блок-схему действий Васи в этом случае.
Решение. Когда телефонная линия занята, то необходимо снова и снова набирать номер, пока Петя не закончит предыдущий разговор, и телефонная линия не окажется вновь свободной. Блок-схема представлена на рис. 2.11.
Здесь тело цикла состоит из одного действия «Набрать номер Пети», т.к. именно это действие следует повторять, пока линия будет занята. Под итерацией цикла понимается очередная попытка дозвониться до Пети. Как таковой переменной цикла здесь нет, т.к. ситуация взята из жизни. Выход из цикла происходит в тот момент, когда условие «У Пети занято» стало неверным, т.е. телефонная линия свободна – действительно, нет необходимости больше набирать номер Пети. В данном примере применен цикл с постусловием, т.к. сначала необходимо набрать номер Пети, ведь иначе мы не можем ответить на вопрос – занята ли линия у Пети.
Пример 8. Ученику требуется купить учебник. Составить блок-схему, описывающую действия ученика в случае, если учебника нет в ряде магазинов.
Решение. Действия ученика в данном примере очевидны: когда он приходит в первый и любой последующий магазины, то возможны два варианта – учебник имеется в наличии или учебника нет в продаже. Если учебника нет в продаже, то ученику следует пойти в другой книжный магазин и спросить данный учебник, и т.д. пока учебник не будет куплен, т.к. перед учеником стоит конечная цель – купить учебник. Мы будем использовать цикл с предусловием, т.к. сначала требуется найти магазин, имеющий в наличии данный учебник. Цикл будет выполняться, пока условие «В данном магазине нет учебника» будет верным, а выход из цикла осуществится, когда условие станет ложным, т.е. когда ученик придет в магазин, в котором есть данный учебник. Действительно, в этом случае ученик купит нужный ему учебник и не будет больше искать книжные магазины. Результат блок-схемы представлен на рис. 2.12.
Здесь тело цикла состоит из одного действия «Найти другой книжный магазин». Переменной цикла в явном виде нет, но можно подразумевать номер магазина, в который пришел ученик в очередной раз. Как любой другой цикл с предусловием, данный цикл может ни разу не выполниться (не иметь итераций), если в первом же магазине окажется нужный учебник.
Примечание. Если в данную задачу добавить условие выбора учебника в жесткой или мягкой обложке, как в примере 5, то оно появится после выхода из цикла. На реализацию циклического алгоритма данное условие не повлияет.
Тело цикла состоит из нескольких действий: вычисление суммы, вычисление разности и вывод полученных данных на экран. Таким образом, у нас получится несколько значений сумм и разностей, т.к. 
изменяется. Количество сумм и количество разностей совпадет с количеством различных значений , т.е. пять.
Данная задача может быть сделана и с циклом с предусловием, и с постусловием. В этом случае тело цикла, условие и изменение переменной цикла будут такими же, как и в цикле с предусловием, но сначала необходимо выполнить тело цикла, а потом проверить условие для выполнения следующей итерации.
Приведем блок-схему, использующую цикл с постусловием, на рис. 2.14.
В данной задаче также могут быть соединены циклический и разветвляющийся алгоритмы, если по условию задачи требуется сравнить полученные значения суммы и разности, как в примере 6. В этом случае цикл можно реализовать как с предусловием, так и с постусловием, а сравнение суммы и разности добавится внутрь тела цикла, т.к. следует сравнить между собой все полученные суммы и разности. Организация самого цикла останется прежней. Приведем на рис. 2.15а блок-схему с предусловием, а на рис. 2.15б блок-схему с постусловием.
Алгоритмизация | Лекция №4
Циклические алгоритмы.
Содержание:
Циклические алгоритмы применяются в тех случаях, когда требуется реализовать многократно повторяющиеся однотипные вычисления.
Циклическим называется алгоритм, в котором некоторая часть операций (тело цикла – последовательность команд) выполняется многократно, т.е. более одного раза. Однако «многократно» не значит «до бесконечности». Организация циклов, никогда не приводящая к остановке в выполнении алгоритма, является нарушением требования его результативности – получения результата за конечное число шагов.
В любом цикле должна быть переменная, которая управляет выходом из цикла, т.е. определяет число повторений цикла.
Перед операцией цикла осуществляются операции присвоения начальных значений тем объектам, которые используются в теле цикла. В цикл входят в качестве базовых следующие структуры:
Телом цикла или рабочей частью цикла называется последовательность действий, которая должна выполняться на каждом шаге цикла (т.е. определяет число повторений цикла).
Циклы со счетчиком
В циклах такого типа известно число повторений цикла, т.е. оно является фиксированным числом. В этом случае переменная, которая считает количество повторений (шагов) цикла, называется счетчиком цикла (или параметром цикла, или управляющей переменной цикла).
Блок-схема циклического алгоритма в этом случае выглядит так: 
Такая блок-схема хорошо иллюстрирует работу цикла со счетчиком. Перед выполнением первого шага цикла счетчику цикла должно быть присвоено начальное значение – любое число в зависимости от алгоритма. Если величина счетчика цикла не превышает конечное значение, то далее будет выполняться группа действий, составляющих тело цикла. После выполнения тела цикла счетчик цикла изменяется на определенную величину – шаг изменения счетчика цикла h. Если полученное значение счетчика цикла не превысит конечное значение, то цикл продолжится до тех пор, пока счетчик цикла не станет больше конечного значения – тогда управление передается действию, следующему за циклом.
В блок-схемах для изображения цикла со счетчиком используют блок «Подготовка». В блоке «Подготовка» записывается счетчик цикла (I), далее последовательно указываются начальное значение (Iн), конечное значение (Iк) счетчика цикла и шаг его изменения (h). Если шаг изменения h равен 1, его можно не записывать. Желательно, чтобы линия потока входила в блок сверху, линия потока к телу цикла выходила снизу, слева (или справа) входила линия потока перехода к следующему шагу цикла, а справа (или слева) выходила линия потока – выход из цикла.
При использовании цикла со счетчиком необходимо соблюдать некоторые требования:
Циклы с предусловием
Циклы с предусловием чаще всего используются тогда, когда неизвестно число повторений цикла. Циклы с предусловием – это такие циклы, в которых до начала выполнения тела цикла проверяется условие выполнения его шага цикла. Если значение этого условия истинно (т.е. условие выполняется), то выполняется тело цикла. В теле цикла должно изменяться значение по крайней мере одной переменной, которая влияет на значение условия (иначе произойдет «зацикливание»). Далее опять проверяется условие выполнения цикла, и если значение условия ложно, то осуществляется выход из цикла.
Можно использовать и еще один вариант этого цикла, когда проверяется не истинность значения условия, а ложность. В этом случае выход из цикла происходит, когда значение условия цикла становится истинным. Тот или иной вариант цикла используется в зависимости от того, какое условие в данном алгоритме программисту удобнее использовать.
На блок-схеме такой цикл реализуется следующей конструкцией:
Особенность этого цикла в том, что тело цикла может не выполниться ни разу, если условие первоначально ложно в первом варианте (или истинно во втором).
Циклы с постусловием
Этот тип цикла также используется при неизвестном заранее количестве повторений цикла, но в отличие от цикла с предусловием здесь условие на выход из цикла проверяется после того, как выполнились операторы тела цикла, поэтому хотя бы один раз тело цикла будет обязательно выполнено.
На блок-схеме этот тип цикла изображается следующим образом:
Сложные циклы
Циклы, которые содержат внутри себя (в теле цикла) один или несколько других циклов, называются сложными или вложенными циклами.
При этом циклы, охватывающие другие циклы, называются внешними. А циклы, входящие во внешние циклы, — внутренними циклами.
На каждом шаге внешнего цикла внутренний цикл «прокручивается» полностью.
Контрольные вопросы
Для чего нужен циклический алгоритм
Понятие алгоритма. Исполнитель алгоритма. Свойства алгоритма. Способы записи алгоритмов.
Основные алгоритмические структуры: следование, ветвление, цикл; изображение
на блок-схемах. Вспомогательные алгоритмы.
Алгоритм – описание последовательности действий (план), строгое исполнение которых приводит к решению поставленной задачи за конечное число шагов.
Вы постоянно сталкиваетесь с этим понятием в различных сферах деятельности человека (кулинарные книги, инструкции по использованию различных приборов, правила решения математических задач. ). Обычно мы выполняем привычные действия не задумываясь, механически. Например, вы хорошо знаете, как открывать ключом дверь. Однако, чтобы научить этому малыша, придется четко разъяснить и сами эти действия и порядок их выполнения:
1. Достать ключ из кармана.
2. Вставить ключ в замочную скважину.
3. Повернуть ключ два раза против часовой стрелки.
Если вы внимательно оглянитесь вокруг, то обнаружите множество алгоритмов которые мы с вами постоянно выполняем. Мир алгоритмов очень разнообразен. Несмотря на это, удается выделить общие свойства, которыми обладает любой алгоритм.
Дискретность (от лат. discretus — разделённый, прерывистый, раздельность) (алгоритм должен состоять из конкретных действий, следующих в определенном порядке);
Детерминированность (от. лат. determinate – определенность, точность) (любое действие должно быть строго и недвусмысленно определено в каждом случае);
Конечность (каждое действие и алгоритм в целом должны иметь возможность завершения);
Массовость (один и тот же алгоритм можно использовать с разными исходными данными);
Результативность (отсутствие ошибок, алгоритм должен приводить к правильному результату для всех допустимых входных значениях).
1. Линейный алгоритм (описание действий, которые выполняются однократно в заданном порядке);
2. Циклический алгоритм (описание действий, которые должны повторятся указанное число раз или пока не выполнено заданное условие);
3. Разветвляющийся алгоритм (алгоритм, в котором в зависимости от условия выполняется либо одна, либо другая последовательность действий);
4. Вспомогательный алгоритм (алгоритм, который можно использовать в других алгоритмах, указав только его имя).
На практике наиболее распространены следующие формы представления алгоритмов:
В письменной форме на естественном языке.
В письменной форме на формальном языке.
Для более наглядного представления алгоритма широко используется графическая форма – блок-схема, которая составляется из стандартных графических объектов.
При графическом представлении алгоритм изображается в виде последовательности связанных между собой функциональных блоков, каждый из которых соответствует выполнению одного или нескольких действий. В блок-схеме каждому типу действий (вводу исходных данных, вычислению значений выражений, проверке условий, управлению повторением действий, окончанию обработки и т.п.) соответствует геометрическая фигура.
Стадии создания алгоритма:
1. Алгоритм должен быть представлен в форме, понятной человеку, который его разрабатывает (определить цель, наметить план действий).
2. Алгоритм должен быть представлен в форме, понятной тому объекту (в том числе и человеку), который будет выполнять описанные в алгоритме действия (выбрать среду и объект алгоритма, детализировать алгоритм).
Объект, который будет выполнять алгоритм, обычно называют исполнителем.
Назначение исполнителя точно выполнить предписания алгоритма, подчас не задумываясь о результате и целях, т.е. формально. Идеальными исполнителями являются машины, роботы, компьютеры.
Компьютер – автоматический исполнитель алгоритмов.
Алгоритм, записанный на «понятном» компьютеру языке программирования, называется программой.
Линейный алгоритм
Линейный алгоритм – описание действий, которые выполняются однократно в заданном порядке. Исполнитель выполняет действия последовательно, одно за другим в том порядке в котором они следуют.
Блок-схема линейного алгоритма:
Циклический алгоритм – описание действий, которые должны повторяться указанное число раз или пока не выполнено заданное условие.
Перечень повторяющихся действий называют телом цикла.
Циклические алгоритмы бывают двух типов:
Циклы со счетчиком, в которых какие-то действия выполняются определенное число раз;
Циклы с условием, в которых тело цикла выполняется, в зависимости от какого-либо условия. Различают циклы с предусловием и постусловием.
Циклы со счетчиком используют когда заранее известно какое число повторений тела цикла необходимо выполнить. Например, на уроке физкультуры вы должны пробежать некоторое количество кругов вокруг стадиона.
Для счетчика от нач. значения до кон. значения выполнить действие.
Часто бывает так, что необходимо повторить тело цикла, но заранее не известно, какое количество раз это надо сделать. В таких случаях количество повторений зависит от некоторого условия. Такие циклы называются циклы с условием. Циклы в которых сначала проверяется условие, а затем, возможно, выполняется тело цикла называют циклы с предусловием. Если условие проверяется после первого выполнения тела цикла, то циклы называются циклы с постусловием.
Например, в субботу вечером вы смотрите телевизор. Время от времени поглядываете на часы и если время меньше полуночи, то продолжаете смотреть телевизор, если это не так, то вы прекращаете просмотр телепередач.
В общем случае схема циклического алгоритма с условием будет выглядеть так:
Пока условие повторять действие.
При составлении циклических алгоритмов важно думать о том, чтобы цикл был конечным. Ситуация, при которой выполнение цикла никогда не заканчивается, называется зацикливанием.
Во многих случаях требуется, чтобы при одних условиях выполнялась одна последовательность действий, а при других – другая.
Если пошел дождь, то надо открыть зонт.
Если прозвенел будильник, то надо вставать.
Если встречу Сашу, то скажу ему …
Если встречу Сашу, то скажу ему …, иначе зайду к нему сам.
Эти предложения начинаются с проверки какого-либо условия: пошел дождь, прозвенел будильник, встретил Сашу… Далее в зависимости мы либо вылиняем какое-либо действие, либо не выполняем его (или выполняем какое-то другое действие).
Компьютер тоже в зависимости от какого-либо условия может выполнять или не выполнять те или иные действия. Алгоритм, в котором используется условие, получил название разветвляющегося, так как в зависимости от значения условия выбираются те или иные действия.
В общем случае схема разветвляющегося алгоритма будет выглядеть так: «если условие, то действие 1, иначе действие 2» (Если встречу Сашу, то скажу ему …, иначе зайду к нему сам.). Так же можно использовать неполную форму: «если условие, то действие» (Если встречу Сашу, то скажу ему ). В этом случае не предусматривается действий на случай невыполнения условия.
Условие – это высказывание которое может быть либо истинно, либо ложно.
Еще раз обратим внимание, что существует две формы ветвления – неполная (когда присутствует только одна ветвь, т.е. в зависимости от истинности условия либо выполняется, либо не выполняется действие) и полная (когда присутствуют две ветви, т.е. в зависимости от истинности условия выполняется либо одно, либо другое действие).
Вспомогательный алгоритм – алгоритм, который можно использовать в других алгоритмах, указав только его имя.