43450

Алгоритм, вывести путешественников, попавших в лабиринт, к выходу

Практическая работа

Информатика, кибернетика и программирование

Основной блок программы Из процедуры pint_grph отвечающая за прорисовку всего графа будет представлена только та часть которая ответственна за корректный ход пользователя и включает в себя: отображение ходов непосредственно в копированной матрице _C; запись в массив вершин из которых мы попали первый раз в данную...

Русский

2013-11-06

88.5 KB

12 чел.

7

Министерство образования Российской Федерации

Сибирский государственный технологический университет

Факультет: Автоматизации и информационных технологий

Кафедра: Системотехники

Расчетно – графическая работа

по курсу «Дискретная математика»

Проверила:

                            Иванилова Т.Н.

            (подпись)

                        (оценка, дата)

Разработал:

студент гр. 21 – 6

                                 Сучков Д.Н.

                  (подпись)

Содержание

[1] Содержание

[2] 1. Формулировка задачи

[3] 2. Формулировка в терминах теории графов и соответствующий алгоритм

[4] 3. Основной блок программы

[5] 4. Результаты расчетов

[6] 5. Список использованных источников

1. Формулировка задачи

Вариант 9. Вывести путешественников, попавших в лабиринт, к выходу. Лабиринт представляет собой совокупность коридоров и перекрестков. Местом начала пути может быть любой из имеющихся перекрестков.

2. Формулировка в терминах теории графов и соответствующий алгоритм

Поиск маршрута в неориентированном графе.

Алгоритм Терри поиска маршрута в связном графе G (V, X), соединяющего заданные вершины v, w  V.

Исходя из v, осуществлять последовательный переход от каждой достигнутой вершины к смежной ей вершине, руководствуясь следующими правилами:

  1.  Идя по произвольному ребру, всякий раз отмечать направление, по которому оно было пройдено.
  2.  Исходя из v всегда следовать только по тому ребру, которое не было пройдено, или было пройдено в противоположном направлении.
  3.  Исходя их всякого v, по первому заходящему в v ребру, идти лишь тогда, когда нет других возможностей.

3. Основной блок программы

Из процедуры paint_graph, отвечающая за прорисовку всего графа, будет представлена только та часть, которая ответственна за корректный ход пользователя и включает в себя:

  •  отображение ходов, непосредственно в копированной матрице (_C);
    •  запись в массив вершин из которых мы попали первый раз в данную (Zah_reb[N_ver]);

For I := 1 to 100 do zah_reb [i] := 0;

last_ver := N_vhod;

m := 0;

Repeat

   out:

   str (last_ver, last);

   enter_ver2 := enter_ver + raz + ') ' + last + ' -> ';

   Repeat

       Sum_ver := 0;

       _go := false;

       Enter_digit(maxX, maxY, n, enter_ver2, N_ver, _exit); {ввод следующей вершины}

       if _exit then begin

           clear_help (maxX,maxY,ost);

           exit;

       end;

       for i := 1 to n do sum_ver := sum_ver + _c[last_ver,i]; {вычисление ходов из данной вершины}

       {проверка на то, что если имеются ходы, то не является ли он заходящим в вершину}   

       if (_c[last_ver,N_ver] = 1) and (sum_ver > 1) then

           if N_ver <> zah_reb[last_ver] then _go:=true else

             begin

                 clear_help(maxX, maxY, ost);

                 setcolor(lightred);

                 outtextXY(maxx div 2, maxy-25,error2); {печать: «Заходящее ребро. Хода нет.»}

                 readkey;

                 clear_help(maxX, maxY, ost);

                 goto out;

             end

       else         {проверка на то, что нет возможных путей, кроме как заходящего ребра в вершину}

       if (_c[last_ver,N_ver] = 1) and (sum_ver = 1) then _go:=true else

         begin

             clear_help(maxX, maxY, ost);

             setcolor(lightred);

             outtextXY(maxx div 2, maxy-25,error1); {печать: «Ребро пройдено. Хода нет.»}

             readkey;

             clear_help(maxX, maxY, ost);

             goto out;

       end;

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

       if _go then _c[last_ver,N_ver] := 0;

   until _go;

   {если в данной вершине нет заходящего ребра, то запишем в массив вершину из которой попали в данную, нарисуем окружность на этом ребре}

   if zah_reb[N_ver] = 0 then begin

       zah_reb[N_ver] := last_ver;

       diag:= round ( sqrt(abs(y[last_ver]-y[N_ver]) + abs(x[last_ver]-x[N_ver]) ));

       x0 := round ( x[N_ver] - (rad_zah)*(x[N_ver] - x[last_ver])/diag );

       y0 := round (y[N_ver] + (rad_zah)*(y[last_ver]-y[N_ver])/diag );

       setcolor(red);

       circle(x0, y0, 3);

   end;    

   {рисуем ход в данную вершину по ребру (обозначение: стрелка)}

   diag:= round ( sqrt(abs(y[last_ver]-y[N_ver]) + abs(x[last_ver]-x[N_ver]) ));

   x0 := round ( x[N_ver] - (rad_arr)*(x[N_ver] - x[last_ver])/diag );

   y0 := round (y[N_ver] + (rad_arr)*(y[last_ver]-y[N_ver])/diag );

   x1 := round ( x[N_ver] - (rad_plus)*(x[N_ver] - x[last_ver])/diag );

   y1 := round (y[N_ver] + (rad_plus)*(y[last_ver]-y[N_ver])/diag );

   setlinestyle(0,0,3);

   setcolor(yellow);

   line(x0,y0,x1,y1);

   setlinestyle(0,0,1);

   last_ver := N_ver;

until last_ver = N_vihod;  {выход производиться тогда, когда данная вершина является выходом}

4. Результаты расчетов

При запуски программы появляется меню,  состоящее из следующих подпунктов:

  •  Задать матрицу;
  •  Изменить матрицу;
  •  Начать поиск;
  •  Выход;

Войдем в первый из них: «задать матрицу», затем вводим размерность матрицы (2 – 9) и, пользуясь клавишами: «1» и «0» задаем ребра графа.

Рис. 1 Изменение матрицы

Далее, после ввода матрицы заходим в пункт «начать поиск», который позволяет нам найти выход из лабиринта, представляющий неориентированным графом.

Рис. 2 Выход из лабиринта

5. Список использованных источников

  1.  Иванилова Т.Н., Крайченкова О.В. Дискретная матаматика. Сборник заданий с примерами решений. Красноярск: СибГТУ, 2000. – 47с.

  1.  Приложение: Turbo Pascal 7.0


 

А также другие работы, которые могут Вас заинтересовать

28478. Найпростішіоматематичніомоделі математичного програмування 17.03 KB
  Побудова математичної моделі: Позначимо: хі - кількість одиниць продукції виду Пі, заплановано: до випуску (і=1,2); z - сумарний прибуток при реалізації запланованої виробничої програми. Для змінних x1, x2, очевидно, виконуються нерівност
28480. Стандартні форми задач лінійного програмування 27.15 KB
  Існуючі методи розв'язування ЗЛП передбачають певні вимоги на систему основних обмежень в силу чого розрізняють дві стандартні форми ЗЛП: Іа з обмеженнямирівняннями в такому вигляді розв'язуються задачі з допомогою універсальних методів реалізованих на персональних комп'ютерах; ІІа з обмеженняминерівностями використовується в теоретичних дослідженнях і для геометричної ілюстрації; Лема 1. Будьяка задача ЛП може бути приведена до рівносильної задачі ЛП яка записана в 1й стандартній формі. Будьяка ЗЛП може бути зведена до...
28481. Основні властивості розв’язків задач лінійного програмування 19.37 KB
  Основні властивості розвязків задач лінійного програмування. Множина розв'язків нерівності заповнює суцільно одну із півплощин на які ділить площину гранична пряма аі1 x1 ai2 Х2= b Леми 1 та 2 дозволяють сформулювати:Властивість 1. Сукупність допустимих розв'язків задачі ] 2 заповнює опуклий многокутник або є порожньою множиною. Оптимальним розвязком задачі ] 2називається такий її допустимий план на якому цільова функція 1 досягає екстремального найбільшого або найменшого значення.
28482. Алгоритм графічного методу розв’язування задач лінійного програмування 11.86 KB
  Алгоритм графічного методу розвязування задач лінійного програмування. Графічний метод ґрунтується на геометричній інтерпретації ЗЛП і застосовується в основному при розв'язуванні задач в R2 і тільки деяких задач трьохмірного простору оскільки в R3 досить важко побудувати многогранник допустимих розв'язків що утворюється в результаті перетину півпросторів. Якщо ж ЗЛП записана в І стандартній формі система рівнянь якої містить n невідомих і m лінійно незалежних рівнянь то вона також може бути розв'язана графічним методом всякий раз коли...
28484. Ідея симплексного методу та його геометрична інтерпретація 14.2 KB
  Проте задачі лінійного програмування які доводиться розв'язувати на практиці характеризуються великими числами m та n а кількість опорних планів обмежена зверху числом Тому доцільніше було б вказати таку схему послідовного покрашення опорного плану що при переході від одного опорного плану вершини многогранника допустимих розв'язків до іншого опорного плану іншої вершини отримується збільшення цільової функції при максимізації функції 1 і зменшення її при мінімізації функції 1. Саме...
28485. Алгоритм симплексного методу 23.31 KB
  Заповнення початкової симплекстаблиці перша ітерація Таблиця 1 В рядках 1 3 записані відповідні рівняння системи 12 при цьому спочатку права частина в стовпці опорний план а потім коефіцієнти при відповідних змінних. Отже з початкової таблиці безпосередньо виписується початковий опорний план: Х1 оп = 0; 0; 182; 316; 238. В нульовому рядку міститься інформація про цільову функцію: для зручності функція 11 розглядається формалізовано як рівняння z 18х1 16х2 = О...
28486. Постановка транспортної задачі та її математична модель 31.64 KB
  Постановка транспортної задачі та її математична модель. Побудуємо математичну модель закритої транспортної задачі Позначимо через xij кількість одиниць вантажу запланованого до перевезення від iго постачальника до jго споживачаz сумарну вартість запланованих перевезень Для зручності умову задачі запишемо у вигляді таблиці табл 1 яку надалі будемо називати транспортною сіткою При цьому постачальників скорочено позначимо літерою П а споживачів С Таблиця 1...