.

Нахождение пути от одного населённого пункта к другому

Язык: русский
Формат: реферат
Тип документа: Word Doc
0 539
Скачать документ

Цель работы:

Разработать программу, осуществляющую нахождение пути от одного
населённого пункта к другому.

Введение

В настоящее время индустрия производства компьютеров и программного
обеспечения для них является одной из наиболее важных сфер экономики
развитых стран. Ежегодно в мире продаются десятки миллионов
компьютеров. Только в США объем продаж компьютеров составляет десятки
миллионов долларов и постоянно продолжает расти.

В чем же причины такого стремительного роста индустрии персональных
компьютеров и их сравнительная выгодность для многих деловых применений?

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

Относительно высокие возможности по переработке информации, наличие
программного обеспечения, а так же мощных систем для разработки нового
программного обеспечения.

Использованная в отчёте программа может использоваться для решения
задач, связанных с проложением маршрута дороги любого типа.

Определение достижимости населённых пунктов.

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 c of {Определить код нажатой клавиши}

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

1: InputData;

2: OutputData;

3: Save;

4: Load;

TH

a

z

”Z

dh

&

&

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;

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

textattr:=66;

gotoxy (25,n+3);

write (t[n]); {Вывод отмеченного города}

end;

textattr:=7;

{Вывод найденного маршрута либо надписи о его отсутствии}

gotoxy(60,1);

if (nfv>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.

PAGE 1

PAGE 13

Нашли опечатку? Выделите и нажмите CTRL+Enter

Похожие документы
Обсуждение

Оставить комментарий

avatar
  Подписаться  
Уведомление о
Заказать реферат!
UkrReferat.com. Всі права захищені. 2000-2020