Задачи на алгоритм цикл и блок схема для них
Цель: изучение алгоритмической структуры циклы, создание моделей и алгоритмов для решения практических задач.
Ход урока
I. Актуализация знаний
- Повторить понятие алгоритма, основные конструкции алгоритмического языка.
- Уметь разрабатывать математическую модель, алгоритм и блок схему решения задачи.
- Иметь понятие о языках программирования и их назначении.
- Уметь работать в среде программирования.
- Знать структуры программы.
- Уметь записывать выражения, содержащие числовые и символьные величины.
- Знать структуры операторов и особенности их работы.
- Уметь применять операторы при написании программ с линейными и ветвящимися структурами.
- Уметь на компьютере создавать и запускать программы на отладку.
II. Теоретический материал урока
Большинство практических задач требует многократного повторения одних и тех же действий, т. е. повторного использования одного или нескольких операторов. (Презентация)
Пусть требуется ввести и обработать последовательность чисел. Если чисел всего пять, можно составить линейный алгоритм. Если их тысяча, записать линейный алгоритм можно, но очень утомительно и нерационально. Если количество чисел к моменту разработки алгоритма неизвестно, то линейный алгоритм принципиально невозможен.
Другой пример. Чтобы найти фамилию человека в списке, надо проверить первую фамилию списка, затем вторую, третью и т.д. до тех пор, пока не будет найдена нужная или не будет достигнут конец списка. Преодолеть подобные трудности можно с помощью циклов.
Циклом называется многократно исполняемый участок алгоритма (программы). Соответственно циклический алгоритм – это алгоритм, содержащий циклы.
Различают два типа циклов: с известным числом повторений и с неизвестным числом повторений. При этом в обоих случаях имеется в виду число повторений на стадии разработки алгоритма.
Существует 3 типа циклических структур:
- Цикл с предусловием;
- Цикл с послеусловием;
- Цикл с параметром;
Иначе данные структуры называют циклами типа «Пока», «До», «Для».
Графическая форма записи данных алгоритмических структур:
Цикл с предусловием (иначе цикл пока) имеет вид:
| Форматы записи операторов алгоритма | Блок-схема | Форматы записи операторов на Паскале |
| Пока (условие) нц серия команд кц | while условие do begin серия команд; end; |
где
условие – выражение логического типа.
Цикл может не выполняться ни разу, если значение логического выражения сразу же оказывается ложь.
Серия команд, находящихся между begin и end, выполняются до тех пор, пока условие истинно.
Для того чтобы цикл завершился, необходимо, чтобы последовательность инструкций между BEGIN и END изменяла значение переменных, входящих в условие.
Цикл с постусловием (иначе цикл до) имеет вид:
| Форматы записи операторов алгоритма | Блок-схема | Форматы записи операторов на Паскале |
| В алгоритмическом языке нет команды которая могла бы описать данную структуру, но ее можно выразить с помощью других команд (Например, ветвления). | repeat серия команд until условие |
где
условие – выражение логического типа.
Обратите внимание:
Последовательность инструкций между repeat и until всегда будет выполнено хотя бы один раз;
Для того чтобы цикл завершился, необходимо, чтобы последовательность операторов между repeat и until изменяла значения переменных, входящих в выражение условие.
Инструкция repeat, как и инструкция while, используется в программе, если надо провести некоторые повторяющиеся вычисления (цикл), однако число повторов заранее не известно и определяется самим ходом вычисления.
Цикл с параметром (иначе цикл для) имеет вид:
| Форматы записи операторов алгоритма | Блок-схема | Форматы записи операторов на Паскале |
| Для i от а до b шаг h делай Нц Серия команд кц | h = +1 for i:= a to b do begin серия команд end; h = -1 for i:= b downto a do begin Cерия команд; end; |
где
i – параметр цикла;
a – начальное значение цикла;
b – конечное значение цикла;
h – шаг изменения параметра.
Структура данного цикла иначе называют циклом i раз.
Эта команда выполняется таким образом: параметру i присваивается начальное значение а, сравнивается с конечным значением b и, если оно меньше или равно конечному значению b, выполняется серия команд. Параметру присваивается значение предыдущего, увеличенного на величину h – шага изменения параметра и вновь сравнивается с конечным значением b.
На языке программирования Паскаль шаг изменения параметра может быть равным одному или минус одному.
Если между begin и end находится только один оператор, то операторные скобки можно не писать. Это правило работает для цикла типа «Пока» и «Для».
Рассмотрим пример решения задач с использованием данных структур
Пример.
Вычислить произведение чисел от 1 до 5 используя различные варианты цикла
Математическая модель:
Р= 1· 2· 3· 4· 5=120
Составим алгоритм в виде блок-схемы.
Для проверки правильности алгоритма заполним трассировочную таблицу.
| Шаг | Операция | Р | i | Проверка условия |
| 1 | P:=1 | 1 | ||
| 2 | i:=1; | 1 | 1 | |
| 3 | i<=5 P:=P*I i:=i+1 | 1 | 1 | 1<=5, да (истина) |
| 4 | i<=5 P:=P*I i:=i+1 | 2 | 2 | 2<=5, да (истина) |
| 5 | i<=5 P:=P*I i:=i+1 | 6 | 3 | 3<=5, да (истина) |
| 6 | i<=5 P:=P*I i:=i+1 | 24 | 4 | 4<=5, да (истина) |
| 7 | i<=5 P:=P*I i:=i+1 | 120 | 5 | 5<=5, да (истина) |
| 8 | i<=5 P:=P*I i:=i+1 | 6<=5, нет (ложь) |
Проверка условия происходит в несколько шагов: проверка условия и выполнение команд на одной из ветвей. Поэтому в трассировочной таблице записываются не команды алгоритма, а отдельные операции, выполняемые компьютером на каждом шаге.
Шаг первый: Р присваивается значение один.
Шаг второй: i присваивается значение один.
Шаг третий: при i равном единице проверяем условие один меньше или равен пяти, да, условие истинно, значит Р присваивается значение один умноженное на один, будет два. Для i: один плюс один, будет два.
Шаг четвертый: при i равном двум проверяем условие два меньше или равен пяти, да, условие истинно, значит Р присваивается значение 2 умноженное на один, будет 2. Для i: два плюс один, будет три.
Шаг пятый: при i равном трем проверяем условие три меньше или равен пяти, да, условие истинно, значит Р присваивается значение два умноженное на три, будет шесть. Для i: три плюс один, будет четыре.
Шаг шестой: при i равном четырем проверяем условие четыре меньше или равен пяти, да, условие истинно, значит Р присваивается значение шесть умноженное на четыре, будет двадцать четыре. Для i: четыре плюс один, будет пять.
Шаг седьмой: при i равном пяти проверяем условие пять меньше или равен пяти, да ,условие истинно, значит Р присваивается значение двадцать четыре умноженное на пять, будет сто двадцать. Для i: пять плюс один, будет шесть.
Шаг восьмой: при i равном шести проверяем условие шесть меньше или равен пяти, нет, условие ложно, тогда мы выходим из цикла, а в результате получаем последнее значение равное сто двадцати.
Program Pr1;
Var i: integer;
Begin
P:=1;
i:=1;
While i<=5 do
begin
P:=P*i;
i:=i+1;
end;
Write (‘P=’, P);
end.
Для цикла с постусловием построим блок-схему и трассировочную таблицу. (слайд16)
В результате получаем последнее значение равное сто двадцати на седьмом шаге
И для Цикла с параметром построим блок-схему и трассировочную таблицу. (слайд17)
В результате получаем последнее значение равное сто двадцати на шестом шаге
Задача:
Вывести на экран числа от 1 до 5 в:
- прямом порядке;
- обратном порядке.
Математическая модель:
- 1 2 3 4 5;
- 5 4 3 2 1.
Блок-схема и программа решения задачи представлена для чисел в прямом порядке и обратном порядке.
(слайд 21)
Запишем рассмотренные алгоритмы на языке программирования Паскаль.
(слайд 22)
III. Подведение итогов урока
И так мы рассмотрели следующие вопросы:
- Алгоритмическая структура цикл;
- Виды алгоритмических структур:
- Цикл с предусловием;
- Цикл с послеусловием;
- Цикл с параметром;
- Рассмотрели способы записи данных структур;
- Разобрали примеры решения задач с помощью этих структур.
Источник
Цели: Освоить технологию:
ОглавлениеЗадание 1. Пошаговое выполнение алгоритма Условие Задание 2. Пошаговое выполнение циклического алгоритма Задание 3. Составление блок-схемы алгоритма Задание 4. Составление блок-схемы условного алгоритма Задание 1. Пошаговое выполнение алгоритма Условие
Задание 2. Пошаговое выполнение циклического алгоритма
Рис. 1. Блок-схема 1
1 шаг А=11; В=14; I =1 2 шаг С=25 3 шаг – Проверка условия. С=<100, выбирается ветка Нет. 4 шаг – I = 2 5 шаг – А=22; В=28;
Значения переменных после окончания выполнения алгоритма: I=3; A=44; B=56. Задание 3. Составление блок-схемы алгоритмаСоставьте блок-схему циклического алгоритма, который заданное число раз вычисляет значения выражения: М= I *(D + K)/(D – K). Предусмотрите допустимые условия выполнения алгоритма. Заданы следующие данные:
Рис. 2. Блок-схема циклического алгоритма Задание 4. Составление блок-схемы условного алгоритма
Рассчитать стоимость покупки (SP). Вводится информация о цене товара (переменная С) и о количестве единиц товара (переменная К) покупки. На стоимость покупки назначается скидка в зависимости от количества закупленных единиц товара:
Рис. 3. Вложенные условия |
Источник
Схема – это абстракция какого-либо процесса или системы, наглядно отображающая наиболее значимые части. Схемы широко применяются с древних времен до настоящего времени – чертежи древних пирамид, карты земель, принципиальные электрические схемы. Очевидно, древние мореплаватели хотели обмениваться картами и поэтому выработали единую систему обозначений и правил их выполнения. Аналогичные соглашения выработаны для изображения схем-алгоритмов и закреплены ГОСТ и международными стандартами.
На территории Российской Федерации действует единая система программной документации (ЕСПД), частью которой является Государственный стандарт – ГОСТ 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 с. ил.
Источник