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

 

Цель работы:

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

 

Введение

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

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

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

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

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


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

 

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

programpath;

usescrt,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;

    casec of                     {Определить код нажатой клавиши}

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

       1: InputData;

       2: OutputData;

       3: Save;

       4: Load;

       5: FindPath;

     end;

      #0:begin                     {Анализ функциональных клавиш}

        c:=readkey;

       case c of

         #80: if sl<KItems then sl:=sl+1 else sl:=1;

         #72: if sl>1 then sl:=sl-1 else sl:=KItems;

       end

     end

   end;

 until ((c=#13) and (sl=6) or (c=#27));

 textattr:=7;

 clrscr;

end.

Модуль ph

unitph;

interface

usescrt;

type

 town= array [1..20] of string;       {Данные о городах}

 road= array [1..200] of record       {Данные о дорогах}

   a:integer;

   b:integer;

 end;

 vec=array [1..20] ofinteger;      {Данные о пройденных городах}

var

 t:town;                             {Данные о городах}

 nt:integer;                         {Число городов}

 r:road;                             {Данные о дорогах}

 nr:integer;                         {Число дорог}

 fv:vec;                             {Вектор пройденных городов}

 nfv:integer;                        {Количество городов}

procedureInputData;

procedureOutputData;

procedureSave;

procedureLoad;

procedurefindnext(a:vec; tv:integer; nv:integer; lv:integer);

procedureFindPath;

implementation

{Вводданных}

procedureInputData;

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(n<>0) 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 n<>0 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 sl<nt then sl:=sl+1 else sl:=1;

           #72: if sl>1 then sl:=sl-1 else sl:=nt;

         end

       end

     end;

   until (c=#27);

 end;

end;

{Выводданных}

procedureOutputData;

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;

{Запись данных в файл}

procedureSave;

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;

{Чтениеиз файла}

procedureLoad;

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 — Количество пройденных городов}

procedurefindnext(a:vec;tv:integer;nv:integer;lv:integer);

var

 i:integer;                           {Счетчик}

begin

 a[tv]:=lv;                        {Устанавливается в векторе

                                   флаг, что город tvпройден}

  if (tv=nv)then begin

  {Еслидостигнут необходимый город}

    if((lv+1)<nfv)or(nfv=0) then begin

{Еслинайден первый либо более короткий маршрут — он становится найденным}

      nfv:=lv+1;

     fv:=a;

   end;

 end else begin

{Иначе — просмотр всех городов, в которые можно добраться из данного}

    fori:=1 to nr do

{Еслигород еще не учитывался — запуск для него той же самой функции}

      if((r[i].a=tv)and(a[r[i].b]=0)) then findnext(a,r[i].b,nv,lv+1);

{Просмотр,но для дорог, где текущий город учитывался как второй}

    fori:=1 to nr do

{Еслигород еще не учитывался — запуск для него той же самой функции}

      if((r[i].b=tv)and(a[r[i].a]=0)) then findnext(a,r[i].a,nv,lv+1);

 end;

end;

{Нахождениепути}

procedureFindPath;

var

 i:integer;                       {Счетчик}

 j:integer;                       {Счетчик}

 n:integer;                       {Исходный город}

 sl:integer;                      {Выбираемый город}

 c:char;                         {Считанный с клавиатуры символ}

 v:vec;                           {Вектор для начала рекурсии}

begin

{Изначальнопервый город не выбран}

  n:=0;

  sl:=1;

 nfv:=0;                           {Маршрут не найден}

{Циклзапроса городов и вывода результатов}

  repeat

   textattr:=7;

   clrscr;

  {Выводпоясняющей надписи}

   gotoxy(2,20);

    if(n=0) then write(' Выберите начальный пункт')

     else writeln(' Выберите конечный пункт ');

  {Вывод списка городов}

   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 (n<>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;                       {Ввод символа с клавиатуры}

    casec of

     #13: begin

     {Либо фиксируется начальный город}

        if n=0 then n:=sl elsebegin

       {Либо убираетсяошибочно выбранный город}

         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 sl<nt then sl:=sl+1 else sl:=1;

         #72: if sl>1 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.

еще рефераты
Еще работы по информатике, программированию