Занятие 4. Графическая реализация циклического алгоритма
В рассмотрении циклического алгоритма следует выделить несколько понятий.
Тело цикла – это набор инструкций, предназначенный для многократного выполнения.
Итерация – это единичное выполнение тела цикла.
Переменная цикла – это величина, изменяющаяся на каждой итерации цикла.
Каждый цикл должен содержать следующие необходимые элементы:
- первоначальное задание переменной цикла,
- проверку условия,
- выполнение тела цикла,
- изменение переменной цикла.
Циклы бывают двух видов – с предусловием и с постусловием. В цикле с предусловием сначала проверяется условие входа в цикл, а затем выполняется тело цикла, если условие верно. Цикл с предусловием представлен на рис. 2.9. Цикл с предусловием также может быть задан с помощью счетчика. Это удобно в тех случаях, когда точно известно количество итераций. В общем виде блок-схема, реализующая цикл с предусловием, представлена ниже. Сначала задается начальное значение переменной цикла, затем условие входа в цикл, тело цикла и изменение переменной цикла. Выход из цикла осуществляется в момент проверки условия входа в цикл, когда оно не выполняется, т.е. условие ложно. Цикл с предусловием может ни разу не выполниться, если при первой проверке условия входа в цикл оно оказывается ложным.
Рис.
2.9.
Циклический алгоритм с предусловием в общем виде
В цикле с постусловием сначала выполняется тело цикла, а потом проверяется условие. Циклический алгоритм с постусловием представлен на рис. 2.10.
Рис.
2.10.
Циклический алгоритм с постусловием в общем виде
Если условие верно, то итерация повторяется, если же неверно, то осуществляется выход из цикла. В отличие от цикла с предусловием, любой цикл с постусловием всегда выполнится хоть раз.
Примечание. Как видно из представленных блок-схем для циклов с предусловием и постусловием, условие записывается внутри блока условия (формы ромба), как и в разветвляющемся алгоритме. Принципиальная разница между разветвляющимся и циклическим алгоритмами при графической реализации состоит в том, что в циклическом алгоритме в обязательном порядке присутствует стрелка, идущая наверх. Именно эта стрелка обеспечивает многократный повтор тела цикла.
Приведем простейшие примеры, соответствующие циклическому алгоритму.
Пример 7. Вася звонит Пете, но у Пети может быть занята линия. Составить блок-схему действий Васи в этом случае.
Решение. Когда телефонная линия занята, то необходимо снова и снова набирать номер, пока Петя не закончит предыдущий разговор, и телефонная линия не окажется вновь свободной. Блок-схема представлена на рис. 2.11.
Рис.
2.11.
Блок-схема для примера 7
Здесь тело цикла состоит из одного действия «Набрать номер Пети», т.к. именно это действие следует повторять, пока линия будет занята. Под итерацией цикла понимается очередная попытка дозвониться до Пети. Как таковой переменной цикла здесь нет, т.к. ситуация взята из жизни. Выход из цикла происходит в тот момент, когда условие «У Пети занято» стало неверным, т.е. телефонная линия свободна – действительно, нет необходимости больше набирать номер Пети. В данном примере применен цикл с постусловием, т.к. сначала необходимо набрать номер Пети, ведь иначе мы не можем ответить на вопрос – занята ли линия у Пети.
Пример 8. Ученику требуется купить учебник. Составить блок-схему, описывающую действия ученика в случае, если учебника нет в ряде магазинов.
Решение. Действия ученика в данном примере очевидны: когда он приходит в первый и любой последующий магазины, то возможны два варианта – учебник имеется в наличии или учебника нет в продаже. Если учебника нет в продаже, то ученику следует пойти в другой книжный магазин и спросить данный учебник, и т.д. пока учебник не будет куплен, т.к. перед учеником стоит конечная цель – купить учебник. Мы будем использовать цикл с предусловием, т.к. сначала требуется найти магазин, имеющий в наличии данный учебник. Цикл будет выполняться, пока условие «В данном магазине нет учебника» будет верным, а выход из цикла осуществится, когда условие станет ложным, т.е. когда ученик придет в магазин, в котором есть данный учебник. Действительно, в этом случае ученик купит нужный ему учебник и не будет больше искать книжные магазины. Результат блок-схемы представлен на рис. 2.12.
Рис.
2.12.
Блок-схема для примера 8
Здесь тело цикла состоит из одного действия «Найти другой книжный магазин». Переменной цикла в явном виде нет, но можно подразумевать номер магазина, в который пришел ученик в очередной раз. Как любой другой цикл с предусловием, данный цикл может ни разу не выполниться (не иметь итераций), если в первом же магазине окажется нужный учебник.
Примечание. Если в данную задачу добавить условие выбора учебника в жесткой или мягкой обложке, как в примере 5, то оно появится после выхода из цикла. На реализацию циклического алгоритма данное условие не повлияет.
Пример 9. Даны числа 
. Известно, что число 
меняется от -10 до 10 с шагом 5, 
и не изменяется. Вычислить сумму 
и разность 
чисел 
и 
для всех значений и .
Решение. В отличие от примеров 3 и 6 здесь число меняется от -10 до 10 с шагом 5. Это означает, что число является переменной цикла. Сначала равно -10 – это первоначальное задание переменной цикла. Далее будет изменяться с шагом 5, и т.д. пока не будет достигнуто значение 10 – это соответствует изменению переменной цикла. Итерации надо повторять, пока выполняется условие «
«. Итак, будет принимать следующие значения: -10, -5, 0, 5, 10. Число не будет являться переменной цикла, т.к. и не изменяется по условию задачи. Результат блок-схемы (с предусловием) представлен на рис. 2.13.
Рис.
2.13.
Блок-схема для примера 9 (с предусловием)
Тело цикла состоит из нескольких действий: вычисление суммы, вычисление разности и вывод полученных данных на экран. Таким образом, у нас получится несколько значений сумм и разностей, т.к. изменяется. Количество сумм и количество разностей совпадет с количеством различных значений , т.е. пять.
Данная задача может быть сделана и с циклом с предусловием, и с постусловием. В этом случае тело цикла, условие и изменение переменной цикла будут такими же, как и в цикле с предусловием, но сначала необходимо выполнить тело цикла, а потом проверить условие для выполнения следующей итерации.
Приведем блок-схему, использующую цикл с постусловием, на рис. 2.14.
Рис.
2.14.
Блок-схема для примера 9 (с постусловием)
В данной задаче также могут быть соединены циклический и разветвляющийся алгоритмы, если по условию задачи требуется сравнить полученные значения суммы и разности, как в примере 6. В этом случае цикл можно реализовать как с предусловием, так и с постусловием, а сравнение суммы и разности добавится внутрь тела цикла, т.к. следует сравнить между собой все полученные суммы и разности. Организация самого цикла останется прежней. Приведем на рис. 2.15а блок-схему с предусловием, а на рис. 2.15б блок-схему с постусловием.
Рис.
2.15.
Блок-схема с ветвлением для примера 9: а) с предусловием, б) с постусловием
Часто при решении задач приходится повторять выполнение операций по одним и тем же зависимостям при различных значениях входящих в них переменных и производить многократный проход по одним и тем же участкам алгоритма. Такие участки называются циклами. Алгоритмы, содержащие циклы, называется циклическими. Использование циклов существенно сокращает объем алгоритма.
Различают циклы с наперед известным и наперед неизвестным количеством проходов.
Пример 1. Рассмотрим пример алгоритма с циклом, имеющим наперед неизвестное количество проходов. Для этого решим следующую задачу. Указать наименьшее количество членов ряда натуральных чисел 1, 2, 3, …, сумма которых больше числа К.
Блок-схема алгоритма решения этой задачи приведена на рисунке 1. Она состоит из восьми блоков.
После начала работы в блоке 2 вводится значение числа К. Далее в блоке 3 переменная i получает значение 1, т. е. значение, с которого начнется отсчет натуральных чисел. Переменная S, предназначенная для накопления сумма этих чисел, перед началом суммирования получает значение 0. После этого управление передается блоку 5.
В нем при выполнении команды S = S + i производится сложение содержимого ячеек S и i, а результат записывается в ячейку S. Поскольку до операции сложения было S = 0, i = 1, то после операции будет S = 1. При записи нового значения старое содержимое ячейки S (нуль) стирается, а на его место записывается число 1.
Нужно обратить внимание на то, что если бы до этой операции в блоке 3 не была выполнена команда S = 0 (записать нуль в ячейку S ), то при нахождении суммы S + 1 возникла бы ошибка, поскольку из ячейки S была бы извлечена константа, которая оказалась там после распределения памяти.
После суммирования первого члена последовательности в блоке 6 выполняется проверка условия о превышении суммы S заданного числа К.
Если условие 6 не выполнится, то производится переход к блоку 4, где при выполнении операции значение переменной увеличивается на 1 и становится равным 2. Теперь алгоритм вновь вернется к блоку 5 и к старому значении суммы добавит новый член 2. После этого сумма станет равной 3. В блоке б вновь проверяется условие получения требуемой суммы и т. д. Цепочка блоков 5-4 будет обрабатываться вновь и вновь до того момента, когда однажды при определенном значении переменной i, наконец, выполнится условие S > К, т. е. когда накапливаемая в таком цикле сумма впервые превысит заданное значение К. Переменная i, значение которой при очередном проходе цепочки этих блоков увеличивается на 1, играет роль счетчика этого цикла.
Далее производится переход к блоку 7, где отпечатается значение количества членов ряда (извлечено и отпечатано число из ячейки i, которое там хранится в момент выполнения условия), суммы S и в блоке 8 алгоритм закончит работу.
Пример 2. Теперь приведем пример алгоритма, содержащего цикл с наперед известным количеством проходов (повторений). Алгоритм решает задачу накопления суммы положительных элементов одномерного массива Z длины N ( под длиной массива понимается количество его элементов ). Блок-схема алгоритма дана на рисунке 2.
Вначале в блоке 2 производится ввод двух переменных N и Z. Первая из них представляет одну ячейку. В нее записывается одна константа – число, равное количеству элементов массива Z. Именно такое количество ячеек объединяет другая переменная – Z.
Следует подчеркнуть, что если бы ввод этих переменных в блоке 2 производился в противоположном порядке, то это привело бы к ошибке. Действительно, невозможно заполнить N ячеек массива Z, когда самое N еще не известно (оно будет введено позже Z). Далее в блоке 3 переменной S присвоено начальное значение 0. Это сделано для того, чтобы приготовить ячейку к дальнейшему накоплению необходимой суммы.
Блоки 4-6 представляет собой сам цикл, в котором накапливается сумма.
Для того чтобы понять, как функционирует не только этот, а и любой другой цикл, обратимся к рисункам 3 и 4. На них показана общая структура цикла и его важнейшие параметры.
Как видно из рисунка 3, цикл состоит из заголовка и тела. Всякий цикл обязательно имеет свой счетчик.
На рисунке 4, где показана структура и параметры заголовка цикла, роль такого счетчика выполняет переменная i.
Внутри заголовка после счетчика и символа «=» через запятую указывает начальное и конечное значения счетчика и шаг его изменения (на рисунке 4 их роль выполняют переменные j, k, l соответственно). Если значение шага l = l, то его можно не указывать.
Сначала производится вход в цикл. После этого начинается его выполнение.
Внутри заголовка счетчику первоначально присваивается значение i = j. Затем выполняется блоки, образующие тело цикла. Обработка блоков внутри цикла производится по часовой стрелке. В результате после первого выполнения тела цикла управление вновь передается заголовку. Здесь к текущему значению счетчика добавится шаг. Теперь, если новое значение счетчика не вышло за свои пределы (т. е. не стало больше своего конечного значения при положительном шаге или меньше конечного значения – при отрицательном шаге), то снова выполняется тело цикла, вновь после возврата к заголовку к счетчику добавляется шаг. Так цикл будет выполняться до тех пор, пока значение счетчика однажды не выйдет за предписанный предел. Как только такой предел будет преодолен, произойдет выход из цикла и управление будет передано блоку, который следует сразу за циклом.
Вернемся к блок-схеме рис. 2. Заголовок ее цикла представлен блоком 4. Роль счетчика цикла играет переменная i, которая должна в цикле изменяться от 1 до N. Поскольку шаг явно не указан, то по умолчанию он подразумевается равным 1. Тело цикла образуют блоки 5 и 6.
Сразу после входа в цикл переменная i примет начальное значение i = 1. Далее в блоке 5 выполняется проверка положительности первого элемента массива Z (т. к. i = 1). Если этот элемент действительно положителен, то в блоке б он будет добавлен к переменной S, после чего выполняется возврат к заголовку цикла. Если этот элемент не положителен (т. е. нуль или отрицательный), то будет выполнен переход сразу к заголовку цикла, минуя блок суммирования 6.
На втором круге цикла счетчик i в заголовке увеличится на 1 и станет равным 2. Теперь, при новом выполнении тела цикла, в блоке 5 проверяется на положительность второй элемент массива Z и, если он положителен, то добавляется в сумму и т. д. Последний раз тело цикла выполнится при i = N. При этом значении счетчика проверяется последний элемент массива. Наконец, в заголовке цикла i примет значение N+1. Это значение выходит за предписанный предел, следовательно, произойдет выход из цикла и управление перейдет блоку 7. В этом блоке выводится накопленная сумма и алгоритм закончит работу.
План урока:
Циклы, их виды
Повторение в программировании
Сравнение цикличных структур
С повторяющимися действиями мы сталкиваемся и в обычной жизни и при решении задач. Проход стрелок часов каждую минуту, секунду, час, смена дня и ночи, ежедневные сборы в школу, еженедельная смена уроков, ежегодные поездки на море – примеров циклов повторения миллиарды. Несмотря на разнообразие происходящих процессов, большинство из них можно описать простыми конструкциями. Делая что-то раз за разом, мы не задумываемся, что ученые уже написали алгоритмы с повторением или циклы универсальными способами.
Циклы, их виды
Многие операции, действия выполняются однотипно много раз. Этот процесс повторения называют циклом, а повторяемая последовательность – телом цикла. Процедуру с повторяющимися этапами называют циклической.
Каждое повторение действий в алгоритмах – итерация.
Выделяют 3 основных вида повторяющихся структур:
- с условием выполнения цикла (предусловием);
- с критерием завершения (постусловием);
- с указанным числом повторений цикла.
Описывать подобные процессы удобно схематично или при помощи команд.
Цикл с предусловием
Данную конструкцию еще встречается как «цикл-пока», потому что пока выполняется условием, программа/исполнитель будет проходить шаги снова и снова.Описанный критерий, логическое сравнение — причина начала прохождения повторяемых шагов/команд.
Описание цикла с условием двумя способами:
Порядок выполнения:
- Проверка критерия/логического сравнения.
- Пока результат «Да», «проигрывать по кругу» однотипные операции.
- Если ответ на условие отрицательный, закончить процедуру.
Особенность этой конструкции – существуют такие условия, когда команды не будут выполнены ни разу.
Циклический алгоритм, примеры:
- Написать алгоритм постройки забора из кирпичей высотой 2 м.
алг забор
нач
нц пока есть кирпичи и раствор цемента
если высота забора < 2,0 м
то намазать слой цемента
положить слой кирпичей
иначе сделать сверху декоративный слой
все
кц
кон
- Нарисовать шуточный (но действующий) алгоритм покраски забора «от начала и до обеда.
- Написать алгоритм вычисления частного и остатка от числа, не используя операции деления. В программе используются целые числа.
Заменим деление вычитанием, будем выполнять отнимание, пока остаток не будет меньше вычитаемого – условие выполнения. Число вычитаний и будет частному от деления, это счетчик цикла, а разность, выполненная в последний раз – остаток от деления.
Обозначим x – делимое, y – делитель, q – частное от деления, r – остаток.
Особенности цикла-Пока:
- Если условие ни разу не выполняется, то команды из тела не будут выполнены ни разу. Это нормально, это один из вариантов – нет необходимости в выполнении команд.
- Если же условие всегда истинно, тело операции будут выполняться бесконечное число раз. Такое положение называется зацикливанием. Фактически программа «зависает» и не сможет завершиться сама. Рекомендуется предусмотреть этот вариант.
Циклический алгоритм с постусловием
Такую конструкцию называют «цикл-До». Здесь условие является основанием окончания выполнения команд из тела, то есть, они выполнятся хотя бы раз, даже если условие ложно.
Порядок выполнения цикла с заданным условием:
- Выполнение команд из тела.
- Проверка условия (сравнения определенной величины с заданной).
- Пока ответ на условие «Нет», повторять описанные в теле операции/шаги.
- Если ответ на условие положительный, закончить процедуру.
Описание структуры с постусловием языком блок-схем и на алгоритмическом языке:
Особенности циклов с заданным условием окончания работы:
- Будет хотя бы одно выполнение процедуры;
- Условие описывает завершение повторяемых действий.
Пример: написать программу покраски забора.
Блок схема циклического алгоритма.
Цикл с параметром
Используется для задач, в которых известно количество повторений однотипных шагов, то есть заранее известно, сколько раз нужно выполнить действия. Параметр в этой процедуре– количество повторений цикла(счетчик повторов).
Особенность алгоритмической конструкции повторение с параметром – не бывает зацикливаний, ведь после выполнений указанного числа повторов процесс остановится.
Циклы с известным числом повторений вокруг нас: прием курса лекарств, расписание уроков на неделю, посадка известного числа саженцев, поклейка определенного числа полос обоев.
Пример: написать алгоритм разгрузки и переноса 15 мониторов из авто в компьютерный класс.
Повторение в программировании
Не нужно недооценивать изучение простейших алгоритмических конструкций. Следование, ветвление, повторение – важные конструкции, операторы, используемые в программировании.
Зная их особенности, умея строить блок-схемы и писать решение задач на алгоритмическом языке, позволяет изучать большинство языков программирования легко и быстро.
Большинство задач можно описать при помощи первой конструкции, иногда это неудобно, для каждого типа заданий лучше подбирать оптимальный по выполнению алгоритм.
Цикл начала работы в программировании
Так, описанная выше команда в программировании обозначается словом While. Этот оператор обозначает многократное прохождение участка кода. Это очень востребованная операция.
«While» обозначает на английском «пока». Но не как прощание, а как то, что «делается пока, что-то происходит/выполняется». Этот оператор используется во всех языках программирования, использующих структурный подход (Pascal, Python). Обобщено его записывают так:
Как видим, это очень похоже на запись на алгоритмическом языке – написанное просто, структурировано и понятно.
Подход такой же, как и цикле-пока – проверяется условие, если оно «True», выполняется тело с командами, если «False» – блок программы заканчивается. В этой конструкции не выполненное условие — окончания работы цикла. После этого программа перейдет к следующему блоку команд, то есть «выйдет из цикла».
Цикл окончания работы в программировании
Для записи такой повторяемой конструкции в языках программирования используется оператор repeat. После него следуют команды (тело), после – оператор until, обозначающий условие окончание процесса.
Для этих двух конструкций возможно зацикливание. В программировании применяется специальный оператор break принудительного окончания процесса.
Источник
Цикл со счетчиком в программировании
Для описания цикла с заданным повторением применяют оператор for.
Общий вид блока на языке программирования:
Программа проходит команды из тела и значение счетчика (параметра) становится больше на 1. Чтобы выйти из цикла с фиксированным числом повторений, нужно достичь максимума параметра, который указан в условии задачи.
Сравнение цикличных структур
Блок-схемы повторяющихся алгоритмов позволяют оценить подобие всех 3 видов:
- обязательное наличие условия (для оператора с параметром – это число повторений);
- серия однотипных команд/шагов.
В сложных задачах алгоритм выполнения может содержать любые виды алгоритмических конструкций, в том числе разветвляющиеся циклические алгоритмы.
Хотя все алгоритмы циклической структуры описывают повторяющиеся шаги, у них много отличий.
Построение блок-схем алгоритмов циклических вычислительных процессов
В большинстве
задач, встречающихся на практике,
необходимо вычисления по некоторой
группе формул осуществлять многократно.
Этот многократно повторяющийся участок
вычислительного процесса называют
циклом. Цикл, не содержащий в себя другие
циклы, называют простым. Цикл называется
сложным, если он содержит внутри себя
другие циклы или разветвления. Обычно
при каждом повторении цикла вычисления
осуществляются с новыми значениями
переменных. В любом циклическом процессе
в ходе вычислений необходимо решать
вопрос: повторять вычисления или нет?
Ответ на этот вопрос получают в результате
анализа значений одной или нескольких
переменных, т.е. анализ некоторого
условия. Анализируемую переменную
называют параметром цикла. Из
вышеизложенного следует, что циклический
процесс является разветвляющимся
вычислительным процессом с двумя
ветвями, из которых одна возвращается
на предыдущие блоки, т.е. реализует цикл.
Блок-схема циклического процесса,
независимо от многообразия сводящихся
к нему задач, должна содержать блок
задания начального значения параметру
цикла (2), блок реализации необходимых
вычислений (3), блок изменения параметра
цикла (4) и блок проверки условия окончания
цикла (5)(рис.5.)
Рисунок 5. Блок-схема
циклического процесса
При каждом
выполнении цикла выполняются по формулам
вычисления (3), изменяются параметры
цикла (4), и в зависимости от результата
проверки цикл повторяется, начиная с
блока 3, или заканчивается.
Пример: составить
блок-схему нахождения суммы чисел от 1
до 15 (рис.6).
Рисунок 6. Блок-схема
алгоритма нахождения суммы чисел
Используя символы
для изображения циклов, эту блок-схему
алгоритма можно представить в следующем
виде (рис.7).
Рисунок 7. Блок-схема
циклического процесса
Построение блок-схем алгоритмов итерационных процессов
Итерационным
вычислительным процессом называется
такой циклический процесс, который
продолжается до тех пор, пока разность
между соседними, уточняемыми на каждом
шаге цикла (итерации) значениями, не
окажется меньше или равной некоторой
заданной величине. Характерной
особенностью итерационного процесса
является то, что в нем количество
повторений вычислений заранее неизвестно
и становится определенным только после
окончания вычислений. Решение об
окончании вычислений принимается тогда,
когда результаты счета (значение функции,
искомые величины на очередной отличаются
от предыдущих или эталонных не более,
чем на некоторую, наперед заданную
величину, т.е. найдены с заданной
точностью.
Второй особенностью
итерационного процесса является то,
что результаты вычислений очередного
выполнения цикла используются как
исходные данные при следующем выполнении
цикла, т.е. решение находится
последовательными приближениями, путем
уточнения на каждом шаге цикла.
Пример: для 15
значений переменной Х вычислить функцию
cosx,
используя формулу Тейлора.
cos
x=1-
+
—
+
—
…
Вычисления
ряда необходимо прекратить, как только
очередной учитываемый член ряда окажется
по абсолютной величине не больше
заданного числа
(но в разложении ряда не должно быть
более 50 членов). Знаменатель очередного
члена ряда рекомендуется вычислить
используя значения предыдущего
знаменателя и умножая его на очередные
два числа натурального ряда чисел.
Числитель каждого последующего члена
получается из предыдущего умножением
на –x2
. Это
одновременно позволит изменять знак
каждого очередного члена (рис.8).
Рисунок 8. Блок-схема
алгоритма итерационного вычислительного
процесса.
Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]
- #
- #
- #
- #
- #
- #
- #
- #
- #
- #
- #