ОАФИ-Метод.указ-версия для студентов
.pdf31
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) (1, процесс сортировки(0)) = пришедший состав
6.9) (2, процесс сортировки(0)) = на первом шаге сортировки в тупике находится пришедший состав, а двухсторонний путь пуст
6.10) уходящий состав = (2, процесс сортировки(n))
уходящий состав – это состав, полученный на двухстороннем пути в результате процесса сортировки
6.12) (v: I[1,n]) процесс сортировки(v) = <head( (1, процесс сортировки(v-1))), / (пункт назначения(last( (1, процесс сортировки(v-1))) = A addend( (3, процесс сортировки(v-1)), last( (1, процесс сортировки(v-1))))) (пункт назначения(last( (1, процесс сортировки(v-1))) = B addbeg( (3, процесс сортировки(v-1)), last( (1, процесс сортировки(v-1))))/>
32
7) Запишем программу на алгоритмическом языке программирования Паскаль.
program сортировка_вагонов; type составы = ^ вагоны;
вагоны = record
номер вагона: integer; пункт_назначения: char; следующий: составы; предыдущий: составы;
end;
var начало_уходящего: составы, конец_уходящего: составы, начало_пришедшего: составы; конец_пришедшего: составы; текущий_вагон: составы; все_вагоны: byte; процесс_сортировки: record
конец_первого: составы; начало_второго: составы; конец_второго: составы; end;
function head(конец_состава: составы): составы; begin
head := конец_состава.предыдущий; head^.следующий:= nil;
end;
procedure addbeg( var начало_состава: составы; добавляемый: составы);
begin
добавляемый.следующий := начало_состава; начало_состава:= добавляемый; начало_состава.предыдущий:= nill;
end;
procedure addend( var конец_состава: составы;
добавляемый: составы);
begin
добавляемый.предыдущий := конец_состава; конец_состава := добавляемый; конец_состава.следующий:= nill;
end; begin
{ ввод информации о пришедшем составе }
writeln('введите информацию о вагонах пришедшего состава'); все_вагоны:= 2;
конец_пришедшего:= nil;
33
начало_пришедшего:= nil; while все_вагоны = 2 do
begin
write('номер вагона и пункт назначения:'); new(текущий_вагон);
with текущий_вагон^ do
readln( номер вагона, пункт_назначения); addend( конец_пришедшего, текущий_вагон); if начало_пришедшего = nil
then начало_пришедшего := конец_пришедшего;
writeln('все вагоны? 1 – да, 2 – нет '); readln(все_вагоны);
end;
процесс_сортировки.конец_первого:= конец_пришедшего; процесс_сортировки.начало_второго:= nil; процесс_сортировки.конец_второго:= nil;
while процесс_сортировки.конец_первого <> nil do
if процесс_сортировки.конец_первого.пункт_назначения = 'A' then
begin
текущий_вагон:= процесс_сортировки.конец_первого; процесс_сортировки.конец_первого:=
head(процесс_сортировки.конец_первого); addend(процесс_сортировки.конец_третьего,
текущий_вагон);
end
else
if процесс_сортировки.конец_первого.пункт_назначения = 'B' then
begin
текущий_вагон:= процесс_сортировки.конец_первого; процесс_сортировки.конец_первого:=
head(процесс_сортировки.конец_первого); addbeg(процесс_сортировки.начало_третьего,
текущий_вагон);
end;
начало_уходящего:= процесс_сортировки.начало_второго; конец_уходящего:= процесс_сортировки.конец_второго; end;
Литература
1. А.С.Клещев. Основы анализа и формализации информации. Лекции по курсу. Электронный вариант. 2001.
34
2.Ф.Л.Бауэр, Г.Гооз. Информатика. Вводный курс: В 2-х частях. М:Мир, 1990.
3.В.А.Успенский, А.Л.Семенов. Теория алгоритмов: основные открытия и приложения. М: Наука, Гл. ред.физ.мат.лит., 1987, 288 с.
4.А.С.Клещев, И.Л.Артемьева. Необогащенные системы логических соотношений. Ч.1. // Научно-техническая информация. Сер.2. Информ. процессы и системы, 2000, № 7, с. 18-28.