Пример 1. Стеки

1) Предметная область "Формирование железнодорожного состава".

2) Профессиональная деятельность в этой предметной области состоит в решении задач формирования уходящих с некоторой станции железнодорожных составов. Пунктом назначения разных вагонов каждого уходящего состава являются пункт А или пункт В. Состав должен быть сформирован так, чтобы все вагоны, которые требуется доставить в один и тот же пункт, образовывали непрерывную последовательность вагонов, тогда по прибытии в пункт назначения достаточно отсоединить нужные вагоны не переформировывая состав. При формировании состава используются вагоны пришедшего на станцию состава, причем про каждый вагон известно, каков его пункт назначения. Вагоны к пришедшему составу присоединялись на станциях и остановочных пунктах, через которые проходил поезд. Поэтому вагоны с одним и тем же пунктом назначения располагаются в пришедшем поезде не подряд. Будем считать, что при решении каждой задачи используется только один пришедший состав и формируется только один уходящий состав. При сортировке используется три тупика. Пришедший состав стоит в первом тупике. Во второй тупик ставят вагоны, пункт назначения которых А. В третий тупик ставят вагоны, пункт назначения которых В. После окончания сортировки вагоны из второго тупика добавляют к последовательности вагонов первого тупика.

3) В предметной области решаются задачи одного класса. Приведем постановку задач данного класса.

Дано: пришедший состав, состоящий из вагонов.

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

4) В данной предметной области используются следующие замкнутые системы объектов: замкнутая система разреженных множеств, конечные отображения, замкнутая система стеков, замкнутая система скалярных значений, замкнутая система безразмерных значений, замкнутая система структурных значений.

5) Систему понятий предметной области образуют следующие понятия: "вагоны", "пункт назначения", составы, "пришедший состав", "уходящий состав", процесс сортировки". Объем понятия "вагоны" состоит из конечных подмножеств множества всех вагонов, т.е. это понятие соответствует разреженным множествам. Понятия "пункт назначения" и "процесс сортировки" соответствуют конечным отображениям. Конечное отображение, которому соответствует понятие "пункт назначения", отображает вагон в некоторый элемент конечного множества, элементами которого являются скалярные значения "А" и "В". Конечное отображение, которому соответствует понятие "процесс сортировки", отображает элемент безразмерной величины в некоторый элемент замкнутой системы структурных значений, каждое структурное значение состоит из четырех компонент. Компонентами являются элементы замкнутой системы стеков.

6) Прикладная логическая теория имеет название "Сортировка вагонов". При ее построении используются стандартное расширение ST и специализированное расширение "Последовательности". Запишем теорию на языке прикладной логики.

Формирование составов(ST, Последовательности)

6.1) сорт вагоны: {}N

моделью объема понятия, обозначенного термином "вагоны" является бесконечное множество конечных подмножеств бесконечного множества обозначений

6.2) сорт пункт назначения: (вагоны ® {А, В})

моделью объема понятия, обозначенного термином "пункт назначения" является множество конечных отображений, областью определения каждого отображения является значение термина "вагоны", а областью значений - конечное множество названий пунктов назначения

6.3) составы º seq вагоны

моделью объема понятия, обозначенного термином "составы", является бесконечное множество конечных последовательностей, элементы каждой последовательности принадлежат значению термина "вагоны"

6.4) сорт пришедший состав: составы

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

6.5) сорт уходящий состав: составы

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

6.6) n º length(пришедший состав)

значением термина "n" является значение длины пришедшего состава

6.7) сорт процесс сортировки: (I[0,n] ® (составы Ý 3))

объемом понятия, обозначенного термином "процесс сортировки", является множество конечных отображений; областью определения каждого отображения является множество целых чисел, не меньших 0 и не больших значения термина "n", а областью значений - множество структурных значений; элементы каждого структурного значения принадлежат множеству последовательностей, обозначенных термином "составы"

6.8) p(1, процесс сортировки(0)) = пришедший состав

6.9) p(2, процесс сортировки(0)) = L

6.10) p(3, процесс сортировки(0)) = L

на первом шаге сортировки в первом тупике находятся пришедший состав, второй и третий тупики пусты

6.11) уходящий состав = p(2, процесс сортировки(n)) || p(3, процесс сортировки(n))

уходящий состав формируется из вагонов второго и третьего тупиков, полученных на последнем шаге сортировки

6.12) (v: I[1,n]) пункт назначения(last(p(1, процесс сортировки(v-1))) = A Þ p(2, процесс сортировки(v)) = addend(p(2, процесс сортировки(v-1)), last(p(1, процесс сортировки(v-1))) & p(3, процесс сортировки(v)) = p(3, процесс сортировки(v-1))

если пункт назначения первого вагона первого тупика совпадает с пунктом А, тогда этот вагон записывается в начало второго тупика, в третий тупик вагоны не добавляются

6.13) (v: I[1,n]) пункт назначения(last(p(1, процесс сортировки(v-1))) = B Þ p(3, процесс сортировки(v)) = addend(p(3, процесс сортировки(v-1)), last(p(1, процесс сортировки(v-1))) & p(2, процесс сортировки(v)) = p(2, процесс сортировки(v-1))

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

6.14) (v: I[1,n]) p(1, процесс сортировки(v)) = head(p(1, процесс сортировки(v-1)))

на каждом шаге процесса формирования из первого тупика забирается первый вагон

7) Запишем программу на алгоритмическом языке программирования Паскаль.

program сортировка_вагонов;

type составы = ^ вагон;

вагон = record

номер вагона: integer;

пункт_назначения: char;

следующий: составы;

предыдущий: составы;

end;

var начало_уходящего, конец_уходящего,

начало_пришедшего, конец_пришедшего: составы;

текущий_вагон: составы;

все_вагоны: byte;

i, n: integer;

процесс_сортировки: record

конец_первого: составы;

конец_второго: составы;

конец_третьего: составы;

end;

function head(конец_состава: составы): составы;

begin

head:= конец_состава.предыдущий;

head^.следующий:= nil;

end;

procedure addend(var конец_состава: составы; добавляемый: составы);

begin

добавляемый.предыдущий:= конец_состава;

конец_состава:= добавляемый;

конец_состава.следующий:= nil;

end;

begin

{ ввод информации о пришедшем составе }

writeln('введите информацию о вагонах пришедшего состава');

все_вагоны:= 2; n:= 0;

конец_пришедшего:=nil;

начало_пришедшего:=nil;

while все_вагоны = 2 do

begin

write('номер вагона и пункт назначения:');

new(текущий_вагон);

with текущий_вагон^ do

begin

readln(номер вагона, пункт_назначения);

следующий:=nil;

предыдущий:=nil;

end;

addend(конец_пришедшего, текущий_вагон);

n:= n+1;

writeln('все вагоны? 1 – да, 2 – нет ');

readln(все_вагоны);

end;

процесс_сортировки.конец_первого:= конец_пришедшего;

процесс_сортировки.конец_второго:= nil;

процесс_сортировки.конец_третьего:= nil;

for i:=1 to n do

if процесс_сортировки.конец_первого.пункт_назначения = 'A'

then

begin

текущий_вагон:= процесс_сортировки.конец_первого;

процесс_сортировки.конец_первого:=

head(процесс_сортировки.конец_первого);

addend(процесс_сортировки.конец_второго,

текущий_вагон);

end

else

if процесс_сортировки.конец_первого.пункт_назначения = 'B'

then

begin

текущий_вагон:= процесс_сортировки.конец_первого;

процесс_сортировки.конец_первого:=

head(процесс_сортировки.конец_первого);

addend(процесс_сортировки.конец_третьего,

текущий_вагон);

end;

начало_уходящего:= процесс_сортировки.конец_второго;

{объединяем две последовательности}

{ так как обе моделируются стеком, то адрес начала не хранится}

текущий_вагон:= начало_уходящего;

while текущий_вагон <> nil do

begin

конец_уходящего:= текущий_вагон;

текущий_вагон:= текущий_вагон^.следующий;

end;

конец_уходящего^.следующий:= процесс_сортировки.конец_третьего;