Нахождение шляху від однієї населённого пункту до другому

Тип роботи:
Реферат
Предмет:
Інформатика, програмування


Дізнатися вартість нової

Детальна інформація про роботу

Витяг з роботи

Мета роботи: Розробити програму, яка здійснює перебування шляху від однієї населённого пункту до другому.

Нині індустрія виробництва комп’ютерів, і програмного забезпечення їм є одним із найважливіших сфер економіки розвинутих країн. Щороку до світі продаються мільйони комп’ютерів. Тільки США обсяг продажу комп’ютерів становить мільйони доларів — і постійно продовжує расти.

У чому причини такої стрімкого зростання індустрії персональних комп’ютерів, і їх порівняльна вигідність багатьом ділових застосувань? Простота використання, забезпечена з допомогою діалогового способу взаємодії з комп’ютером. Щодо високі спроби з переробці інформації, наявність програмного забезпечення, а як і потужних систем і розробити нового програмного обеспечения.

Використана в звіті програма можна використовувати на вирішення завдань, що з проложением маршруту дороги будь-якого типа.

Визначення досяжності населених пунктов.

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 =

{Ініціалізація пунктів меню}

(«¦ Введення даних ¦ «,

" ¦ Висновок даних ¦ «,

" ¦ Запис в файл ¦ «,

" ¦ Зчитування файла ¦ «,

" ¦ Висновок результату ¦ «,

" 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 з of {Визначити код натиснутою клавиши}

#13: case sl of {Клавіша Enter}

1: InputData;

2: OutputData;

3: Save;

4: Load;

5: FindPath; end;

#0: begin {Аналіз функціональних клавіш} c: =readkey; case з 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; interface uses 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 з 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 з 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 з 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 з 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.

Показати Згорнути
Заповнити форму поточною роботою