Реферат: Задача про транспортную систему. Подбор вариантов проезда с учетом кол-ва пересадок, длительности, видов транспорта (самолет, авто, поезд, водн.)

Новосибирскийгосударственный технический университет

Кафедра прикладной математикиКурсовая работа по дисциплине «Структуры данных и алгоритмы»

Факультет: ПМИ

Группа: ПМ-71

Студент: Гридасов А. Ю.

Руководитель: Карманов В. С.

Дата защиты: 15.05.98

Новосибирск

1998

Оглавление

TOC o «1-3» Оглавление________________________________________________________ 1

1. Условиезадачи_________________________________________________ PAGEREF_Toc419224195 h 3

2. Анализзадачи__________________________________________________ PAGEREF_Toc419224196 h 3

3. Выбор иобоснование форм представления данных.__________________ PAGEREF _Toc419224197h 3

4. Алгоритм______________________________________________________ PAGEREF_Toc419224198 h 4

5. Текстпрограммы на языке Pascal_________________________________ PAGEREF_Toc419224199 h 5

6. Выбор иобоснование набора тестов______________________________ PAGEREF_Toc419224200 h 12

7. Анализрезультатов____________________________________________ PAGEREF_Toc419224201 h 14

8. Литература____________________________________________________ PAGEREF_Toc419224202 h 14

9. Приложение___________________________________________________ PAGEREF_Toc419224203 h 15

1.

Имеется некоторое конечное число городов, которые связанытранспортной сетью, состоящей из авиа, железнодорожных, автомобильных и водныхрейсов произвольного направления и включающих произвольное число городов.Стоимость проезда различна по классам. Рейсы отправляются по недельномурасписанию. При пересадки между рейсами должно быть не менее 2-х часов. По заданным начальному и конечному городам,дате желаемого отправления, максимальному времени пути и максимальной стоимостии максимальному числу пересадок выдать все возможные маршруты, так, чтобымаршруты с меньшей датой и временем прибытия отображались раньше, чем сбольшим.

2.

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

Входными данными является:

a)

система. (города и все рейсы)

b)

Начальный, конечный город, ориентировочнаядата и время отправления, максимальное время пути максимальная цена,максимальное количество пересадок.

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

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

Метод решения – метод последовательных испытаний. Поискрешений будет осуществляться рекурсивно, причем максимальная глубина рекурсиибудет равна максимальному количеству пересадок. Так как мы имеем ограничения понекоторым параметрам то мы можем отсечь заведомо ошибочную ветвь поискарешений, сделав проверку на превышение параметров. Это позволит выигратьдополнительное время. (о реализации более подробно п.4)

3.

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

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

Для внутреннего хранения информации о рейсах используется цепь (однонаправленный список) PFlight с 7-ю информационнымиполями различных типов:

1)

string[20] так по понятным причинам.

2)

string[10] т.к. в номерах рейса часто используются различные нецифровые шифры, индексы, коды.

3)

4)

5)

4-х станциях, т.е. представляетсобой массив из 4 элементов. Это сделано для экономии памяти на избыточныхуказателях. При этом усложнение кода программы незначительно.

6)

7)

представляется в виде массива индексом является класс, а типом элемента– булевский.

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

Для хранения времени пути используется тип Integer. Отрицательные числа нужны дляконтроля за превышением времени пути.

Для хранения цены используется тип LongInt. Причины выбора этого типаочевидны.

Тип Patternдля хранения исходных параметров поиска представляет собой запись сполями: время отправления относительно понедельника в минутах, начальный иконечный город, допустимые типы транспорта, допустимые классы, максимальноеколичество пересадок, максимальное время пути, максимальная цена, допустимыеклассы. Выбор типов для всех полей кроме «допустимые типы транспорта»обсуждался выше. Для поля «допустимыетипы транспорта» выбран массив где тип индекс – это тип транспорта, а типэлемента – булевский. Это сделано по причине того что маршрут может включать.Поездки на разных видах транспорта (тех где в значение true). Запись использована чтобпередавать все данные единым объектом в процедуру поиска маршрута.

Тип Link предназначендля хранения информации о части маршрута между двумя городами, соединеннымиодним рейсом. Кроме ссылки на предыдущую такую часть он содержит ссылку нарейс, коды начального и конечного города, общую цену участка, времяотправления, относительно заданного пользователем время отправления, общеевремя пути по участку. Типы полей и обоснования их выбора обсуждались выше. Всовокупности цепочка таких элементов задает один маршрут.

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

Внешнее представление:

Транспортная система хранится во внешнем текстовом файле.Файл может быть создан любым текстовым редактором. В файле указываетсяследующее:

Количество городов. Со следующей строки начинаетсяинформация о городах: название города, на следующей строчке координаты. Послевсех городов начинается информация о рейсах: компания, номер, тип, классы, количество станций; номер города,время пути, время стоянки цена по классам, для каждого города; времяотправления от начальной станции.

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

Название городов вводятся как строки, дата – в любом формате (дд-мм-гг, дд-мм-гггг, дд-мес-гг и т.п.) время чч: мм. Поумолчанию полагается дата – текущий день, время 0:00.

Максимальное время пути, максимальное число пересадок,максимальная цена – вводятся как числа.

4.

Begin

{Загрузка транспортной схемы};

{Ввод исходных данных и заполнениешаблона};

{Вызов процедуры поиска с введеннымшаблоном, построенная часть маршрута — пустая};

{Вывод полученного множества маршрутов}

End

{Процедурапоиска маршрута с данным шаблоном и уже построенной частью маршрута}

Begin

While {просмотрены не все рейсы} do begin

If {соответствует тип транспорта} and {Текущий рейс не равенпредыдущему}then

Begin

If {город отправления присутствует врейсе, причем раньше конечной станции} then begin

{Рассчитать времяотправления ближайшего следующего рейса}

Repeat

{Перейтик следующему городу};

{Рассчитать время дорогис учетом нового участка}

If {текущий город еще не проезжали} and {время пути непревышает максимального}

and {количество пересадок не превышаетмаксимального} and {неприехали[1]

}

then {Добавить к маршруту проеханныйучасток. Вызвать процедуру поиска маршрута

от текущего города до конечного с новыми значениями времени}

Until {текущий городпроезжали} or {времяисчерпано} or {приехали} or {конец рейса};

If {приехали} and {времяне превышено} and {минимальнаяцена рейсане выше

допустимой} then {Добавить построенный маршрут вмно-во ответов на нужное место}

end;

{Перейти к следующему рейсу}

end;

end

5. Pascal

uses Crt, Date, Graph;

Const MaxCity=100; MClass=6;

Type

CityCode=1..maxcity; {Внутрений код города}

Week=0..10079; {Тип время вминутак с 0:00 понедельника}

DayTable=^IDayTable; {Таблица отправлений от начальной станции}

IDayTable=record

Time:Week;

Next:DayTable;

end;

WayKind=1..4; {Тип пути (аэро,море, ж.д, авто)}

WayClass=1..MClass; {Класс илитип перевозки}

Cities=array[CityCode] of {Названия и координаты городов}

record

name:string[20];

x,y:word;

end;

mcost=array[wayclass] of longint; {Таблица стоимости по классам}

Way=record

City:Citycode;

Delay,Reboard:Word;

Cost:mcost;

end;

WayP=^way;

PWay=^Way1; {Информация о городахследования рейса}

Way1=record

Way:array[1..4] of way;

next:PWay;

end;

wclass=array[WayClass] of boolean;

PFlight=^Flight;

Flight=record {Информация о рейсе}

company:string[20];

number:string[10];

totalstation:CityCode;

table:DayTable;

path:PWay;

kind:WayKind;

class:WClass;

next:PFlight;

end;

Blank=record {Шаблон для поиска пути}

delay:Week;

BCity,ECity:CityCode;

Kind:array[WayKind] of boolean;

ReBoading:CityCode;

WayTime:Integer;

Cost:Longint;

Class:WClass;

end;

Link=^CityList; {Цепочка рейсовдля проезда от начала до конца}

CityList=record {Информация опроезде между двумя пунктами одним рейсом}

DDelay:Word;

waytime:word;

cost:mcost;

Bcity,Target:CityCode;

Flight:PFlight;

Last:Link;

end;

AnswerList=^IAnswer; {Список всех возможных маршрутов следования}

IAnswer=record

path:link;

reboard:citycode;

mincost,maxcost:longint;

waytime:word;

next:AnswerList;

end;

var Lanswer:AnswerList; {глобальная переменная — началосписка маршрутов }

{Добавления нового найденного маршрута}

Procedure Answer(A:Link;cost:longint);

var P,Q:Link; d,s1,s2:word; W,PAnswer:answerlist;r:citycode;

functionmin(a:mcost):longint; {Минимальная стоимость по классам}

var i:integer;m:longint;

begin

m:=1000000000;

for i:=1 toMclass do if (m>a[i]) and (a[i]>0) then m:=a[i];

min:=m

end;

functionmax(a:mcost):longint; {Максимальнаястоимость по классам}

var i:integer;m:longint;

begin

m:=a[1];

for i:=2 toMclass do if m<a[i] then m:=a[i];

max:=m

end;

begin

new(PAnswer);

Panswer^.path:=nil;

P:=A;

s1:=0; s2:=0;{верхняя и нижняя границы цены}

r:=1; {количествопересадок}

d:=0; {времяпути}

Repeat

s1:=s1+min(P^.cost); {Подсчетсуммы параметров по рейсам в маршруте}

s2:=s2+max(P^.cost);

d:=d+P^.ddelay+P^.waytime;

P:=P^.last;{Переход к следующему рейсу в маршруте}

inc(r);

Until P=nil;

if s1<=costthen begin {Если соответствует цена}

P:=A;

Repeat

new(Q); {Сборка цепочки рейсов маршрута}

Q^:=P^;

Q^.last:=Panswer^.path;

Panswer^.path:=Q;

P:=P^.last;{Переход к следующему рейсу в маршруте}

Until p=nil;

Panswer^.mincost:=s1; Panswer^.maxcost:=s2; {Сохранение сумарных цен и времени}

Panswer^.waytime:=d; Panswer^.reboard:=r; {и числа пересадок в элементе маршрута}

W:=LAnswer;

While(W^.next<>nil) and ((W^.next)^.waytime<d) do W:=W^.next; {Поиск местав соответствии времени пути}

While(W^.next<>nil) and ((W^.next)^.reboard<r) and ((W^.next)^.waytime=d)do W:=W^.next; {Поиск места по кол-ву пересадок}

Panswer^.next:=W^.next; {Добавление маршрута в найденное место}

W^.next:=Panswer;

end

end;

{Возвращает ссылку на информацию об I-ой станцииследования}

Function CityInPath(A:Pway; I:citycode):WayP;

var P:Pway;

Begin

P:=A;

While I>4 do begin I:=I-4; P:=P^.next end; {Поискчетверки в которой данная станция}

CityInPath:=@P^.Way[I]; {Результат}

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 dobegin

N:=N-4;

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

P:=P^.next;

end;

For I:=1 to N doS:=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<time+ReboadingDelay) do Q:=Q^.next; {Поискближайшего времени на текущей неделе}

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

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

end;

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

Procedure Search (FlightList:Pflight; constPattern: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;

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

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

end;

repeat

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

i:=(imod 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;

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

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

begin

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

While(I<P^.TotalStation-1) and (CityInPath(P^.path,I)^.city<>Pattern.BCity) do inc (I);

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

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

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

Npath^.flight:=P;

For K:=1to 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);

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

ForK:=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 B1and (not B2) and (Pattern.reboading>1) thenSearch(FlightList,Npattern,Npath);

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

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

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

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

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

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

end;

Dispose(NPath)

end;

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

Function Load (A:PFlight; FName:String;varCity: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 dobegin ReadLn(source,City[j].name); readln(source,city[j].x,city[j].y) end;

While NotEOF(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 toMClass do begin Read(Source,C); P^.class[i]:=C='X' end;

ReadLn(Source,P^.TotalStation);

New(P^.path);

Q:=P^.path;

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

For J:=1 toP^.TotalSTation do begin

K:=((J-1) mod4)+1;

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

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

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

If (J mod4)=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 NotEOLn(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('Wrongdata');

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

end;

ReadLn(Source);

end;

Load:=A;

end;

constline='--------------------------------------------------------------------------------';

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<maxcity) and (city[p].name<>'') 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;

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 dobegin

GotoXY(30,1);

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

write(line);

repeat

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

readln(st);

Bcity:=1; while(BCity<Maxcity) and (City[BCity].name<>st) do inc(BCity);

untilBCity<>MaxCity;

repeat

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

readln(st);

Ecity:=1; while(ECity<Maxcity) and (City[ECity].name<>st) do inc(ECity);

untilEcity<>MaxCity;

repeat

gotoxy(1,5);

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

DTInput(a);

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

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

readln(w);

waytime:=round(1440*w);

untilwaytime>0;

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

ReadLn(cost);

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

readln(reboading);

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

readln(st);

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

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

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

readln(st);

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

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

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<>nildo begin

inc(k);

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

Q:=P^.path;

b:=a;

whileQ<>nil do begin

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

Writeln('<',q^.flight^.company,q^.Flight^.Number,'> ',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;

whileq<>nil do begin

i:=1;

y:=q^.flight^.path;

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

i:=(i mod4)+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 mod4)+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 thenwrite('При данных условиях добраться нельзя') else writeln('Всего ',k,'маршшрутов');

end;

Begin

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

graphout(city);

repeat untilkeypressed;

closegraph;

Input(pattern,a);

new(lanswer);

lanswer^.next:=nil;

Search(List,pattern,nil);

outres(Lanswer^.next,a);

end.

6.

В качестве транспортной системы бала взята система,состоящая из 23 городов, соединенных 19 прямыми и таким же числом обратныхрейсами. Название городов и перевозчиков вымышленные. Рейсы были разработаны так, что имеется несколько крупныхтранспортных развязок: Palaceof Dream, Diamond World, GoldenRiver, 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 ...

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

7.

1.

2.

3.

4.

8.

9.

Unit Date;

interface

Var DTErr:boolean;

Type Dat=record

day:1..31;

month:1..12;

year:integer;

dweek:0..6;

time:word;

end;

Const EWeek:array[0..6] ofstring[2]=('Mo','Tu','We','Th','Fr','Sa','Sa');

Const RWeek:array[0..6] ofstring[2]=('Џ','‚в','‘а','—в','Џв','‘Ў','‚б');

procedure newdat(a:dat; delay:word; var b:dat);

procedure writedat(b:dat);

Function DayDiffer(A,B:dat):Integer;

Function STime(st:string):word;

Function dweek (a:dat):byte;

Procedure DTInput(var d:dat);

Procedure SDate(St:string; var a:dat);

Implementation

uses dos,crt;

Function DayInMonth(m:byte; y:integer):byte;forward;

procedure SDate(St:string; var a:dat);

constmthe:array[1..12] of string[3]=('JAN','FEB','MAR','APR','MAY','JUN','JUL','AUG','SEP','OCT','NOV','DEC');

constmthru:array[1..12] of string[3]=('џЌ‚','”…‚','ЊЂђ','ЂЏђ','ЊЂ‰','ћЌ','ћ‹','Ђ‚ѓ','‘…Ќ','ЋЉ’','ЌЋџ','„…Љ');

var i,j,e:byte;mode:byte; S:word; err:boolean; D,M,Y,wd:word; c:shortint;

Procedureadd(mode:byte;s:word;var a:dat);

begin

case mode of

1:if(s>0) and (s<=31) then A.day:=S else DTErr:=true;

3:if(s>0) and (s<=12) then A.month:=S else DTErr:=true;

5:ifs>=100 then A.year:=S else A.year:=S+100*(Y div 100);

end;

begin

DTErr:=false;

GetDate(Y,M,D,wd);

e:=length(st);

i:=1; mode:=0;

while (i<=e)do begin

c:=ord(st[i])-ord('0');

if ((mode mod2)=0) and (c>=0) and (c<=9) then begin S:=c; inc(mode) end

else if(c<=9) and (c>=0) then S:=S*10+c

else if(mode mod 2)=1 then begin Add(mode,S,a); Inc(mode) end;

if (mode=2)then

for j:=1 to12 do

if(mthe[j,1]=upcase(st[i])) and (mthe[j,2]=upcase(st[i+1])) and (mthe[j,3]=upcase(st[i+2]))or

((mthru[j,1]=st[i]) or (mthrl[j,1]=st[i])) and ((mthru[j,2]=st[i+1]) or(mthrl[j,2]=st[i+1])) and

((mthru[j,3]=st[i+2]) or (mthrl[j,3]=st[i+2])) then

beginadd(3,j,a); mode:=4 end;

inc(i);

end;

if (mode mod 2)=1then add(mode,S,a);

if mode<1 thenadd(1,D,a);

if mode<3 thenadd(3,M,a);

if mode<5 thenadd(5,Y,a);

if not DTErr thenDTErr:=a.day>DayInMonth(a.month,a.year);

if not DTErr thena.dweek:=dweek(a);

end;

function dweek (a:dat):byte;

var n,m,y:word;

begin

DTErr:=false;

y:=a.year;

if a.month<=2then begin m:=a.month+12; dec(y) end else m:=a.month;

n:=(A.day+2*m+trunc(0.6*(m+1))+y+(y div 4)-(y div 100)+(y div 400)) mod7;

dweek:=n;

end;

Function STime (st:string):Word;

var i,e,mode:byte; a,s:word; c:shortint;

begin

DTErr:=false;

e:=length(st);

i:=1; mode:=0; a:=0;

while (i<=e)do begin

c:=ord(st[i])-ord('0');

if ((mode mod2)=0) and (c>=0) and (c<=9) then begin S:=c; inc(mode) end

else if(c<=9) and (c>=0) then S:=S*10+c

else ifmode=1 then begin A:=S; inc(mode) end

else ifmode=3 then begin A:=A*60+S; inc(mode) end;

inc(i)

end;

if mode=3 thenA:=a*60+s;

if a<1440 thenStime:=a else DTErr:=true;

end;

Function DayInMonth(m:byte; y:integer):byte;

const DayInM:array[1..12] ofbyte=(31,29,31,30,31,30,31,31,30,31,30,31);

begin

If M<>2then DayInMonth:=DayInM[M]

else if (y mod4)<>0 then DayInMonth:=28

else if (ymod 100)<>0 then DayInMonth:=29

else if (ymod 400)<>0 then DayInMonth:=28 else DayInMonth:=29

end;

Function DayDiffer(A,B:dat):Integer;

Var m1,m2,y1,y2:Integer;

Begin

DTErr:=false;

y1:=A.year;

y2:=B.year;

if a.month<=2then begin m1:=a.month+12; dec(y1) end else m1:=a.month;

if b.month<=2then begin m2:=b.month+12; dec(y2) end else m2:=b.month;

DayDiffer:=-(A.day+30*m1+trunc(0.6*(m1+1))+365*y1+(y1 div 4)-(y1 div100)+(y1 div 400))+

(B.day+30*m2+trunc(0.6*(m2+1))+365*y2+(y2 div 4)-(y2 div 100)+(y2 div400));

End;

Procedure DTInput(var d:dat);

var st:string; y:byte;

const empty=' ';

begin

y:=wherey;

repeat

GotoXY(1,y);

Write('„ в … ',empty);

GotoXY(10,y);

ReadLn(St);

SDate(st,d);

Until not DTErr;

GotoXY(10,y);

writeln(d.day,'.',d.month,'.',d.year,' ',Rweek[Dweek(d)]);

repeat

gotoxy(1,y+1);

write('‚аҐ¬п… ',empty);

gotoxy(11,y+1);

readln(st);

d.time:=stime(st);

until not DTErr;

gotoxy(11,y+1);

writeln(stime(st)div 60,':',stime(st) mod 60);

end;

procedure writedat(b:dat);

begin

write(b.time div60,':',b.time mod 60,' ',b.day,'.',b.month,'.',b.year,' ',Rweek[b.dweek]);

end;

procedure newdat(a:dat; delay:word; var b:dat);

var c:word;

begin

B:=A;

B.time:=(a.time+(delay mod 1440)) mod 1440;

delay:=(delay div1440)+((a.time+(delay mod 1440)) div 1440);

whiledelay+b.day>DayInMonth(b.month,b.year) do begin

delay:=delay-1-DayInMonth(b.month,b.year)+b.day;

b.day:=1;

b.month:=(b.month mod 12)+1;

if b.month=1then inc(b.year);

end;

b.day:=delay+b.day;

end;

begin

end.

[1]

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

еще рефераты

Еще работы по программированию, базе данных

Реферат по программированию, базе данных

Тест по истории

29 Августа 2013

Реферат по программированию, базе данных

Программа контроля знаний студентов по дисциплине ЭРМ и РК в процессе учебы

29 Августа 2013

Реферат по программированию, базе данных

LL (k) (-грамматики)

29 Августа 2013

Реферат по программированию, базе данных

Системное и программное обеспечение

29 Августа 2013