85056 (612462), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

end;

const ReBoadingDelay=120; {Минимальное время пересадки}

{Возвращает время до следещего после указанного времени time отоправление от станции}

{номер N рейса A}

Function DepartureDelay(A:PFlight; N:CityCode; time:week ):word;

var S:word; I:1..4; P:PWay; Q:DayTable;

begin

P:=A^.path;

S:=0;

While N>4 do begin

N:=N-4;

For I:=1 to 4 do S:=S+P^.Way[I].delay+P^.Way[I].reboard; {подсчет времени пути по полным четверкам}

P:=P^.next;

end;

For I:=1 to N do S:=S+P^.Way[I].delay+P^.Way[I].reboard; {Подсчет по неполной четверке}

time:=(10080+time-(S mod 10080)) mod 10080; {Время отправления этого рейса от начальной станции}

Q:=A^.Table;

while (Q<>nil) and (Q^.time

If Q<>nil then Departuredelay:=Q^.time-time else {Если на текущей неделе не найден}

DepartureDelay:=10080-time+(A^.Table)^.time; {Поиск ближайщего времени на следующей неделе}

end;

{Поиск всех возможных маршрутов, удовлетворяющих Pattern}

Procedure Search (FlightList:Pflight; const Pattern:Blank; Path:Link);

Var P:Pflight; I,J:CityCode; D,DDelay:Word; K:WayClass; B1,B2:Boolean;

NPattern:Blank; NPath:Link; c:Longint;

{Проверка допустимости маршрута (проверка дублирования города)}

Function Posible (P:Link; L:CityCode):Boolean;

Var b:boolean; i:citycode; Q:pway;

Begin

b:=true;

While (P<>nil) and b do begin {Просмотр всех предидущих пересадок}

Q:=P^.flight^.path;

i:=1;

while Q^.way[i].city<>P^.bcity do begin {Поиск города отправления}

i:=(i mod 4)+1; if i=1 then Q:=Q^.next;

end;

repeat

b:=Q^.way[i].city<>L; {Проверка города на дублирование}

i:=(i mod 4)+1; if i=1 then Q:=Q^.next

until (Q^.way[i].city=P^.target) or not b; {переход к следующему пока не город назначения}

p:=p^.last

end;

Posible:=b;

End;

begin

New(NPath);

NPath^.last:=Path;

P:=FlightList;

While P<>nil do begin {Просмотр всех рейсов}

if ((Path=nil) or (P<>Path^.Flight)) and Pattern.Kind[P^.Kind] then {не повторяется рейс и сответствует тип перевозки}

begin

I:=1; {Поиск среди городов следования начальный пункт}

While (IPattern.BCity) do inc (I);

If CityInPath(P^.path, I)^.city=Pattern.BCity then begin {Если начальный найден}

NPattern:=Pattern; {Подготовка нового шаблона и новой пересадки}

if Npattern.reboading>1 then dec(Npattern.reboading);

Npath^.flight:=P;

For K:=1 to Mclass do Npath^.cost[k]:=0;

Npath^.bcity:=pattern.bcity;

Npath^.Ddelay:=DepartureDelay(P,I,Pattern.delay);

Npath^.waytime:=0;

J:=I;

Repeat {просмотр следующих городов}

Inc(J);

{Внесение исправлений в шаблон и элемент маршрута о цене и времени}

For K:=1 to MClass do If Pattern.Class[K] and P^.class[K] then

Npath^.cost[k]:=Npath^.cost[k]+CityInPath(P^.path,J)^.Cost[K];

Npath^.waytime:=Npath^.waytime+CityInPath(P^.path,J)^.delay;

Npath^.target:=CityInPath(P^.path,J)^.City;

NPattern.Bcity:=CityInPath(P^.path,J)^.City;

Npattern.WayTime:=Pattern.WayTime-Npath^.ddelay-Npath^.waytime;

Npattern.Delay:=(pattern.Delay+Npath^.Ddelay+Npath^.wayTime) mod 10080;

B1:=Posible(Path,CityInPath(P^.path,J)^.City) and (NPattern.WayTime>=0);

{Проверка: не превышены лимиты времени и стоимости и нет повтора пути}

B2:=CityInPath(P^.path,J)^.city=Pattern.ECity; {приехали?}

{Если не приехали и лимиты не превышены то делаем рассмотроим маршруты от текущего до конечного городов}

if B1 and (not B2) and (Pattern.reboading>1) then Search(FlightList,Npattern,Npath);

Npath^.waytime:=Npath^.waytime+CityInPath(P^.path,J)^.reboard;

Until (not B1) or B2 or (J>=P^.totalStation); {Выходим, если есть нарушения или рейс закончился или прехали}

If B2 and B1 then Answer(Npath,pattern.cost); {Если приехали, добавить маршрут в список}

end {найден начальный город}

end; {маршрут подходит по типу}

P:=P^.next; {переход к следущему циклу}

end;

Dispose(NPath)

end;

{Загрузка исходных данных из файла}

Function Load (A:PFlight; FName:String;var City:cities):PFlight;

Var

Source:Text; P:Pflight; I:WayClass; J,MC:CityCode; K:byte;

C:char; Q:Pway; G,L:DayTable; D:string[8];

Begin

Assign(Source,FName);

Reset(Source);

readln(Source,MC); {Количество городов}

{Считывание название городов и координат на карте }

For J:=1 to MC do begin ReadLn(source,City[j].name); readln(source,city[j].x,city[j].y) end;

While Not EOF(Source) do begin

New(P);

P^.Next:=A;

A:=P;

{Общая информация о рейсе}

ReadLn(Source, P^.company);

ReadLn(Source, P^.number);

ReadLn(Source, P^.kind);

{Стоимость каждого из классов}

For I:=1 to MClass do begin Read(Source,C); P^.class[i]:=C='X' end;

ReadLn(Source, P^.TotalStation);

New(P^.path);

Q:=P^.path;

{информация о городах следования времени пути, стоянках}

For J:=1 to P^.TotalSTation do begin

K:=((J-1) mod 4)+1;

Read(Source,Q^.Way[K].City,Q^.Way[K].Delay,Q^.Way[K].Reboard);

For I:=1 to MClass do If P^.class[I] then Read(Source,Q^.Way[K].cost[I])

else Q^.Way[K].cost[I]:=0;

If (J mod 4)=0 then begin

If (J<>P^.TotalStation) then begin New(Q^.Next); Q:=Q^.next end

else Q^.next:=nil;

end;

ReadLn(Source);

end;

New(P^.Table);

G:=P^.Table;

L:=G;

{Информация о отправлении из начального пункта}

While Not EOLn(Source) do begin

Read(Source,D);

G^.Time:=(ord(D[1])-ord('0')-1)*1440+((ord(D[3])-ord('0'))*10+ord(D[4])-ord('0'))*60

+(ord(D[6])-ord('0'))*10+ord(D[7])-ord('0');

if L^.time>G^.time then write('Wrong data');

If not EOLn(Source) then begin New(G^.next); G:=G^.next end else G^.next:=nil;

end;

ReadLn(Source);

end;

Load:=A;

end;

const line='--------------------------------------------------------------------------------';

procedure graphout(const city:cities);

var

grDriver: Integer;

grMode: Integer;

p:citycode;

begin

grDriver := Detect;

InitGraph(grDriver, grMode,'');

setcolor(12);

outtextxy(200,0,'Карта транспортной схемы');

p:=1;

while (p'') do begin

setcolor(5);

fillellipse(4*city[p].x,380-3*city[p].y,2,2);

setcolor(11);

outtextxy(4*city[p].x+5,376-3*city[p].y,city[p].name);

inc(p)

end;

end;

var List:PFLight; pattern:blank; st:string; p:answerlist;

city:cities; a:dat;

Procedure Input(var Pattern:blank; var a:dat);

var i:citycode; st:string; b:dat; w:real;

begin

with pattern do begin

GotoXY(30,1);

WriteLn('Ввод исходных данных');

write(line);

repeat

write('Начальный город ... ');

readln(st);

Bcity:=1; while (BCityst) do inc(BCity);

until BCity<>MaxCity;

repeat

write('Конечный город ... ');

readln(st);

Ecity:=1; while (ECityst) do inc(ECity);

until Ecity<>MaxCity;

repeat

gotoxy(1,5);

WriteLn('Дата отправление:');

DTInput(a);

delay:=a.Dweek*1440+a.time;

Write('Максимальное время пути (сутки):');

readln(w);

waytime:=round(1440*w);

until waytime>0;

write('Максимальная стоимость ... ');

ReadLn(cost);

write('Максимальное число пересадок ... ');

readln(reboading);

write('Тип перевозки (авиа,ж.д.,авто,водн.) ... ');

readln(st);

if st='' then for i:=1 to 4 do kind[i]:=true else

for i:=1 to 4 do kind[i]:=(st[i]='Y') or (st[i]='y') or (st[i]='X') or (st[i]='x');

write('Допустимые классы 123456 ... ');

readln(st);

if st='' then for i:=1 to 4 do class[i]:=true else

for i:=1 to 4 do class[i]:=(st[i]='Y') or (st[i]='y') or (st[i]='X') or (st[i]='x');

end;

end;

procedure outres(p:Answerlist; a:dat);

var k:word; q:link; b:dat; i:citycode; y:pway; c:byte;

begin

k:=0;

while P<>nil do begin

inc(k);

{ write(p^.path^.bcity);}

Q:=P^.path;

b:=a;

while Q<>nil do begin

write(city[q^.bcity].name);

Writeln(' ',city[Q^.Target].name);

newdat(b,Q^.ddelay,b);

write('Отправление: '); writedat(b);

newdat(b,Q^.waytime,b);

write(' Прибытие: '); writedat(b); writeln;

Q:=Q^.last;

end;

newdat(a,p^.waytime,b);

writeln (' цена: ',P^.mincost,' - ',p^.maxcost);

readln(st);

if st='p' then begin

graphout(city);

q:=p^.path;

c:=2;

while q<>nil do begin

i:=1;

y:=q^.flight^.path;

while y^.way[i].city<>q^.bcity do begin

i:=(i mod 4)+1; if i=1 then y:=y^.next;

end;

setcolor(c);

moveto(4*city[q^.bcity].x,380-3*city[q^.bcity].y);

repeat

i:=(i mod 4)+1; if i=1 then y:=y^.next;

lineto(4*city[y^.way[i].city].x,380-3*city[y^.way[i].city].y);

until (y^.way[i].city=q^.target);

Q:=Q^.last; inc(c);

end; repeat until keypressed; CloseGraph;

end;

P:=P^.next;

end;

if k=0 then write('При данных условиях добраться нельзя') else writeln('Всего ',k,' маршшрутов');

end;

Begin

List:=Load(nil,'trafic',city);

graphout(city);

repeat until keypressed;

closegraph;

Input(pattern,a);

new(lanswer);

lanswer^.next:=nil;

Search(List,pattern,nil);

outres(Lanswer^.next,a);

end.

Выбор и обоснование набора тестов

В качестве транспортной системы бала взята система, состоящая из 23 городов, соединенных 19 прямыми и таким же числом обратных рейсами. Название городов и перевозчиков вымышленные. Рейсы были разработаны так, что имеется несколько крупных транспортных развязок: Palace of Dream, Diamond World, Golden River, Seaside City; и несколько «удаленных» городов: Far Star City, Oil City, North Star City.

Разные рейсы отправляются от 3 до 18 раз в неделю.

1. Общий тест

Начальный город ... Tropic Port

Конечный город ... Beatiful

Дата отправление:

Дата ... 8.5.1998 Пт

Время ... 0:0

Максимальное время пути (сутки):3

Максимальная стоимость ... 200

Максимальное число пересадок ... 3

Тип перевозки (авиа,ж.д.,авто,водн.) ...

Допустимые классы 123456 ...

Tropic Port Palace Of The Dream

Отправление: 14:29 8.5.1998 Пт Прибытие: 19:14 8.5.1998 Пт

Palace Of The Dream Diamond World

Отправление: 2:15 9.5.1998 Пт Прибытие: 5:15 9.5.1998 Пт

Diamond World Beatiful

Отправление: 17:20 9.5.1998 Пт Прибытие: 19:20 9.5.1998 Пт

цена: 195 – 250

Tropic Port Lakes Land

Отправление: 14:29 8.5.1998 Пт Прибытие: 16:29 8.5.1998 Пт

Lakes Land Diamond World

Отправление: 0:25 9.5.1998 Пт Прибытие: 3:25 9.5.1998 Пт

Diamond World Beatiful

Отправление: 17:20 9.5.1998 Пт Прибытие: 19:20 9.5.1998 Пт

цена: 165 - 195

Tropic Port Oil City

Отправление: 12:0 8.5.1998 Пт Прибытие: 4:40 9.5.1998 Пт

Oil City Beatiful

Отправление: 12:0 9.5.1998 Пт Прибытие: 16:10 10.5.1998 Пт

цена: 75 – 105

2. Тест с «урезанием бюджета»

Начальный город ... Tropic Port

Конечный город ... Beatiful

Дата отправление:

Дата ... 8.5.1998 Пт

Время ... 0:0

Максимальное время пути (сутки):3

Максимальная стоимость ... 180

Максимальное число пересадок ... 3

Тип перевозки (авиа,ж.д.,авто,водн.) ...

Допустимые классы 123456 ...

Tropic Port Lakes Land

Отправление: 14:29 8.5.1998 Пт Прибытие: 16:29 8.5.1998 Пт

Lakes Land Diamond World

Отправление: 0:25 9.5.1998 Пт Прибытие: 3:25 9.5.1998 Пт

Diamond World Beatiful

Отправление: 17:20 9.5.1998 Пт Прибытие: 19:20 9.5.1998 Пт

цена: 165 - 195

Tropic Port Oil City

Отправление: 12:0 8.5.1998 Пт Прибытие: 4:40 9.5.1998 Пт

Oil City Beatiful

Отправление: 12:0 9.5.1998 Пт Прибытие: 16:10 10.5.1998 Пт

цена: 75 – 105

3. Уменьшение числа пересадок

Начальный город ... Tropic Port

Конечный город ... Beatiful

Дата отправление:

Дата ... 8.5.1998 Пт

Время ... 0:0

Максимальное время пути (сутки):3

Максимальная стоимость ... 200

Максимальное число пересадок ... 2

Тип перевозки (авиа,ж.д.,авто,водн.) ...

Допустимые классы 123456 ...

Tropic Port Oil City

Отправление: 12:0 8.5.1998 Пт Прибытие: 4:40 9.5.1998 Пт

Oil City Beatiful

Отправление: 12:0 9.5.1998 Пт Прибытие: 16:10 10.5.1998 Пт

цена: 75 – 105

4. Нереальные условия

Начальный город ... Tropic Port

Конечный город ... Beatiful

Дата отправление:

Дата ... 8.5.1998 Пт

Время ... 0:0

Максимальное время пути (сутки):3

Максимальная стоимость ... 200

Максимальное число пересадок ... 1

Тип перевозки (авиа,ж.д.,авто,водн.) ...

Допустимые классы 123456 ...

При данных условиях добраться нельзя

Анализ результатов

Время пути зависит от дня оправления.

По причине ожидания рейса можно с меньшим числом пересадок добраться позже, чем с большим

Дороже – не значит быстрее

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

Список литературы

Для подготовки данной работы были использованы материалы с сайта http://www.ed.vseved.ru/

1 Текущий город – есть пункт назначения.

Характеристики

Список файлов курсовой работы