Цель работы:

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

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

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

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

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

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

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 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
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 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;
{
Вывод

данных
}

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)<nfv)or(nfv=0) then begin

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

      nfv:=lv+1;

      fv:=a;

    end;

  end else begin

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

    for i:=1 to nr do

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

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

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

    for i:=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;
{
Нахождение

пути
}

procedure FindPath;

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

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