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


 

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

49196. ПРОЕКТИРОВАНИЕ АНАЛОГО-ЦИФРОВОГО ПРЕОБРАЗОВАТЕЛЯ С USB ВЫХОДОМ 2.14 MB
  Аналого-цифровой преобразователь АЦП согласующий усилитель СУ фильтр нижних частот ФНЧ конвертор преобразователь DCDC гальваническая развязка операционный усилитель ОУ. В ходе курсовой работы необходимо нарисовать функциональную и принципиальную схему аналого-цифрового преобразователя АЦП выбрать микросхему АЦП в соответствии с вариантом тип конвертора USB преобразователи DCDC и микросхемы гальванической изоляции. Задание на курсовую работу В ходе курсового проектирования необходимо разработать функциональную и...
49197. Расчет однофазного сварочного трансформатора 554.54 KB
  Задание на курсовую работу Расчёт электрических величин трансформатора. Расчет конструктивных параметров трансформатора. Расчет основных электрических, магнитных и конструктивных параметров однофазного трансформатора проводится в следующей последовательности
49200. Разработка печатного узла устройства с помощью пакета программ САПР Altium Designer 5.01 MB
  Чтобы создать новую библиотеку необходимо выполнить следующую последовательность действий: Выбрать команду библиотека. выбрать метрическая система единиц единицы Millimetrs ок. в открывшемся окне выбираем Grids выбрать шаг сетки 5 мм.SchLit щелкнуть ПК опции примитивы по умолчанию В списке примитивов выбрать Librry Objects.
49201. Инструментальный цех завода РТО 513.62 KB
  Электрической программой предусмотрено социально-экономическое развитие страны на базе ускорения научно-технического процесса (НТП), а также внедрения энергосберегающих технологий в быту и на промышленных предприятиях.
49202. Десятиразрядный КМОП ЦА преобразователь на 50 МГц с буфером на 75 Ом 280.03 KB
  В нашей статье пропорционально десятиразрядный ЦАП на 50 МГц основан на цепочке резисторов. Конструкция улучшает стандартный метод одинарной цепочки резисторов, используя двойную лестничную архитектуру в матрице форматирования. В лестничную структуру были приняты некоторые изменения, чтобы уменьшить искажения.
49203. Анализ линейной динамической цепи 21.94 MB
  На втором этапе определяем комплексную функцию передачи используя Generl Numbers. Этап третий определяем нули и полюса комплексной функции передачи построение карты полюсов и нулей. Нахождение комплексной функции передачи 3. Нахождение полюсов и нулей функции передачи.
49204. Управление подачей добавок в АКП 226.41 KB
  Разработать микропроцессорную систему управления подачей добавок в агрегат печьковш. Разработать программное устройство управления подачей добавок в агрегат печьковш. АВТОМАТИЗАЦИЯ УСТАНОВОК ВНЕПЕЧНОЙ ОБРАБОТКИ МЕТАЛЛА УПРАВЛЕНИЕ ПОДАЧЕЙ ДОБАВОК В настоящее время имеется достаточно большое количество вариантов оснащения АКП различными устройства подачей добавок.