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


 

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

15445. ОПРЕДЕЛЕНИЕ ЭЛЕКТРОЕМКОСТИ КОНДЕНСАТОРА 352 KB
  ОПРЕДЕЛЕНИЕ ЭЛЕКТРОЕМКОСТИ КОНДЕНСАТОРА Методические указания к лабораторной работе №8 по физике Указания содержат краткое описание рабочей установки и методики определения электроемкости конденсатора методом моста Сотти. Методические указания предназна...
15446. ОПРЕДЕЛЕНИЕ СОСТАВЛЯЮЩИХ ИНДУКЦИИ МАГНИТНОГО ПОЛЯ ЗЕМЛИ 349 KB
  ОПРЕДЕЛЕНИЕ ГОРИЗОНТАЛЬНОЙ СОСТАВЛЯЮЩЕЙ ИНДУКЦИИ МАГНИТНОГО ПОЛЯ ЗЕМЛИ МЕТОДИЧЕСКИЕ УКАЗАНИЯ К ЛАБОРАТОРНОЙ РАБОТЕ №16ПО ФИЗИКЕ Раздел Электричество и магнетизм Указания содержат краткое описание рабочей установки и методику определения горизонтально
15447. ИЗМЕРЕНИЕ УДЕЛЬНОГО СОПРОТИВЛЕНИЯ ПРОВОДНИКА МЕТОДОМ ВОЛЬТМЕТРА-АМПЕРМЕТРА 597 KB
  Измерение удельного сопротивления проводника методом вольтметраамперметра Методические указания к выполнению лабораторной работы № 38 Указания содержат краткое описание рабочей установки и методики определения удельного сопротивления проволоки методом вольтм
15448. Совершенствование практики раскрытия информации 47 KB
  С.В. Лосев Совершенствование практики раскрытия информации При приобретении ценных бумаг на первичном рынке основной задачей инвестора и эмитента является объективная оценка ценности предмета сделки. Однако данная задача решается участниками не одинаково и с разн...
15449. Производные инструменты в коммерческом банке 1.02 MB
  Роль рынка производных инструментов в экономике Сущность и функции срочного рынка Рынок производных инструментов России Коммерческий банк как участник срочного рынка 2 Направления деятельности банков на рынке д
15450. Состояние и перспективы развития закрытых паевых инвестиционных фондов недвижимости 816.5 KB
  Введение Индустрия инвестиционных фондов в нашей стране в последнее десятилетие развивалась в большей степени экстенсивными темпами нежели по пути качественного роста. Практически ежегодно увеличивался объём средств в доверительном управлении российских управляющ
15451. Управление рисками инвестиционных проектов в пищевой промышленности 2.78 MB
  Управление рисками инвестиционных проектов в пищевой промышленности ВВЕДЕНИЕ Актуальность исследования. Опыт развития рыночных отношений показал что инвестирование является важнейшим источником экономического роста финансовой основой прогресса. Объективный...
15452. Східні слов’яни: походження, розселення, соціально-економічний розвиток і культура. Виникнення назви „Русь” 37.5 KB
  Східні слов’яни: походження розселення соціальноекономічний розвиток і культура. Виникнення назви Русь€. Витоки словян вчені відносять до кінця бронзового початку залізного віку. За своїм походженням словяни. автохтонне не прийшле а таке що сформувалося на ц...
15453. Утворення Київської Русі. Основні етапи її розвитку 73.5 KB
  Утворення Київської Русі. Основні етапи її розвитку. Протягом VIII IX ст. словяни розселилися на території Східної Європи. Найбільшими словянськими племенами були: поляни що жили на Середній Наддніпрянщині сіверяни на р. Десна вятичі на Оці на заході від полян дрегов