Новосибирский государственный технический университет Кафедра прикладной математики Курсовая работа по дисциплине Структуры данных и алгоритмы Факультет ПМИ Группа ПМ-71 Студент Гридасов А. Ю. Руководитель Карманов В. С. Дата защиты 05.98 Новосибирск 1998 Оглавление Оглавление 1 1. Условие задачи 2. Анализ задачи 3. Выбор и обоснование форм представления данных. 4. Алгоритм 5. Текст программы на языке Pascal 6. Выбор и обоснование набора тестов 7. Анализ результатов 8. Литература 9. Приложение 1. Условие задачи Имеется некоторое конечное число городов, которые связаны транспортной сетью, состоящей из авиа, железнодорожных, автомобильных и водных рейсов произвольного направления и включающих произвольное число городов.
Стоимость проезда различна по классам. Рейсы отправляются по недельному расписанию.
При пересадки между рейсами должно быть не менее 2-х часов. По заданным начальному и конечному городам, дате желаемого отправления, максимальному времени пути и максимальной стоимости и максимальному числу пересадок выдать все возможные маршруты, так, чтобы маршруты с меньшей датой и временем прибытия отображались раньше, чем с большим. 2.
Метод решения метод последовательных испытаний. города и все рейсы b Начальный, конечный город, ориентировочная дата и... Поиск решений будет осуществляться рекурсивно, причем максимальная глу... Каждая дуга характеризуется принадлежностью к рейсу, временем пути, це... .
Выбор и обоснование форм представления данных. По понятным причинам. Тип Pattern для хранения исходных параметров поиска представляет собой... Запись использована чтоб передавать все данные единым объектом в проце... Так как эта информация редактируется крайне редко, причем разработчико...
Алгоритм. Begin Загрузка транспортной схемы Ввод исходных данных и заполнение ша... then Добавить к маршруту проеханный участок. Вызвать процедуру поиска ... .
uses Crt, Date, Graph Const MaxCity100 MClass6 Type CityCode1 maxcity ... KindP.Kind then не повторяется рейс и сответствует тип перевозки begin... WayTime-Npath.dd elay-Npath.waytime Npattern. ECity приехали Если не приехали и лимиты не превышены то делаем рассмо... x,380-3cityq.bcity.y repeat ii mod 41 if i1 then yy.next lineto4cityy....
Уменьшение числа пересадок Начальный город Tropic Port Конечный город ... 1. Допустимые классы 123456 При данных условиях добраться нельзя 7. . Общий тест Начальный город Tropic Port Конечный город Beatiful Дата от...
Анализ результатов 1. Время пути зависит от дня оправления. 2. По причине ожидания рейса можно с меньшим числом пересадок добраться позже, чем с большим 3. Дороже не значит быстрее 4. Для нормальной транспортной системы нужно как можно больше больших транспортных узлов 8.
Литература 9.
Приложение Unit Date interface Var DTErrboolean Type Datrecord day1 31 month1 12 yearinteger dweek0 6 timeword end Const EWeekarray0 6 of string2Mo,Tu,We,Th,Fr,Sa,Sa Const RWeekarray0 6 of string2,в, а, в, в, ,б procedure newdatadat delayword var bdat procedure writedatbdat Function DayDifferA,BdatInteger Function STimeststringword Function dweek adatbyte Procedure DTInputvar ddat Procedure SDateStstring var adat Implementation uses dos, crt Function DayInMonthmbyte yintegerbyteforward procedure SDateStstring var adat const mthearray1 12 of string3 JAN,FEB,MAR,APR,MAY,JUN,JUL,AUG,SEP,OCT, NOV,DEC const mthruarray1 12 of string3 , const mthrlarray1 12 of string3 п, д, а, а, ,о, о, ,б, в,п, var i, j,ebyte modebyte Sword errboolean D,M,Y,wdword cshortint Procedure addmodebyteswordvar adat begin case mode of 1if s 0 and s 31 then A.dayS else DTErrtrue 3if s 0 and s 12 then A.monthS else DTErrtrue 5if s 100 then A.yearS else A.yearS100Y div 100 end end begin DTErrfalse GetDateY,M,D,wd elengthst i1 mode0 while i e do begin cordsti-ord0 if mode mod 20 and c 0 and c 9 then begin Sc incmode end else if c 9 and c 0 then SS10c else if mode mod 21 then begin Addmode,S,a Incmode end if mode2 then for j1 to 12 do if mthej,1upcasesti and mthej,2upcasesti1 and mthej,3upcasesti2 or mthruj,1sti or mthrlj,1sti and mthruj,2sti1 or mthrlj,2sti1 and mthruj,3sti2 or mthrlj,3sti2 then begin add3,j, a mode4 end inci end if mode mod 21 then addmode,S,a if mode 1 then add1,D,a if mode 3 then add3,M,a if mode 5 then add5,Y,a if not DTErr then DTErra.day DayInMontha.month, a.year if not DTErr then a.dweekdweeka end function dweek adatbyte var n, m,yword begin DTErrfalse ya.year if a.month 2 then begin ma.month12 decy end else ma.month nA.day2mtrunc0.6m1yy div 4-y div 100y div 400 mod 7 dweekn end Function STime ststringWord var i, e,modebyte a, sword cshortint begin DTErrfalse elengthst i1 mode0 a0 while i e do begin cordsti-ord0 if mode mod 20 and c 0 and c 9 then begin Sc incmode end else if c 9 and c 0 then SS10c else if mode1 then begin AS incmode end else if mode3 then begin AA60S incmode end inci end if mode3 then Aa60s if a 1440 then Stimea else DTErrtrue end Function DayInMonthmbyte yintegerbyte const DayInMarray1 12 of byte31,29,31,30,31,30,31,31,30,31,30,31 begin If M 2 then DayInMonthDayInMM else if y mod 4 0 then DayInMonth28 else if y mod 100 0 then DayInMonth29 else if y mod 400 0 then DayInMonth28 else DayInMonth29 end Function DayDifferA,BdatInteger Var m1,m2,y1,y2Integer Begin DTErrfalse y1A.year y2B.year if a.month 2 then begin m1a.month12 decy1 end else m1a.month if b.month 2 then begin m2b.month12 decy2 end else m2b.month DayDiffer-A.day30m1trunc0.6m11365y1y1 div 4-y1 div 100y1 div 400 B.day30m2trunc0.6m21365y2y2 div 4-y2 div 100y2 div 400 End Procedure DTInputvar ddat var ststring ybyte const empty begin ywherey repeat GotoXY1,y Write в, empty GotoXY10,y ReadLnSt SDatest, d Until not DTErr GotoXY10,y writelnd.day d.month d.year, ,RweekDweekd repeat gotoxy1,y1 writeап, empty gotoxy11,y1 readlnst d.timestimest until not DTErr gotoxy11,y1 writelnstimest div 60 stimest mod 60 end procedure writedatbdat begin writeb.time div 60 b.time mod 60, ,b.day b.month b.year, ,Rweekb.dweek end procedure newdatadat delayword var bdat var cword begin BA B.timea.timedelay mod 1440 mod 1440 delaydelay div 1440a.timedelay mod 1440 div 1440 while delayb.day DayInMonthb.month, b.year do begin delaydelay-1-DayInMonthb.month, b.yearb.d ay b.day1 b.monthb.month mod 121 if b.month1 then incb.year end b.daydelayb.day end begin end.