43450

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

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

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

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

Русский

2013-11-06

88.5 KB

4 чел.

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


 

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

13458. Ввод фактических данных 924 KB
  Ввод фактических данных Фактические данные – это информация о ходе выполнения запланированных работ на основании которой менеджер проекта осуществляет процесс отслеживания. В системе существует несколько способов ввода фактических данных отличающихся друг от дру
13459. Анализ и оптимизация плана работ 1.12 MB
  Урок 4. Анализ и оптимизация плана работ. Для анализа плана работ проекта применяют две классические методики: PERT и метод критического пути СРМ. При анализе стоимости проекта используют настраиваемые поля формулы и группировки создаются формулы с условиями выявляют
13460. Анализ рисков в Microsoft Project 882.5 KB
  Анализ рисков. Анализ опасностей которые могут возникнуть при выполнении составленного плана один из самых интересных и сложных этапов планирования проекта. От того как проведен анализ зависит будет ли проект успешно завершен. В этом уроке вы научитесь определять
13461. Метод освоенного объема 1.38 MB
  Лабораторная работа Метод освоенного объема Для определения состояния проекта методом освоенного объема используется три величины: Базовая стоимость запланированных работ БСЗР обозначает сводную стоимость работ которые должны были быть осуществлены к текущем
13462. Совместное использование ресурсов 906.5 KB
  Лабораторная работа Совместное использование ресурсов Одновременное управление несколькими проектами в рамках организации осложняется тем что сотрудники и материальные ресурсы должны назначаться на задачи так чтобы назначения одних проектов не противоречили друг...
13463. Подготовка отчетов. Статистика проекта 2.45 MB
  Лабораторная работа Подготовка отчетов Статистика проекта Самым простым отчетом содержащим обобщенные данные о проекте является окно статистики проекта изображенное на рис.48. Рис.48.Статистика проекта Это окно открывается кнопкой Статистика из окна сведени
13464. МАГНИТНОЕ ПОЛЕ 103.67 KB
  ЛАБОРАТОРНАЯ РАБОТА № 1 Тема: МАГНИТНОЕ ПОЛЕ Цель работы: знакомство с моделированием магнитного поля от различных источников. экспериментальное подтверждение закономерностей для магнитного поля прямого провода и кругового витка контура с током. эксперим...
13465. ЭЛЕКТРОМАГНИТНАЯ ИНДУКЦИЯ 44.27 KB
  Лабораторная работа № 2 Тема: ЭЛЕКТРОМАГНИТНАЯ ИНДУКЦИЯ Цель работы: знакомство с моделированием явления электромагнитной индукции ЭМИ. экспериментальное подтверждение закономерностей ЭМИ. Бригада №____. Ход работы: Закрыли окно теории нажав...
13466. РАБОТА В СИСТЕМЕ EGROUPWARE 2.04 MB
  РАБОТА В СИСТЕМЕ EGROUPWARE. Управление проектом Внедрение программы 1С Предприятие 8.1 в торговом предприятии с помощью web – ориентированной системы Для начала работы регистрируемся Администратором для входа в систему. Далее входим в систему на вкладку Администрирован...