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


 

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

80943. Види історичних уявлень та їхня роль у процесі формування історичних знань 34.74 KB
  Відповідно до змісту історичного матеріалу і характеру усвідомлення його учнями розрізняють види історичних уявлень: 1 кількісні; 2 локальні просторові; 3 хронологічні часові; 4 образні; 5 логічні. Створення і збагачення історичних уявлень у свідомості дитини має велике виховне значення. Процес формування історичних уявлень у навчанні є достатньо складним.
80945. Обєкт і придмет методики історії як науки 29.56 KB
  Предмет методики - історія як шкільна дисципліна, процес навчання історії. Обєктом дослідження методики виступає процес навчання, а предметом - внутрішні закономірності взаємодії головних чинників процесу навчання історії в якості навчального предмета
80946. Методичні прийми роботи з підручником при вивченні темп: «Давній Єгипет» 32.39 KB
  Один з прийомів може бути таким: скласти план по темі Стародавній Єгипет. Зокрема складання плану для підзаголовків Землеробство основне заняття єгиптян і Початок обробки металів допоможуть учням встановити взаємозв`язок фактів в історії: спочатку змінюється техніка покращуються знаряддя праці виникають нові галузі виробництва і лише тоді відбуваються зміни в соціальній структурі суспільства.
80947. Контроль навчання, його функції, види методи 37.51 KB
  У дидактиці це нагляд спостереження і перевірка успішності учнів. Спостереження за учнями під час занять перевірка їх знань навичок і вмінь зошитів навчальної і практичної діяльності учнів є засобами контролю. Облік успішності передбачає фіксацію результатів контролю у вигляді оцінки Функції контролю перевірки і оцінки навчальних досягнень учнів. Ці функції оцінки знань учнів різнопланові.
80948. Система перевірки знань, умінь, навичок; учнів після вивчення теми «Україна в другій половині XIX століття» 35.42 KB
  Повторити та узагальнити матеріал з даної теми. Хронологічний конкурс Цей конкурс має характер розминки і передбачає знання хронології історичних подій. Командам потрібно розташувати події в хронологічній послідовності і вказати дати, коли вони сталися. Максимальна оцінка за цей конкурс шість балів.(робота з індивідуальними картками)
80951. Характеристика сучасної системи шкільної історичної освіти в Україні 36.25 KB
  Програма шкільних курсів історії. У програмі шкільних курсів історії закладено такі пріоритети. Вивчення історії України. Вивчення історії ХХ століття.