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


 

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

68924. Функції РНР для роботи з MYSQL 100 KB
  Всі параметри функції є необов’язковими, оскільки значення за умовчанням можна прописати в конфігураційному файлі php.ini. Якщо ви хочете вказати інші ім’я MySQL-вузла, ім’я користувача і пароль, ви завжди можете це зробити. Параметр $hostname може бути вказаний у вигляді вузол: порт.
68925. Структура програми в РНР. Стандартний вид РНР-сценарія 87 KB
  Це означає наступне: Обробка PHPкоду проводиться на стороні сервера ще до того як Web-сторінка буде передана браузеру. Виходить що PHP є транслюючим інтерпретатором або інтерпретуючим транслятором як кому більше подобається. Варто відзначити що PHP версії 3 був чистим...
68926. Змінні і типи даних 56.5 KB
  Чому я спожив вираз Практично у всіх Існують і такі мови в яких немає змінних як таких. На щастя РНР не відноситься до таких мов він найзвичайніша мова з погляду наявності змінних. Всі дані з якими працює програма зберігаються у вигляді змінних.
68927. Операції над змінними 43 KB
  Перевірка існування змінної. Знищення змінної. Перевірка існування змінної. Знищення змінної Ви можете запитати а як же арифметичні і інші операції Решта всіх операцій специфічна для конкретного типу змінної.
68928. Вирази та операції в РНР 62 KB
  Вирази є тією «цеглою», з якої складаються РHP-програми. Практично все, що ви пишете в програмі, є виразом. При цьому під виразом розуміється те, що має значення. Можна сказати і по-іншому: все, що має значення, є виразом. Найпростіший вираз — це константа, що стоїть в правій частині оператора...
68929. Рядки. Операції над рядками 36.5 KB
  Обоє операторів echo виведуть рядки. Перший оператор echo виведе рядок Hello, а другою — $s. Між рядками в лапках і в апострофах існує велика різниця. Якщо рядок поміщений в апострофи, то всі символи трактуються як є. Винятки становлять послідовност...
68930. Посилання, умовний оператор 43 KB
  Неважко здогадатися що виведе програма 66. Краще використовувати жорсткі посилання: хоч би виходячи з того що для них потрібний один оператор. Умовний оператор Проблему вибору можна без докорів совісті віднести до глобальних проблем.
68931. Цикли План. Цикли з передумовою. Цикли з постумовою 58 KB
  Цикл дозволяє повторити певну і навіть не визначене коли робота циклу залежить від умови кількість разів якінебудь оператори. Дані оператори називаються тілом циклу они крутитимуться в циклі. Прохід циклу називається ітерацією. Як і С PHP підтримує три види циклів: Цикл з передумовою while...
68932. Форми в HTML-документах. Елементи форм 109.5 KB
  Форма в HTML-документі реалізується тегом-контейнером FORM, в якому задаються всі елементи, що управляють, — поля введення, кнопки і т.д. Якщо елементи, що управляють, вказані поза вмістом тега FORM, то вони не створюють форму, а використовуються для побудови призначеного для користувача...