Примеры блок схем цикла for
Предыдущий раздел:
Следующий раздел:
3.1. Цикл for
Современные компьютеры выполняют миллиарды операций в секунду. Однако к счастью, программистам не приходится писать программы из миллиардов строк кода. Чтобы с помощью короткой программы указать на необходимость выполнения большого количества операций используется оператор цикла, суть которого в многократном повторении одного и того же набора инструкций. На рис. 1 работа циклов показана с помощью блок-схем.
В варианте (а) если «условие» истинно выполняются «операторы». После этого снова проверяется «условие» и, если оно по прежнему истинно, то снова выполняются операторы и так далее, пока условие не станет ложным. Вариант (б) подобен варианту (а), отличие только в том, что сначала выполняются «операторы», а только затем делается проверка условия, на основе которой мы решаем, нужно ли повторять их выполнение.
Рис. 1. Блок-схемы циклов.
В языке Паскаль существует несколько вариантов организации циклов. Рассмотрим один из них – так называемый цикл с параметром или цикл for. Чтобы записать его нам потребуется переменная целого типа, например:
var i: integer;
Схема его записи выглядит следующим образом:
for i := to do begin end;
Здесь i – так называемая переменная-счетчик (разумеется, ее не обязательно называть именно i, это может быть любая переменная целого типа). Начальное и конечное значение это любые выражения, имеющее значение целого типа. Когда оператор цикла начинает работу переменная счетчик принимает начальное значение, затем выполняются , после этого счетчик увеличивается на единицу, и снова выполняются операторы. Процесс повторяется, пока счетчик не окажется больше конечного значения. Например, если начальное значение 2, а конечное 3, то будут выполнены 2 раза. Область между словами begin и end, где располагаются повторяющие в цикле операторы, называется телом цикла.
На рис. 2 показана блок-схема работы этого цикла.
Рис. 2. Схема работы цикла с параметром (for).
Пример 1: Напечатать слово Hello на экране 100 раз.
Один раз слово Hello можно напечатать с помощью процедуры
writeln(‘Hello’);
Чтобы напечатать его 100 раз, надо эту инструкцию поместить внутрь оператора цикла, который выполнится нужное количество раз. А именно:
for n := 1 to 100 do begin writeln(‘Hello’); end;
Переменной счетчику n будет присвоено начальное значение 1. Затем Hello будет напечатано 1-й раз. Счетчик увеличится на 1 и Hello напечатается 2-й раз и т.д.
Перечислим в одном месте все правила, касающиеся работы цикла с параметром:
1) Переменная-счетчик должна быть обязательно целого типа (например, integer).
2) Начальное и конечное значения задаются выражениями, значение которых также имеет целый тип.
Нельзя, например, записать цикл
for x := 0 to 2*Pi do …
Но можно, например:
for k := 2*round(n*1000) to trunc(2*pi)+1 do …
3) Если конечное значение меньше начального цикл не выполнится ни разу.
4) После окончания работы переменная-счетчик «портится». Глядя на блок-схему можно предположить, что после окончания работы цикла она на единицу больше конечного значения. На практике это не так и она может иметь любое значение. Отсюда правило: если переменная используется, как счетчик шагов в цикле не следует обращаться к ней после того, как цикл завершил свою работу.
5) Если в теле цикла содержится всего один оператор, то слова begin и end, ограничивающие тело цикла можно опустить. Такая ситуация у нас была в примере 1. Там можно было написать:
for n := 1 to 100 do writeln(‘Hello’);
6) Важное стилистическое правило: хотя это и не запрещено, не следует в теле цикла использовать какие-либо операторы, меняющие значения переменной-счетчика. В частности нельзя ей ничего присваивать. Нарушение этого правила ведет к увеличению вероятности сделать трудно обнаруживаемую ошибку. Соблюдение – никак не ограничивает ваши возможности.
7) Тело цикла может содержать любые операторы. Следовательно, туда можно поместить другой оператор цикла. Переменные-счетчики в этом случае у циклов должны быть разные. Если их сделать одинаковыми это нарушит предыдущее правило – внутренний цикл изменит значение переменной-счетчика внешнего.
8) Еще одно стилистическое правило: все операторы тела цикла должны быть дополнительно сдвинуты на 2-3 пробела вправо (см. запись программы в примере 1 и последующих примеров ниже по тексту).
Итак, одни и те же действия мы можем выполнять сколько угодно раз, но что полезного это дает? Печатать 100 раз Hello не очень важное приложение. Чтобы сделать что-то полезное, надо чтобы действия на каждом шаге цикла чем-то различались. Первый способ добиться этого состоит в использовании переменной счетчика, которая на каждом шаге принимает различные значения.
Пример 2: Напечатать все целые числа в диапазоне от 5 до 25.
for i := 5 to 25 do writeln(i);
Как видно, в данном примере на каждом шаге печатаются разные числа.
Используем эту возможность для чего-то более полезного.
Пример 3: Табуляция функций.
Под табуляцией функций подразумевается составление таблицы значений функции для некоторого диапазона значений аргумента. Пусть требуется N значений функции f(x) в диапазоне от Xmin до Xmax. Рассматривая переменную-счетчик как номер аргумента функции, составим выражение, позволяющее по номеру получить значение аргумента:
x := Xmin + (Xmax – Xmin)*(i-1)/(N-1).
Убедитесь, что действительно первое значение аргумента (при i = 1) составляет x = Xmin, а N-е (i = N) – x = Xmax. Вычисляя на каждом шаге значение аргумента, можем тут же вычислить функцию и составить требуемую таблицу.
for i := 1 to N do begin x := Xmin+(Xmax-Xmin)*(i-1)/(N-1); y := f(x); writeln(x, ‘ ‘, y); end;
Вместо f(x) в приведенной программе следует подставить любое выражение, составленное по правилам языка Паскаль.
Следующий раздел:
Предыдущий раздел:
Добавить комментарий
Источник
Схема – это абстракция какого-либо процесса или системы, наглядно отображающая наиболее значимые части. Схемы широко применяются с древних времен до настоящего времени – чертежи древних пирамид, карты земель, принципиальные электрические схемы. Очевидно, древние мореплаватели хотели обмениваться картами и поэтому выработали единую систему обозначений и правил их выполнения. Аналогичные соглашения выработаны для изображения схем-алгоритмов и закреплены ГОСТ и международными стандартами.
На территории Российской Федерации действует единая система программной документации (ЕСПД), частью которой является Государственный стандарт – ГОСТ 19.701-90 «Схемы алгоритмов программ, данных и систем» [1]. Не смотря на то, что описанные в стандарте обозначения могут использоваться для изображения схем ресурсов системы, схем взаимодействия программ и т.п., в настоящей статье описана лишь разработка схем алгоритмов программ.
Рассматриваемый ГОСТ практически полностью соответствует международному стандарту ISO 5807:1985.
Содержание:
- Элементы блок-схем алгоритмов
- Примеры блок-схем
- Нужны ли блок-схемы? Альтернативы
Элементы блок-схем алгоритмов
Блок-схема представляет собой совокупность символов, соответствующих этапам работы алгоритма и соединяющих их линий. Пунктирная линия используется для соединения символа с комментарием. Сплошная линия отражает зависимости по управлению между символами и может снабжаться стрелкой. Стрелку можно не указывать при направлении дуги слева направо и сверху вниз. Согласно п. 4.2.4, линии должны подходить к символу слева, либо сверху, а исходить снизу, либо справа.
Есть и другие типы линий, используемые, например, для изображения блок-схем параллельных алгоритмов, но в текущей статье они, как и ряд специфических символов, не рассматриваются. Рассмотрены лишь основные символы, которых всегда достаточно студентам.
| Терминатор начала и конца работы функции | Терминатором начинается и заканчивается любая функция. Тип возвращаемого значения и аргументов функции обычно указывается в комментариях к блоку терминатора. |
| Операции ввода и вывода данных | В ГОСТ определено множество символов ввода/вывода, например вывод на магнитные ленты, дисплеи и т.п. Если источник данных не принципиален, обычно используется символ параллелограмма. Подробности ввода/вывода могут быть указаны в комментариях. |
| Выполнение операций над данными | В блоке операций обычно размещают одно или несколько (ГОСТ не запрещает) операций присваивания, не требующих вызова внешних функций. |
| Блок, иллюстрирующий ветвление алгоритма | Блок в виде ромба имеет один вход и несколько подписанных выходов. В случае, если блок имеет 2 выхода (соответствует оператору ветвления), на них подписывается результат сравнения – «да/нет». Если из блока выходит большее число линий (оператор выбора), внутри него записывается имя переменной, а на выходящих дугах – значения этой переменной. |
| Вызов внешней процедуры | Вызов внешних процедур и функций помещается в прямоугольник с дополнительными вертикальными линиями. |
| Начало и конец цикла | Символы начала и конца цикла содержат имя и условие. Условие может отсутствовать в одном из символов пары. Расположение условия, определяет тип оператора, соответствующего символам на языке высокого уровня – оператор с предусловием (while) или постусловием (do … while). |
| Подготовка данных | Символ «подготовка данных» в произвольной форме (в ГОСТ нет ни пояснений, ни примеров), задает входные значения. Используется обычно для задания циклов со счетчиком. |
| Соединитель | В случае, если блок-схема не умещается на лист, используется символ соединителя, отражающий переход потока управления между листами. Символ может использоваться и на одном листе, если по каким-либо причинам тянуть линию не удобно. |
| Комментарий | Комментарий может быть соединен как с одним блоком, так и группой. Группа блоков выделяется на схеме пунктирной линией. |
Примеры блок-схем
В качестве примеров, построены блок-схемы очень простых алгоритмов сортировки, при этом акцент сделан на различные реализации циклов, т.к. у студенты делают наибольшее число ошибок именно в этой части.
Сортировка вставками
Массив в алгоритме сортировки вставками разделяется на отсортированную и еще не обработанную части. Изначально отсортированная часть состоит из одного элемента, и постепенно увеличивается.
На каждом шаге алгоритма выбирается первый элемент необработанной части массива и вставляется в отсортированную так, чтобы в ней сохранялся требуемый порядок следования элементов. Вставка может выполняться как в конец массива, так и в середину. При вставке в середину необходимо сдвинуть все элементы, расположенные «правее» позиции вставки на один элемент вправо. В алгоритме используется два цикла – в первом выбираются элементы необработанной части, а во втором осуществляется вставка.
Блок-схема алгоритма сортировки вставками
В приведенной блок-схеме для организации цикла используется символ ветвления. В главном цикле (i < n) перебираются элементы необработанной части массива. Если все элементы обработаны – алгоритм завершает работу, в противном случае выполняется поиск позиции для вставки i-того элемента. Искомая позиция будет сохранена в переменной j в результате выполнения внутреннего цикла, осуществляющем сдвиг элементов до тех пор, пока не будет найден элемент, значение которого меньше i-того.
На блок-схеме показано каким образом может использоваться символ перехода – его можно использовать не только для соединения частей схем, размещенных на разных листах, но и для сокращения количества линий. В ряде случаев это позволяет избежать пересечения линий и упрощает восприятие алгоритма.
Сортировка пузырьком
Сортировка пузырьком, как и сортировка вставками, использует два цикла. Во вложенном цикле выполняется попарное сравнение элементов и, в случае нарушения порядка их следования, перестановка. В результате выполнения одной итерации внутреннего цикла, максимальный элемент гарантированно будет смещен в конец массива. Внешний цикл выполняется до тех пор, пока весь массив не будет отсортирован.
Блок-схема алгоритма сортировки пузырьком
На блок-схеме показано использование символов начала и конца цикла. Условие внешнего цикла (А) проверяется в конце (с постусловием), он работает до тех пор, пока переменная hasSwapped имеет значение true. Внутренний цикл использует предусловие для перебора пар сравниваемых элементов. В случае, если элементы расположены в неправильном порядке, выполняется их перестановка посредством вызова внешней процедуры (swap). Для того, чтобы было понятно назначение внешней процедуры и порядок следования ее аргументов, необходимо писать комментарии. В случае, если функция возвращает значение, комментарий может быть написан к символу терминатору конца.
Сортировка выбором
В сортировке выбором массив разделяется на отсортированную и необработанную части. Изначально отсортированная часть пустая, но постепенно она увеличивается. Алгоритм производит поиск минимального элемента необработанной части и меняет его местами с первым элементом той же части, после чего считается, что первый элемент обработан (отсортированная часть увеличивается).
Блок-схема сортировки выбором
На блок-схеме приведен пример использования блока «подготовка», а также показано, что в ряде случаев можно описывать алгоритм более «укрупнённо» (не вдаваясь в детали). К сортировке выбором не имеют отношения детали реализации поиска индекса минимального элемента массива, поэтому они могут быть описаны символом вызова внешней процедуры. Если блок-схема алгоритма внешней процедуры отсутствует, не помешает написать к символу вызова комментарий, исключением могут быть функции с говорящими названиями типа swap, sort, … .
На блоге можно найти другие примеры блок-схем:
- блок-схема проверки правильности расстановки скобок арифметического выражения [2];
- блок-схемы алгоритмов быстрой сортировки и сортировки слиянием [3].
Часть студентов традиционно пытается рисовать блок-схемы в Microsoft Word, но это оказывается сложно и не удобно. Например, в MS Word нет стандартного блока для терминатора начала и конца алгоритма (прямоугольник со скругленными краями, а не овал). Наиболее удобными, на мой взгляд, являются утилиты MS Visio и yEd [5], обе они позволяют гораздо больше, чем строить блок-схемы (например рисовать диаграммы UML), но первая является платной и работает только под Windows, вторая бесплатная и кроссплатфомренная. Все блок-схемы в этой статье выполнены с использованием yEd.
Частные конторы никакие блок-схемы не используют, в книжках по алгоритмам [6] вместо них применяют словесное описание (псевдокод) как более краткую форму. Возможно блок-схемы применяют на государственных предприятиях, которые должны оформлять документацию согласно требованиям ЕСПД, но есть сомнения – даже для регистрации программы в Государственном реестре программ для ЭВМ никаких блок-схем не требуется.
Тем не менее, рисовать блок-схемы заставляют школьников (примеры из учебников ГОСТ не соответствуют) – выносят вопросы на государственные экзамены (ГИА и ЕГЭ), студентов – перед защитой диплом сдается на нормоконтроль, где проверяется соответствие схем стандартам.
Разработка блок-схем выполняется на этапах проектирования и документирования, согласно каскадной модели разработки ПО, которая сейчас почти не применяется, т.к. сопровождается большими рисками, связанными с ошибками на этапах проектирования.
Появляются подозрения, что система образования прогнила и отстала лет на 20, однако аналогичная проблема наблюдается и за рубежом. Международный стандарт ISO 5807:1985 мало чем отличается от ГОСТ 19.701-90, более нового стандарта за рубежом нет. Там же производится множество программ для выполнения этих самых схем – Dia, MS Visio, yEd, …, а значит списывать их не собираются. Вместо блок-схем иногда применяют диаграммы деятельности UML [6], однако удобнее они оказываются, разве что при изображении параллельных алгоритмов.
Периодически поднимается вопрос о том, что ни блок-схемы, ни UML не нужны, да и документация тоже не нужна. Об этом твердят программисты, придерживающиеся методологии экстремального программирования (XP) [7], ходя даже в их кругу нет единого мнения.
В ряде случаев, программирование невозможно без рисования блок-схем, т.к. это один процесс – существуют визуальные языки программирования, такие как ДРАКОН [8], кроме того, блок-схемы используются для верификации алгоритмов (формального доказательства их корректности) методом индуктивных утверждений Флойда [9].
В общем, единого мнения нет. Очевидно, есть области, в которых без чего-то типа блок-схем обойтись нельзя, но более гибкой альтернативы нет. Для формальной верификации необходимо рисовать подробные блок-схемы, но для проектирования и документирования такие схемы не нужны – я считаю разумным утверждение экстремальных программистов о том, что нужно рисовать лишь те схемы, которые помогают в работе и не требуют больших усилий для поддержания в актуальном состоянии [10].
Список использованных источников:
- ГОСТ 19.701-90 (ИСО 5807-85) «Единая система программной документации».
- Алгоритм. Свойства алгоритма https://pro-prof.com/s/578
- Алгоритмы сортировки слиянием и быстрой сортировки https://pro-prof.com/s/813
- yEd Graph Editor https://www.yworks.com/products/yed
- Книги: алгоритмы https://pro-prof.com/books-algorithms
- Рамбо Дж., Якобсон А., Буч Г. UML: специальный справочник. -СПб.: Питер, 2002. -656 с.
- Кент Бек Экстремальное программирование: разработка через тестирование – СПб.: Питер – 2003
- Визуальный язык ДРАКОН https://drakon.su/
- Шилов Н.В. Верификация шаблонов алгоритмов для метода отката и метода ветвей и границ. Моделирование и анализ информационных систем, ISSN 1818 – 1015, т.18, №4, 2011
- Брукс Ф., Мифический человеко – месяц или как создаются программные системы. СПб. Символ Плюс, 1999 – 304 с. ил.
Источник
Цикл с параметром был уже рассмотрен нами в разделе “Алгоритм” в теме “Виды алгоритмов”.
Цикл с параметром используется, когда заранее известно сколько раз должен выполниться цикл.
Формат записи цикла:
For <пар.цикла> := <нач.знач> to <кон.знач.> do <оператор>
Здесь for, to, do – зарезервированные слова (для, до, выполнить);
<пар. цикла> – параметр цикла – переменная целочисленного типа (типа integer);
<нач. знач.> – начальное значение – число или переменная целочисленного типа (типа integer);
<кон. знач.> – конечное значение – число или переменная целочисленного типа (типа integer);
<оператор> – произвольный оператор Паскаля.
Пример: For i:=1 to n do <оператор>
здесь i – параметр цикла
1 – начальное значение
n – конечное значение
Если в теле цикла используется несколько операторов, тогда, используются операторные скобки: begin … end.
При выполнении оператора for вначале вычисляется выражение <нач .знач.> и осуществляется присваивание его значения переменной цикла <пар .цикла> := <нач. знач.>. Далее сравниваются <пар .цикла> и <кон.знач.>. До тех пор, пока они не станут равными будет выполняться оператор (операторы). Значение переменной цикла <нач.знач> автоматически увеличивается на единицу в ходе выполнения цикла. Надо сразу заметить, что задать шаг цикла, отличный от 1 в этом операторе нельзя.
Пример:
Возможны такие записи оператора цикла:
1) for i:= 1 to n do s1;
2) for i:= 3 to 10 do s1;
3) for i := a to b do s1;
4) for i := a to b do
begin
s1;
s2;
…
sn
end;
Здесь s1, s2, s3, … sn – операторы цикла.
Пример:
Составить программу вывода на экран чисел от 1 до 10.
| Блок-схема: | Программный код: Program Problem; {Вывод чисел} var i : integer; begin for i:=1 to 10 do writeln (i); redaln; end. |
Пример:
Составить программу вычисления факториала числа n, т. е. n!. (0! = 1)
| Блок-схема: | Программный код: Program Problem1; {Вычисление факториала числа n!} var n, f, i : integer; begin write(‘Введите натуральное число’); readln(n); f := 1; if n <> 0 then for i := 1 to n do f := f*i; writeln (‘Факториал числа ‘, n, ‘ равен ‘, f); redaln; end. |
Объяснение программы:
Переменная n – для вводимого пользователем числа, факториал которого надо найти; f – переменная, в которой будет “накапливаться” значение факториала числа n; i – переменная цикла.
Устанавливается первоначальное значение переменной f := 1.
Далее начинается цикл. Переменной i присваивается начальное значение 1; оно сравнивается с конечным – n (1 <= n), если условие истинно, тогда выполняется оператор (в этой программе он один): f := f*i, 1*1=1; значение переменной цикла увеличивается на 1, т. е. станет равным: i := i + 1, 1 + 1 = 2 и цикл повторяется.
Когда значение i станет равным n, тогда цикл выполнится последний раз, потому что следующее значение i будет n + 1, что больше конечного значения n, условие i <= n – ложно, цикл не выполняется.
Существует другая форма оператора цикла For:
Формат записи цикла:
For <пар.цикла> := <нач.знач> downto <кон.знач.> do <оператор>
Замена зарезервированного слова to на downto означает, что шаг параметра цикла равен (-1).
Изменение значения параметра идет от большего значения к меньшему, т. е. <нач. знач.> <кон. знач.>.
Пример:
Возможны такие записи оператора цикла:
1) for i:= n downto 1 do s1;
2) for i:= 10 downto 3 do s1;
3) for i := b downto a do s1; (при условии, что b>a)
4) for i := b downto a do
begin
s1;
s2;
…
sn
end; (при условии, что b>a)
Здесь s1, s2, s3, … sn – операторы цикла.
Пример: Программу вычисления факториала числа можно составить, используя этот оператор цикла.
| Блок-схема | Программный код: var n, i, f : longint; begin write(“Введите натуральное число “); readln(n); f := 1; if n <> 0 then for i := n downto 1 do f := f*i; writeln(“Факториал числа “, n, ” равен “, f); end. |
Задачи
- Даны 10 чисел, вывести те из них, которые являются полными квадратами. Составить блок-схему и программу.
- Даны 10 чисел, найти их произведение. Составить блок-схему и программу.
- Даны 10 чисел, найти сумму четных. Составить блок-схему и программу.
- Даны 10 чисел, найти количество отрицательных. Составить блок-схему и программу.
- Даны n действительных чисел. Найти максимум и минимум. Составить блок-схему и программу.
- Даны n действительных чисел. Найти среднее арифметическое всех элементов. Составить блок-схему и программу.
- Даны n действительных чисел. Найти среднее арифметическое отрицательных и положительных элементов. Составить блок-схему и программу.
- Даны n натуральных чисел. Найти сумму и произведение элементов, кратных 3 и 5. Составить блок-схему и программу.
- Даны n натуральных чисел. Вывести те числа, значения которых являются степенями двойки (1, 2, 4, 8, 16, …). Составить блок-схему и программу.
- Даны n натуральных чисел. Вывести те числа, значения которых находятся в отрезке [a, b]. Составить блок-схему и программу.
- Даны n натуральных чисел. Вывести на экран те числа, значения которых являются квадратами какого-либо числа.Составить блок-схему и программу.
- Дано натуральное число n. Найти n2. Составить блок-схему и программу.
- Даны натуральные числа a, n. Найти an. Составить блок-схему и программу.
- Дано натуральное число n. Определить его разрядность, цифру старшего разряда числа увеличить на 2
- Дано натуральное число n. Поменять местами первую и последнюю цифры числа
- Дано натуральное число n. Цифры числа, кратные 2 заменить на 0.
- Дано натуральное число n. Цифры числа, кратные 3 заменить на 1.
- Дано натуральное число n. Вычислить произведение (2n-1)*(3n-1)*(4n-1)*…*(10n-1). Составить блок-схему и программу.
- Вычислить сумму 2+4+6+…+100. Составить блок-схему и программу.
- Дано натуральное число n, действительное x. Вычислить произведение x+x/2+x/3+…+x/n. Составить блок-схему и программу.
- Дано натуральное число n. Вычислить P=(1-1/2)(1-1/3)…(1-1/n), где n>2. Составить блок-схему и программу.
- Дано натуральное число n. Вычислить P=(1+x)/n+(2+x)/(n-1)+…+(n+x)/1. Составить блок-схему и программу.
- Даны n натуральных чисел. Вычислить сумму ряда 1+x/1!+x2/2!+x3/3!+ …+xn/n!. Составить блок-схему и программу.
Наверх
Источник