Программирование и комп-ры

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



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


                                  Введение

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

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


   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;
        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 (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 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.


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