43450

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

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

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

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

Русский

2013-11-06

88.5 KB

8 чел.

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


 

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

7065. Разработка модуля информационной системы Амортизация оборудования 79.5 KB
  Разработка модуля информационной системы Амортизация оборудования Цель лабораторной работы: приобретение практических навыков создания пользовательских форм для разработки модуля информационной системы Амортизация оборудования. Краткие теоретическ...
7066. Шлицевые соединения 65.5 KB
  Шлицевые соединения Шлицевым называется разъемное соединение составных частей изделия с применением пазов (шлицев) и выступов. Шлицевые соединения бывают подвижные и неподвижные. Детали шлицевого соединения (вал и втулка) показаны на рисунке.. Шлице...
7067. Определение основных показателей погрешности вольтметра 46.53 KB
  Определение основных показателей погрешности вольтметра 1. Цели работы: - ознакомление с принципами измерений напряжений в электрических цепях - приобретение навыков по установлению рабочих метрологических характеристик прибора при измерении ...
7068. Троллинг как тип коммуникативного поведения в Интернете (структура и функции) 1.49 MB
  Троллинг как тип коммуникативного поведения в Интернете (структура и функции) Введение Настоящая диссертационная работа посвящена изучению языковых аспектов троллинга как одной из форм коммуникативного поведения в веб-пространстве. Исследование пров...
7069. Разработка отчетов используя средства Microsoft Access 280.5 KB
  Разработка отчетов Цель работы: Используя средства Microsoft Access, приобрести навыки разработки отчётов для вывода данных из таблиц базы данных на печать. Создание отчета  1. Создадим отчет с помощью автоотчета - Клие...
7070. Проектирование конструкций металлорежущих инструментов 220.5 KB
  Введение Машиностроение - отрасль промышленности, тесно связанная с изготовлением деталей, узлов машин и оборудования различного назначения, от использования которых в значительной степени зависит интенсивность развития всего народно-хозяйственного...
7071. Изучение микроструктуры и механических свойств белых и серых чугунов 119 KB
  Изучение микроструктуры и механических свойств белых и серых чугунов. Цель работы - изучение превращений, проходящих в железоуглеродистых сплавах при реализации метастабильного и стабильного равновесий, и установление взаимосвязи структуры и механ...
7072. Моделирование разброса выходного параметра устройства РЭС и ЭВС методом статистических испытаний 174.95 KB
  Моделирование разброса выходного параметра устройства РЭС и ЭВС методом статистических испытаний Цель работы. Определить закон распределения выходного параметра устройства РЭС и ЭВС методом статистического моделирования (методом Монте-Карло). По пол...
7073. Разработка подачи стола продольно-строгального станка 438 KB
  Введение К современным металлорежущим станкам предъявляются следующие основные требования: возможно большая производительность при достаточной точности формы и размеров, а также чистоты поверхности обрабатываемых на станке изделий прост...