Диаграмма Насси — Шнейдермана - это графический способ представления структурированных алгоритмов и программ, разработанный в 1972 году американскими аспирантами Беном Шнейдерманом и Айзеком Насси.
Поскольку в структурном программировании не используется безусловный переход, то Бен Шнейдерман решил, что для записи структурированных алгоритмов не нужны используемые в блок-схемах стрелки. Придумав разные способы изображения основных структур управления (последовательностей, ветвлений и циклов), он затем вместе с Айзеком Насси подробно проработал свою идею. Вместе они написали статью «Техника блок-схем для структурного программирования», которая была опубликована в научном журнале «SIGPLAN Notices» в августе 1973 года.
Диаграммы Насси — Шнейдермана получили широкое распространение в некоторых странах, особенно в Германии, где для них даже был разработан официальный стандарт Немецким институтом по стандартизации: DIN 66261.
Диаграммы Насси — Шнейдермана имеют ряд преимуществ перед блок-схемами при разработке структурированных алгоритмов и программ:
1 Запись является более компактной (в первую очередь за счёт отсутствия стрелок между элементами).
2 Изобразив алгоритм или программу в виде диаграммы Насси — Шнейдермана, можно быть гарантировано уверенным в том, что принципы структурного программирования соблюдены (при использовании блок-схем можно случайно получить неструктурированный алгоритм, если быть невнимательным).
3 Диаграммы Насси — Шнейдермана удобнее использовать для пошаговой детализации задачи, так как они тоже строятся по принципу пошаговой детализации — изначально диаграмма представляет собой один прямоугольник (исходная задача), затем в нём рисуется некоторая структура управления, в которой имеется несколько прямоугольников (подзадач исходной задачи), и далее с каждым прямоугольником (подзадачей) может быть проделана та же операция.
Описание алгоритма Дейкстры в диаграмме Насси-Шнейдермана представлено в приложении Б стр. 25
ПРОГРАММНАЯ РЕАЛИЗАЦИЯ
5.1 Описание структуры программы
Программа выводит минимальный путь между двумя указанными вершинами в графе и его длину.
При запуске программы на экран выводится запрос о вводе начальной и конечной вершин графа. В случае, если начальная и конечная вершины совпадают, отображается соответствующее сообщение и работа программы завершается. В противном случае выполняется непосредственно алгоритм Дейкстры, схема которого приведена в приложении В.
Результатом программы является вывод на экран вершин, через которые проходит минимальный путь, а также вывод длины маршрута. Если пути между заданными точками не существует – выводится соответствующее сообщение.
Алгоритм использует три массива из N (= числу вершин сети) чисел каждый. Первый массив A содержит метки с двумя значения: 0 (вершина еще не рассмотрена) и 1 (вершина уже рассмотрена); второй массив B содержит расстояния - текущие кратчайшие рас- стояния от до соответствующей вершины; третий массив с содержит номера вершин - k-й элемент С[k] есть номер предпоследней вершины на текущем кратчайшем пути из Vi в Vk. Матрица расстояний D[i,k] задает длины дуге D[i,k]; если такой дуги нет, то D[i,k] присваивается большое число Б, равное "машинной бесконечности".
5.2 Описание использованных программных средств
Таблица 5.2.1–Описание переменных
| Переменная | Тип | Описание |
| n | int | Количество точек (вершин) грифа |
| i,j | int | Счётчики |
| k | int | Номер кратчайшего пути и наименьшей длины пути |
| start | int | Номер начальной точки (вершины) |
| finish | int | Номер конечной точки (вершины) |
| A[i] | boolean | Массив, i-й элемент которого имеет значение false, когда i-й путь и расстояние временные, и принимает значение true, когда i-й путь и расстояние становятся постоянными |
| D[i,j] | int | Массив i-j элемент которого содержит расстояние между i-й и j-й точками (вершинами) Замечание: 1. D[i][i]=0 2. D[i,j]=D[j,i] |
| C[i] | int | Массив,который содержит номера вершин |
| path[80][11] | char | Массив строк, который содержит пути Замечание: После прохождения обработки по алгоритму Дейкстры p-й элемент массива содержит кратчайший путь. |
ИНСТРУКЦИЯ ПОЛЬЗОВАТЕЛЯ
При запуске программы на экране появится окно с инструкциями. Выполняйте эти инструкции, а именно:
1. Введите номер начальной вершины.
2. Введите номер конечной вершины. На экран выводится матрица смежности, прочтенная из текстового файла
3. Чтоб завершить работу программы после получения результата нажмите Enter.
ЗАКЛЮЧЕНИЕ
Таким образом, в процессе создания данного проекта разработана программа, реализующая алгоритм Дейкстры в Turbo Pascal. Её недостатком является примитивный пользовательский интерфейс. Это связано с тем, что программа работает в консольном режиме, не добавляющем к сложности языка сложность программного оконного интерфейса
Также были углублены знания, полученные в процессе выполнения лабораторных работ по предмету «Программирование».
ЛИТЕРАТУРА
1. Е. А. Зуев. Программирование на языке Turbo Pascal 6.0, 7.0, М.:Веста,Радио и связь, 1993, — С.376
2. Кассера В. Ф. Turbo Pascal 7.0, Диасофт, 2003
3. Эллиот Б. Коффман. Turbo Pascal = Turbo Pascal Web Update — М.: Вильямс, 2005. — С. 896.
4. Моргун Александр Николаевич. Справочник по Turbo Pascal для студентов — М.: Диалектика, 2006. — С. 608
5. Нэйл Рубенкинг. Turbo Pascal для Windows = Turbo Pascal for Windows. Techniques and Utilites — М.: Мир, 1993. — С. 535.
6. Фаронов В. В. Turbo Pascal. Наиболее полное руководство. BHV-Санкт-Петербург, 2007
Приложение А
Текст программы
Program Alg_dejkstr;
Uses Crt;
Const MaxSize=8;
n=8;
Infinity=1000;
Var D: array [1..MaxSize, 1..MaxSize] of integer;
A: array [1..MaxSize] of boolean;
B,C: array [1..MaxSize] of integer;
Start, Finish, k, i: integer;
Procedure Init;
Var f: text;
i, j: integer;
Begin
Assign(f, 'INPUT.MTR');
Reset(f);
For i:=1 to n do
Begin
For j:=1 to n do
Read(f, D[i,j])
End;
For i:=1 to n do
begin
For j:=1 to n do
write(d[i,j]);
writeln
end;
Write('начальная вершина: '); Readln(Start);
For i:=1 to n do
Begin
A[i]:=False;
B[i]:=D[Start, i];
C[i]:=Start
End;
C[Start]:=0;
A[Start]:=True
End;
Function Possible: Boolean;
Var i: integer;
Begin
Possible:=True;
For i:=1 to n do If not A[i] then Exit;
Possible:=False
End;
Function Min: Integer;
Var i, minvalue, currentmin: integer;
Begin
Minvalue:=Infinity;
For i:=1 to n do
If not A[i] then
If B[i]<minvalue then
Begin
currentmin:=i;
minvalue:=B[i]
End;
min:=currentmin
End;
Begin
ClrScr;
Init;
While Possible do
Begin
k:=min;
A[k]:=True;
For i:=1 to n do
If B[i]>B[k]+D[i, k] then
Begin
B[i]:=B[k]+D[i, k];
C[i]:=k
End
End;
Write('конечная вершина: '); Readln(Finish);
Write(Finish);
Finish:=C[Finish];
While Finish<>0 do
Begin
Write('<-', Finish);
Finish:=C[Finish];
End;
ReadKey
End.
Массив расстояний, прочитанный из текстового файла имеет вид:
0 23 12 1000 1000 1000 1000 1000
23 0 25 1000 22 1000 1000 35
12 25 0 18 1000 1000 1000 1000
1000 1000 18 0 1000 20 1000 1000
1000 22 1000 1000 0 23 14 1000
1000 1000 1000 20 2 3 0 24 1000
1000 1000 1000 1000 14 24 0 16
1000 35 1000 1000 1000 1000 16 0
Приложение Б
Приложение В