Новосибірський державний технічний університет
Кафедра прикладної математики
Курсова робота
з дисципліни В«Структури даних і алгоритмиВ»
В
Факультет: ПМІ
Група: ПМ-71
Студент: Гридасов А. Ю.
Керівник: Карманов В. С.
Дата захисту: 15.05.98
Новосибірськ
1998
Зміст
Оглавление________________________________________________________ 1
1. Умова задачи_________________________________________________ 3
2. Аналіз задачи__________________________________________________ 3
3. Вибір і обгрунтування форм представлення данних._________________ 3
4. Алгоритм______________________________________________________ 4
5. Текст програми мовою Pascal_________________________________ 5
6. Вибір та обгрунтування набору тестов______________________________ 12
7. Аналіз результатов____________________________________________ 14
8. Литература____________________________________________________ 14
9. Приложение___________________________________________________ 15
В
1. Умова задачі
Є деяке кінцеве число міст, які пов'язані транспортною мережею, що складається з авіа, залізничних, автомобільних і водних рейсів довільного напрямку і які включають довільне число міст. Вартість проїзду різна по класах. Рейс відправляються по тижневому розкладом. При пересадки між рейсами має бути не менше 2-х годин. По заданих початкового і кінцевого містам, датою бажаного відправлення, максимальному часу шляху і максимальної вартості та максимальному числу пересадок видати всі можливі маршрути, так, щоб маршрути з меншою датою і часом прибуття відображалися раніше, ніж з великим.
2. Аналіз завдання
Транспортна схема являє собою спрямований зважений мультіграф. Кожна дуга характеризується належністю до рейсу, часом шляху, ціною кожного з класів, часом відправлення. p> Вхідними даними є:
a) Транспортна система. (Міста і всі рейси)
b) Початковий, кінцевий місто, орієнтовна дата та час відправлення, максимальний час шляху максимальна ціна, максимальна кількість пересадок.
Причому дані першої групи змінюються вкрай рідко і задаються розробником транспортної системи, а дані другої групи змінюються від завдання до завдання і задаються кожним користувачем.
Результатом роботи програми є кінцеве безліч маршрутів. Два маршруту ми будемо вважати різними, якщо вони відрізняються хоча б одним містом прямування або хоча б одним рейсом. Після того, як знайдені всі маршрути вони сор...