Семинар. Диаграммы Насси - Шнейдермана

Вы, конечно, знаете о графическом способе записи алгоритма решения задачи — в виде блок-схемы. Менее известен второй способ такого представления алгоритма — диаграмма Насси – Шнейдермана (ее также называют “диаграммой Нэсси – Шнейдермана”, “N – S-диаграммой” или “структурограммой”).

В своей статье “Краткая история структурных блок-схем (диаграмм Насси – Шнейдермана)” [1] один из авторов диаграммы Бен Шнейдерман пишет: “Пленительная история и эволюция структурных блок-схем (обычно называемых диаграммами Насси – Шнейдермана, или структурограммами) восходит к 1972 году”. Далее он рассказывает, что впервые подумал о создании своих способов записи алгоритмов во время посещения лекции по структурному программированию, когда еще учился в магистратуре. Ему пришло в голову, что если оператор GOTO 1 не должен использоваться, то так же не нужны и соединительные линии в старых блок-схемах. Пятнадцать минут вычерчивания привели к первым идеям по оформлению следования, ветвления и циклов. Вместе с аспирантом Исааком Насси, в то время более глубоко знавшим принципы структурного программирования, они написали статью “Технологии блок-схем для структурного программирования” [2], в которой описали свои идеи и представили новый вид графической записи алгоритмов. Статья была опубликована в августе 1973 года.

С тех пор N – S-диаграммы широко используются в ряде стран. Например, в Германии их применение при документировании программ обусловлено требованиями государственного стандарта этой страны.

Очевидные преимущества N – S-диаграмм заключаются в:

— отсутствии соединительных линий со стрелками, что помогает избежать случайных ошибок;

— компактности, т.к. даже относительно длинный алгоритм на языке N–S-диаграмм несложно разместить на одной странице;

Диаграммы Насси – Шнейдермана строятся с использованием шести элементарных “строительных блоков”.

Как известно, алгоритм состоит из последовательности действий. Блок действия используется для представления отдельного действия алгоритма:

Два действия представляют собой два блока, следующих один за другим:

Блок с разветвлением используется, когда в алгоритме возможны два варианта действий, а выбор того или иного варианта действия зависит от некоторого условия:

Такая алгоритмическая конструкция (ветвление) представляется двумя смежными блоками действий; действие слева выполняется, если условие верно, действие справа — если условие неверно. Например:

Возможно также неполное ветвление, при котором некоторое действие выполняется не всегда, а только при определенном условии:

Блок множественного выбора используется, когда существует несколько вариантов возможных действий, выбор которых зависит от значения некоторого выражения 2 :

Например, в задаче выбора разных видов обуви для разных видов спорта:

Блок цикла с предусловием используется тогда, когда должна быть многократно выполнена некоторая последовательность действий, причем перед каждым выполнением проверяется некоторое условие:

Действия, которые повторяются (так называемое “тело цикла”), представлены самостоятельным блоком внутри блока цикла с предусловием. Например, для задачи: “Накачать спущенную велосипедную шину”:

Так как условие проверяется перед выполнением тела цикла, возможно, действия не будут выполнены ни разу (если условие ложно в самом начале, вы немедленно выходите из цикла).

Цикл с заданным количеством повторений тела цикла (в языках программирования его называют “цикл с параметром” или “цикл со счетчиком” [3]) — это тоже цикл с предусловием. Действия повторяются определенное количество раз и отсчитываются перед каждым выполнением. Например, разбить в миску шесть яиц:

Подсчет действий происходит в начале. Так, если бы вы считали вслух, вы бы сказали “один” перед тем, как разбить первое яйцо.

Блок цикла с постусловием используется, когда в алгоритме действия должны повторяться до наступления определенного условия (условие проверяется после выполнения действий):

Например, в задаче приготовления теста для блинов:

Действия в цикле с постусловием всегда выполняются хотя бы один раз, потому что проверка осуществляется в конце цикла. Так, при приготовлении теста для блинов немного молока будет добавлено и размешано до того, как будет проверена консистенция теста.

Блок подпрограммы используется в случаях, когда некоторый процесс в алгоритме слишком большой, чтобы изображать его на диаграмме, или когда какие-то блоки действий используются несколько раз в разных местах одной и той же диаграммы. Например, для задачи стрижки газона около дома диаграмма алгоритма ее решения может быть оформлена так:

Диаграмма, иллюстрирующая действия в подпрограмме, оформляется отдельно.

Подпрограмма “Очистить травосборник”

Перечисленные блоки могут произвольным образом вкладываться один в другой. Проиллюстрируем сказанное на примере задачи: “Найти наименьшее число в следующей последовательности чисел: 51 25 35 79 13 26 65”.

Рассматривая приведенную последовательность чисел, вы можете увидеть, что 13 — наименьшее число в ней, но как вы это определили? Можете ли вы вывести общее правило для определения наименьшего числа в любой последовательности чисел? Есть хорошее упражнение, которое вы можете выполнить с товарищем, чтобы разобраться с этой задачей.

Напишите каждое число на карточке или маленьком кусочке бумаги. Выкладывайте карточки на стол перед вашим товарищем по одной и не забывайте забирать карточку перед тем, как выложите перед ним следующую, т.е. всякий раз ваш товарищ видит только одну карточку.

В конце попросите вашего товарища назвать наименьшее число. Затем сделайте это с любой другой последовательностью чисел. Обсудите с вашим товарищем, что он думал о каждой выложенной карте.

Разработку алгоритма решения задачи и соответствующей диаграммы будем проводить методом, известным под названием “Проектирование сверху вниз”, или “Пошаговая детализация”. Идея метода очень проста — делим всю задачу на маленькие части и затем рассматриваем каждую часть и детализируем (уточняем) ее до отдельных элементарных действий, которые можно выполнить.

Так как вам придется делать много изменений в ходе работы, стоит вооружиться карандашом, линейкой и ластиком.

1. Нулевой шаг детализации

2. Первый шаг детализации

Как вы нашли наименьшее число? Вы просмотрели всю последовательность, рассматривая каждое число и проверяя, не наименьшее ли оно. Это повторяющееся действие — значит, должен быть цикл. Какой? Так как количество повторений известно, то может быть применен цикл с параметром, в N – S-диаграммах являющийся, как указывалось выше, циклом с предусловием:

3. Второй шаг детализации

Так что же делать, чтобы понять, какое наименьшее? Детализируем внутренний блок на последней диаграмме. Вот что мы делаем, сравнивая каждое число с наименьшим, найденным до сих пор: если следующее число меньше, оно становится наименьшим, в противном случае старое остается наименьшим 3 .

4. Третий шаг детализации

Но как вы получили первое наименьшее число? Простейший способ сделать это — принять за наименьшее число первое число в последовательности чисел:

Проверим работу этого алгоритма на примере последовательности чисел: 51 25 35 79 13 26.

1. Установить в качестве наименьшего первое число последовательности (51).

2. Конец последовательности? — Нет.

3. Следующее число — 25.

5. Устанавливаем в качестве наименьшего число 25.

6. Конец последовательности? — Нет.

7. Следующее число — 35.

9. Конец последовательности? — Нет.

10. Следующее число — 79.

12. Конец последовательности? — Нет.

13. Следующее число — 13.

15. Устанавливаем в качестве наименьшего число 13.

16. Конец последовательности? — Нет.

17. Следующее число — 26.

19. Конец последовательности? Да.

Таким образом, наименьшее число в последовательности равно 13.

Разработайте диаграммы Насси – Шнейдермана для алгоритмов решения следующих задач.

1. Определить, является ли число А делителем числа В.

2. Даны три целых числа. Определить, сколько из них четных.

Примечание. Циклы не использовать.

3. В чемпионате по футболу команде за выигрыш дается 3 очка, за проигрыш — 0, за ничью — 1. Известно количество очков, полученных командой за игру. Определить словесный результат игры (выигрыш, проигрыш или ничья).

Примечание. Три блока ветвления не использовать.

4. Мастям игральных карт условно присвоены следующие порядковые номера: масти “пики” — 1, масти “трефы” — 2, масти “бубны” — 3, масти “червы” — 4. По заданному номеру масти m (1 m 4) определить название соответствующей масти.

Примечание. Блоки ветвления не использовать.

5. Найти сумму 10 заданных целых чисел.

6. Даны n целых чисел. Определить, сколько из них четных.

7. Известен рост каждого из 20 учеников класса. Рост мальчиков условно задан отрицательными числами. Определить средний рост мальчиков и средний рост девочек.

8. Дано целое число. Если оно положительное, то вычислить средний рост девочек (см. задачу 7), в противном случае вычислить средний рост мальчиков.

9. В задаче 7 выяснить, верно ли, что средний рост мальчиков превышает средний рост девочек более чем на 10 см.

1. Ben Shneiderman. A short history of structured flowcharts (Nassi-Shneiderman Diagrams). / Draft, May 27, 2003.

2. Nassi I., Shneiderman B. Flowchart Techniques for Structured Programming. / SIGPLAN Notices 8, 8 (August, 1973).

3. Школа программирования: тематический выпуск газеты “В мир информатики”. / “Информатика”, 2005, № 11.

От редакции. Разработанные диаграммы, пожалуйста, присылайте в редакцию. Фамилии всех приславших будут опубликованы, а лучшие ответы мы поощрим.

1 Оператор, использовавшийся в первых языках программирования высокого уровня, при выполнении которого управление передавалось в другое место программы, отмеченное так называемой “меткой”. — Ред.

2 Фрагмент “Иначе” и соответствующий ему фрагмент “Действие n + 1” в блоке может отсутствовать. — Ред.

3 Т.е. здесь может быть применен неполный вариант блока ветвления (см. выше). — Ред.