Мета роботи:
Розробити програму, що здійснює знаходження шляху від одного населеногопункту до іншого.
Введення
В даний час індустрія виробництва комп'ютерів та програмногозабезпечення для них є однією з найбільш важливих сфер економікирозвинених країн. Щорічно у світі продаються десятки мільйонів комп'ютерів.
Тільки в США обсяг продажів комп'ютерів складає десятки мільйонівдоларів і постійно продовжує рости.
У чому ж причини такого стрімкого зростання індустрії персональнихкомп'ютерів та їх порівняльна вигідність для багатьох ділових застосувань?
Простота використання, забезпечена за допомогою діалогового способувзаємодії з комп'ютером.
Відносно високі можливості з переробки інформації, наявністьпрограмного забезпечення, а також потужних систем для розробки новогопрограмного забезпечення.
Використана в звіті програма може використовуватися для вирішеннязавдань, пов'язаних з прокладання маршруту дороги будь-якого типу.
Визначення досяжності населених пунктів.
1.1 Аналіз вимог.
У списку задаються міста (населені пункти), а також дороги між ними
(є чи ні), необхідно розробити програму з використанняммодульного програмування, що здійснює знаходження найкоротшого шляхуміж населеними пунктами, які задаються користувачем у процесі роботипрограми.
Рішення поставленої задачі здійснюється таким методом:
Cтроітся граф, вершини якого - населені пункти, а ребра - дорогиміж ними.
У процесі роботи програми в даному графі за допомогою рекурентнихпроцедури знаходяться шляху з однієї вершини в іншу. Дана процедура вЯк параметри отримує масив пройдених вершин, поточну вершину ікількість вже пройдених вершин. На кожному етапі процедура перевіряє всі,не пройдений досягнуті вершини, і або знаходить заданий шлях, якщодосягнута кінцева вершина, або викликає саму себе для всіх, непройдених вершин.
Для організації даного алгоритму використовується дві процедури: процедуразнаходження всього шляху і рекурсивна процедура пошуку одиничного маршруту.
Процедура знаходження всього шляху здійснює перебір всіх населенихпунктів і виклик рекурсивної процедури, яка здійснює пошук маршрутуміж цими населеними пунктами.
Засоби вирішення задачі: використовуються засоби логічногомови програмування Turbo Pascal 7.0.
1.2 Проектування.
Для реалізації поставленої задачі програма повинна виконувати наступніфункції:
Введення даних користувачем з клавіатури - вводяться назви населенихпунктів і дороги, що з'єднують їх;
Висновок даних - виведення на екран списку населених пунктів і доріг,з'єднує їх.
Запис у файл - запис у файл, ім'я якого вказує користувач удіалоговому режимі, назви населених пунктів та існуючих доріг міжними у вигляді текстової інформації;
Зчитування файлу з диска, з ім'ям, яке вказує користувач удіалоговому режимі
Висновок результату - користувач задає початковий і кінцевий населенийпункт, між якими необхідно прокласти шлях, на екрані з'являєтьсямаршрут, або повідомлення: "маршрут не знайдений".
Дана програма реалізована з використанням принципу модульногопрограмування, головною перевагою якого є простотавикористання, можливість підключення програмою різних модулів, якімогли бути розроблені раніше, швидке знаходження основного текступрограми, а також виправлення та налагодження процедур при використанні іншогопрограми або спеціальної програми-відладчика, яка підключає до себеданий модуль.
Всі процедури, які використовуються даною програмою, перебувають у unit-модуліph.tpu і призначені для використання основною програмою, яказнаходиться у файлі path.pas.
Основна програма здійснює виведення меню на екран, опитування клавіатури івиклик процедури, відповідної самій клавіші.
Для реалізації введення даних використовується процедура InputData, яказдійснює введення імен міст з клавіатури, якщо замість назви містабув натиснуто введення, то процедура виводить перелік міст на екран ікористувач, пересуваючи курсор і, натискаючи введення, складає список доріг,з'єднують ці міста між собою, при натисненні клавіші Esc процедураприпиняє свою роботу і виходить до головного меню.
Для реалізації виведення даних на екран використовується процедура OutputData,яка здійснює читання в циклі масиву міст і виведення його на екран, атакож масиву доріг, що з'єднують ці міста і виводить з на екран.
Для реалізації запиту імені файлу і запису даних у файл використовуєтьсяпроцедура Save, яка спочатку виводить запит на екран, здійснює введенняімені файлу, відкриває файл, ім'я якого вводиться користувачем зклавіатури в поточному каталозі, у циклі з масиву міст записує надиск перелік міст, потім також перелік доріг, що з'єднують їх.
Для реалізації запиту імені файлу і читання даних з файлу в масиввикористовується процедура load, яка спочатку виводить запит імені файлу наекран, здійснює введення імені файлу, відкриває файл, ім'я якого вводитьсякористувачем, зчитує дані в масив міст, потім в масив доріг.
Для пошуку шляху між містами використовується процедура FindPath, яказдійснює виведення списку міст на екран, опитування клавіатури, при цьомукористувач може вибрати курсором початковий і кінцевий населений пункт всвоєму шляху, процедура FindPath викликає з параметрами рекурсивнупроцедуру, яка здійснює пошук оптимального маршруту між обранимимістами.
Для пошуку маршруту використовується рекурсивна процедура findnext, якійпри її виклику передаються наступні параметри: a (vec) - вектор, кожному місту відповідає номер у маршруті або нуль, якщо місто не має в маршруті; tv (integer) - місто, який перевозиться на маршруті; nv (integer) - місто, у яке необхідно дістатися; lv (integer) - кількість пройдених міст.
На кожному етапі процедура перевіряє всі, не пройдені досягнутівершини, і або знаходить заданий шлях, якщо досягнута кінцева вершина,або викликає саму себе для всіх, не пройдених вершин.
1.3 Кодування
Коротка функціональна специфікація.
Процедура InputData
Призначення: Здійснює введення початкових даних користувачем з клавіатури.
Вхідні дані: ні.
Вихідні дані: ні.
Не викликає жодних процедур.
Викликається з основної програми.
Процедура OutputData
Призначення: Здійснює виведення даних на екран.
Вхідні дані: ні.
Вихідні дані: ні.
Не викликає жодних процедур.
Викликається з основної програми.
Процедура Load
Призначення: Здійснює запит імені, читання файлу даних з цим ім'ям вмасив міст і в масив доріг.
Вхідні дані: ні.
Вихідні дані: ні.
Не викликає жодних процедур.
Викликається з основної програми.
Процедура Save
Призначення: Здійснює запит імені, запис у файл даних з такою назвоюмасиву міст і в масиву доріг.
Вхідні дані: ні.
Вихідні дані: ні.
Не викликає жодних процедур.
Викликається з основної програми.
Процедура FindPath
Призначення: Здійснює пошук шляху між містами.
Вхідні дані: ні.
Вихідні дані: ні.
Викликає findnext.
Викликається з основної програми.
Процедура FindNext
Призначення: Здійснює пошук маршруту.
Вхідні дані: a (vec) - вектор, кожному місту відповідає номер у маршруті або нуль, якщо місто не має в маршруті; tv (integer) - місто, який перевозиться на маршруті; nv (integer) - місто, в який необхідно добратися; lv ( integer) - кількість пройдених міст.
Вихідні дані: ні.
Викликає findnext.
Викликається з FindPath.
Основна програма
Здійснює оформлення екрана, висновок і обробку меню, опитування клавіатури,виклик процедури, яка б відповідала вибраному пункту меню.
1.4 Тестування
Розроблений програмний засіб було протестовано методомфункціонального тестування.
Введені в програму дані показали, що результати роботи збігаютьсяз вичисленими вручну.
Програми розробки.
Програма path
program path;uses crt, ph;var t: town; (Дані про міста) nt: integer; (Число міст) r: road; (Дані про дороги) nr: integer; (Число доріг) sl: integer; (Вибраний пункт меню) c: char; (натисків символ) i: integer; (Лічильник) fv: vec; (Вектор пройдених міст) nfv: integer; (Кількість міст)
Const
KItems = 6; (Кількість пунктів меню) mas: array [1 .. KItems] of string =
(Ініціалізація пунктів меню)
( '| Введення даних | ',
' | Висновок даних |',
'| Запис у файл |',
' | Зчитування файлу |', < p> '| Висновок результату |',
' L ------ Вихід -------');
(Основна програма)begin sl: = 1;
(Міст і доріг немає) nt: = 0; nr: = 0; repeat textattr: = 7; (Основний колір меню) clrscr; for i: = 1 to KItems do begin gotoxy (25, i +3); write (mas [i]); (Висновок пунктів меню) end; textattr: = 77; (Колір активного пункту) gotoxy (25, sl 3); write (mas [sl]); (Висновок активного пункту) c: = readkey; ( Введення символу з клавіатури) textattr: = 7; case c of (Визначити код натиснутою клавіші)
# 13: case sl of (Клавіша Enter)
1: InputData;
2: OutputData;
3: Save;
4: Load;
5: FindPath; end;
# 0: begin (Аналіз функціональних клавіш) c: = readkey; case c of
# 80: if sl1 then sl: = sl-1 else sl: = KItems; end end end; until ((c = # 13) and (sl = 6) or (c = # 27)); textattr: = 7; clrscr;end.
Модуль ph
unit ph;interfaceuses crt;type town = array [1 .. 20] of string; (Дані про міста) road = array [1 .. 200] of record (Дані про дороги) a: integer; b: integer; end; vec = array [1. .20] of integer; (Дані про пройдених містах)var t: town; (Дані про міста) nt: integer; (Число міст) r: road; (Дані про дороги) nr: integer; (Число доріг) fv: vec; (Вектор пройдених міст) nfv: integer; (Кількість міст)
procedure InputData;procedure OutputData;procedure Save;procedure Load;procedure findnext (a: vec; tv: integer; nv: integer; lv: integer);procedure FindPath;
implementation
(Введення даних)procedure InputData;var i: integer; (Лічильник) n: integer; (Обраний початковий місто) sl: integer; (Обраний місто) c: char; (натисків символ)begin
(Зчитування даних про міста) clrscr; nt: = 1; writeln ( 'Введіть назву міста (Порожній рядок - закінчити:'); repeat write ( '>'); readln (t [nt]); nt: = nt 1 ; until (t [nt-1 ]=''); nt: = nt-2;
(Перевірка, вводилися чи міста) if (nt> 0) then begin
(Так, введення доріг) nr: = 0; n: = 0; sl: = 1; repeat textattr: = 7; clrscr; for i: = 1 to nt do begin gotoxy (25, i +3); write (t [i]); (Висновок міст) end; textattr: = 77; (Колір активного міста) gotoxy (25, sl 3); write ( t [sl]); (Висновок активного міста) if (n0) then begin textattr: = 66; (Колір зазначеного міста) gotoxy (25, n +3); write (t [n]); (Висновок зазначеного міста) end ; textattr: = 7; gotoxy (1,20); write ( 'Дороги:'); for i: = 1 to nr do write ( '(', r [i]. a ,',', r [i] . b ,'}'); c: = readkey; (Введення символу з клавіатури) case c of
# 13: begin (Натиснуто ENTER)
(Або позначається початковий місто) if n = 0 then n: = sl else
(Або відбувається спроба додати дорогу) if (n = sl) then n: = 0 else begin nr: = nr 1; if (n> sl) then begin i: = n; n: = sl; sl: = i; end;
(Перевіряється, чи немає такої?) for i: = 1 to nr-1 do if ((r [i ]. a = n) and (r [i]. b = sl)) then n: = 0;
(Якщо ні - додається) if n0 then begin r [nr]. a: = n ; r [nr]. b: = sl; end else nr: = nr-1; n: = 0; sl: = 1; end; end;
# 0: begin (Аналіз функціональних клавіш) c: = readkey; case c of
# 80: if sl1 then sl: = sl-1 else sl: = nt; end end end; until (c = # 27); end;end;
(Висновок даних)procedure OutputData;var i: integer; (Лічильник)begin
(Виведення списку міст) clrscr; writeln ( 'Міста:'); for i: = 1 to nt do begin gotoxy (10, i); write (t [i]); (Висновок міст) end;
(Виведення списку доріг) gotoxy (1,20); write ( 'Дороги:'); for i: = 1 to nr do write ( '(', r [i]. A ,',', r [i]. b ,'}'); gotoxy (2,24); write ( 'ESC-Вихід');
(Очікування ESC) repeat until readkey = # 27;end;
(Запис даних у файл)procedure Save;var f: TEXT; (Файл) name: string; (Файл) n: integer; (Лічильник)begin clrscr; writeln ( 'Запис даних'); write ( 'Введіть ім'я файлу:'); readln (name); assign (f, name); rewrite (f); writeln (f, nt); for n: = 1 to nt do writeln (f, t [n]); writeln (f, nr); for n: = 1 to nr do writeln (f, r [n]. a, '', r [n]. b); close (f);end;
(Читання з файлу)procedure Load;var f: TEXT; (Файл) name: string; (Файл) n: integer; (Лічильник)begin clrscr; writeln ( 'Читання даних'); write ( 'Введіть ім'я файлу:'); readln (name); assign (f, name); reset (f); readln (f, nt); for n: = 1 to nt do readln (f, t [n]); readln (f, nr); for n: = 1 to nr do readln (f, r [n]. a, r [n]. b); close (f );end;
(рекурсивна процедура пошуку маршруту.
Вхідні параметри: a: vec - Вектор, кожному місту відповідає номер у маршруті або нуль, якщо місто не має в маршруті tv: integer - Місто, який перевозиться на маршруті nv: integer - Місто, в яке необхідно дістатися lv: integer - Кількість пройдених міст)procedure findnext (a: vec; tv: integer; nv: integer; lv: integer);var i: integer; (Лічильник)begin a [tv]: = lv; (Встановлюється у векторі прапор, що місто tv пройдений) if (tv = nv) then begin
(Якщо досягнуто необхідного місто) if ((lv +1) 0) then begin write ( 'Знайдений маршрут:'); for j: = 1 to nfv do for i: = 1 to nt do if fv [i] = j then begin gotoxy (60, j +2); write (t [i]); end ; end else write ( 'Маршрут не знайдено'); c: = readkey; (Введення символу з клавіатури) case c of
# 13: begin
(Або фіксується початковий місто) if n = 0 then n: = sl else begin
(Або забирається помилково вибраний місто) if (n = sl) then n: = 0 else begin
(Або відбувається пошук нового маршруту) nfv: = 0; (маршруту немає) for i: = 1 to 20 do v [i]: = 0; (Жодного пройденого міста) findnext (v, n, sl, 1); (Викликається перший раз рекурсивна процедура ) end; n: = 0; sl: = 1; end; end;
# 0: begin (Аналіз функціональних клавіш) c: = readkey; case c of
# 80 : if sl1 then sl: = sl-1 else sl: = nt; end end end; until (c = # 27);end;
end.
Результати виконання програми.
| Введення даних |
| Висновок даних |
| Запис у файл |
| Зчитування файлу |
| Висновок результату |
+------ Вихід ------+
Введення даних:
Введіть назву міста (Порожній рядок - закінчити):
> Місто 1
> Місто 2
> Місто 3
> Місто 4
> Місто 5
>
Дороги: ( 1,3) (3,4) (2,5) (1,4) (2,4) (2,3)
Висновок результату:
Знайдений маршрут:
Місто 1 Місто 1
Місто 3 Місто 2
Місто 2 Місто 3
Місто 5 Місто 4
Місто 5
Список використаних джерел
1. Белецкий Я. Турбо Паскаль з графікою для персональних комп'ютерів
/переклад з польської Д. І. Юренкова. - М.: Машиностроение, 1991.
2. Сергієвський М. В., Шалашов А. В. Турбо Паскаль 7.0; мова, середовище програмування. - М: Машиностроение, 1994.
3. Довідник з процедур та функцій Borland Pascal With Objects 7.0. -
Київ: Диалектика, 1993.
