 |
Диаграмма Насси-Шнейдермана (структурограммы)
|
|
|
|
Утверждаю
Ректор университета
__________________А.В. Лагерев
«____»____________2012 г.
ПРОГРАММИРОВАНИЕ
Способы записи алгоритмов
Методические указания
к выполнению лабораторной работы №1
для студентов очной формы обучения специальности 010500 «Математическое обеспечение и администрирование информационных систем»
Брянск 2012
УДК 004.421+004.43
Программирование. Способы записи алгоритмов [текст]+[электронный ресурс]: методические указания к выполнению лабораторной работы №1 для студентов очной формы обучения специальности 010500 «Математическое обеспечение и администрирование информационных систем». – Брянск: БГТУ, 2012. – 17 с. – Режим доступа: http://www.elibrary.ru.
Разработали:
Д.И.Булатицкий
доц.
Рекомендовано кафедрой «Информатика и программное обеспечение» БГТУ (протокол №4 от 15.02.10)
В этой ЛР студенты знакомятся с понятием алгоритма, его свойствами и способами записи. Формируются навыки записи алгоритмов в виде блок-схем и диаграмм Насси — Шнейдермана.
ЦЕЛЬ РАБОТЫ
Цель работы – изучить основные способы записи алгоритмов. Для этого студент должен:
· изучить понятие алгоритма и исполнителя;
· изучить условные обозначения в блок-схемах;
· изучить условные обозначения в структурограммах;
Продолжительность работы – 2 часа.
ТЕОРЕТИЧЕСКАЯ ЧАСТЬ
Понятие алгоритма
Алгоритм – последовательность чётко определенных действий, выполнение которых ведёт к решению задачи. Алгоритм, записанный на языке машины, есть программа решения задачи.
Алгоритм – это совокупность действий, приводящих к достижению результата за конечное число шагов.
|
|
|
Свойства алгоритмов:
1. Дискретность – это разбиение алгоритма на ряд отдельных законченных действий (шагов).
2. Детерминированность (от лат. determinate — определенность, точность) - любое действие алгоритма должно быть строго и недвусмысленно определено в каждом случае.
3. Конечность – каждое действие в отдельности и алгоритм в целом должны иметь возможность завершения.
4. Массовость – алгоритм должен быть применим к разным наборам исходных данных.
5. Результативность – алгоритм должен приводить к достоверному решению.
Примерами алгоритмов могут являться:
· Кулинарный рецепт;
· Инструкция к прибору;
· Описание маршрута и др.
Различают три основных вида алгоритмов:
· линейный алгоритм,
· разветвляющийся алгоритм,
· циклический алгоритм.
Линейный алгоритм – это алгоритм, в котором действия выполняются однократно и строго последовательно.
Примером линейного алгоритма может являться последовательность действий при приготовлении бутерброда. Алгоритм в этом случае будет выглядеть следующим образом:
1. начало
2. отрезать хлеб;
3. намазать хлеб маслом;
4. отрезать колбасу;
5. положить колбасу на хлеб;
6. конец.
Все действия выполняются последовательно друг за другом в определенном порядке и приводят к конечному результату.
Разветвляющийся алгоритм – это алгоритм, в котором в зависимости от условия выполняется либо одна, либо другая последовательность действий.
Самый простой пример реализации разветвляющегося алгоритма – если на улице идет дождь, то необходимо взять зонт, иначе не брать зонт с собой.
Циклический алгоритм – это алгоритм, команды которого повторяются некое количество раз подряд.
Самый простой пример реализации циклического алгоритма – при чтении книги будут повторяться одни и те же действия: прочитать страницу, перелистнуть и т.д.
Циклические алгоритмы трех видов:
· цикл со счетчиком – действия внутри цикла выполняются определенное количество раз;
|
|
|
· цикл с предусловием – перед каждым новым проходом цикла проверяется определенное условие, если оно истинно, действия внутри цикла выполняются, в противном случае происходит выход из цикла;
· цикл с постусловием – в начале происходит выполнение действий внутри цикла, а только затем проверка условия.
Формы записи алгоритма:
· словесная или вербальная (языковая, формульно-словесная);
· псевдокод (формальные алгоритмические языки);
· схематическая:
o структурограммы (схемы Насси-Шнайдермана);
o графическая (блок-схемы).
Обычно сначала (на уровне идеи) алгоритм описывается словами, но по мере приближения к реализации он обретает всё более формальные очертания и формулировку на языке, понятном исполнителю (например, машинный код).
Пример словестной записи алгоритма приведен ранее при рассмотрении линейного алгоритма. Примером записи алгоритма с помощью псевдокода является код любой программы на любом языке программирования (С++, Pascal, Basic и др.).
Способы схематической записи алгоритмов подробно рассматриваются далее.
Блок-схемы
Правила выполнения схем определяются следующими документами:
· ГОСТ 19.701-90. Схемы алгоритмов, программ, данных и систем. Условные обозначения и правила выполнения.
Данные документы в частности регулируют способы построения схем и внешний вид их элементов.
Основные элементы схем алгоритма
| Наименование | Обозначение | Функция |
| Блок начало-конец (пуск-остановка) | 
| Элемент отображает вход из внешней среды или выход из неё (наиболее частое применение − начало и конец программы). Внутри фигуры записывается соответствующее действие. |
| Блок вычислений (вычислительный блок) | 
| Выполнение одной или нескольких операций, обработка данных любого вида (изменение значения данных, формы представления, расположения). Внутри фигуры записывают непосредственно сами операции, например, операцию присваивания: a = 10*b + c. |
| Логический блок (блок условия) | 
| Отображает решение или функцию переключательного типа с одним входом и двумя или более альтернативными выходами, из которых только один может быть выбран после вычисления условий, определенных внутри этого элемента. Вход в элемент обозначается линией, входящей обычно в верхнюю вершину элемента. Если выходов два или три, то обычно каждый выход обозначается линией, выходящей из оставшихся вершин (боковых и нижней). Примеры решения: в общем случае − сравнение (три выхода: >, <, =); в программировании − условные операторы if (два выхода: true, false) и case (множество выходов). |
| Предопределённый процесс | 
| Символ отображает выполнение процесса, состоящего из одной или нескольких операций, который определен в другом месте программы (в подпрограмме, модуле). Внутри символа записывается название процесса и передаваемые в него данные. Например, в программировании − вызов процедуры или функции. |
| Данные (ввод-вывод) | 
| Преобразование данных в форму, пригодную для обработки (ввод) или отображения результатов обработки (вывод). Данный символ не определяет носителя данных (для указания типа носителя данных используются специфические символы). |
| Граница цикла | 
| Символ состоит из двух частей − соответственно, начало и конец цикла − операции, выполняемые внутри цикла, размещаются между ними. Условия цикла и приращения записываются внутри символа начала или конца цикла − в зависимости от типа организации цикла. Часто для изображения на блок-схеме цикла вместо данного символа используют символ условия, указывая в нём решение, а одну из линий выхода замыкают выше в блок-схеме (перед операциями цикла). |
| Соединитель | 
| Символ отображает вход в часть схемы и выход из другой части этой схемы. Используется для обрыва линии и продолжения её в другом месте (для избежания излишних пересечений или слишком длинных линий, а также, если схема состоит из нескольких страниц). Соответствующие соединительные символы должны иметь одинаковое (при том уникальное) обозначение. |
| Комментарий | 
| Используется для более подробного описания шага, процесса или группы процессов. Описание помещается со стороны квадратной скобки и охватывается ей по всей высоте. Пунктирная линия идет к описываемому элементу, либо группе элементов. Также символ комментария следует использовать в тех случаях, когда объём текста, помещаемого внутри некоего символа, превышает размер самого этого символа. |
|
|
|
|
|
|
Описание других элементов схем можно найти в соответствующих ГОСТ (указаны выше).
Рассмотрим пример построения блок-схемы алгоритма решения полного квадратного уравнения 
. Для начала запишем алгоритм в вербальной форме:
1. Начало;
2. Ввод А;
3. Ввод В;
4. Ввод С;
5. Вывод уравнения на экран;
6. Вычисление дискриминанта по формуле 
;
7. Если 
вывести сообщение об отсутствии корней и перейти к шагу 10, иначе перейти к шагу 8;
8. Если 
, единственный корень уравнения вычислить по формуле 
, вывести его на экран и перейти к шагу 10. В противном случае перейти к шагу 9.
9. Вычислить корни уравнения по формулам
вывести результаты на экран, перейти к шагу 10.
10. Конец.
При построении блок-схемы будут использоваться следующие элементы:
1. Начало и конец -
2. Ввод и вывод данных -
3. Вычисление -
4. Условие -
Последовательность действий задается управляющими стрелками, связывающими блоки, внутри графических элементов записывается соответствующая команда.
Блок схема алгоритма приведена на Рис. 1.
Рис.1. Блок-схема алгоритма вычисления корней квадратного уравнения
Далее рассматривается другой способ графической записи алгоритма – при помощи диаграммы Насси-Шнейдермана.
Диаграмма Насси-Шнейдермана (структурограммы)
Диаграмма Насси-Шнейдермана – это графический способ представления структурированных алгоритмов и программ, разработанный в 1972 году американскими аспирантами Беном Шнейдерманом и Айзеком Насси.
Диаграммы Насси-Шнейдермана имеют ряд преимуществ перед блок-схемами при разработке структурированных алгоритмов и программ:
· Запись является более компактной (в первую очередь за счёт отсутствия стрелок между элементами).
· Гарантированное соблюдение принципов структурного программирования соблюдены (при использовании блок-схем можно случайно получить неструктурированный алгоритм, если быть невнимательным).
· Диаграммы Насси — Шнейдермана удобнее использовать для пошаговой детализации задачи, так как они тоже строятся по принципу пошаговой детализации — изначально диаграмма представляет собой один прямоугольник (исходная задача), затем в нём рисуется некоторая структура управления, в которой имеется несколько прямоугольников (подзадач исходной задачи), и далее с каждым прямоугольником (подзадачей) может быть проделана та же операция.
|
|
|
