06/03 Моделирование процессов обработки двумерных массивов "Путь в лабиринте"

Одним из самых простых правил для прохождения лабиринта является правило "одной руки": двигаясь по лабиринту, надо все время касаться правой или левой рукой его стены. Этот алгоритм, вероятно, был известен еще древним грекам. Придется пройти долгий путь, заходя во все тупики, но в итоге цель будет достигнута. Хотя у этого правила и есть один недостаток, но о нем мы поговорим позже.
Попробуем описать робота, действующего в соответствии с правилом "правой руки".
В начале своей работы робот должен найти стену, по которой он будет следовать. Для этого он может просто двигаться вперед, пока не упрется в преграду.
После того как робот наткнулся на препятствие, он начинает передвигаться в соответствии с правилом "правой руки".
Двигаясь вдоль стены, робот следит, есть ли проход справа. Если проход есть, робот должен идти по нему, чтобы не оторваться от стены справа.
Если прохода нет - впереди стена - робот поворачивает налево. Если прохода снова нет, он еще раз поворачивает налево, таким образом разворачиваясь на 180 градусов, и идет в обратном направлении.
Блок-схема алгоритма для робота, работающего по правилу "правой руки", представлена на рисунке.

Попробуем проверить работу данного алгоритма и напишем для него программу. Для этой цели обратимся к среде программирования GameLogo. Эта среда является удобным средством для моделирования различных алгоритмов, связанных с управлением роботами. В ней есть исполнитель черепаха, который по своей сути является не чем иным, как самым настоящим роботом. Черепаха располагает очень удобным набором команд - вперед, направо, налево, назад. Кроме того, в центре черепахи есть датчик, принимающий значение от 0 до 100, в зависимости от тона поверхности, на которой она находится.
Диалект языка Лого, который мы будем использовать, очень прост и похож на Basic. Познакомиться с командами языка можно здесь. А бесплатно скачать среду программирования GameLogo - здесь. Размер дистрибутива невелик - всего 1 Mb.
В архиве с GameLogo есть фоны с лабиринтами, одним из которых мы и воспользуемся.

Файл maze1.gif

В самом начале программы дадим команду черепахе, чтобы она подняла перо (по умолчанию черепаха оставляет после себя след).
Размер поля - 800 на 600 точек. Исходное положение для черепахи находится в месте с координатами 115, 545 (белый квадрат).
Цвет дорожек лабиринта - светлый, на них датчик будет принимать значения больше 50. Цвет стен лабиринта - темный, значение датчика будет меньше 50. Выход из лабиринта представлен черным квадратом, значение датчика над которым будет равно 0.
Объявим переменную флаг, с помощью которой будем контролировать, достигнут ли выход из лабиринта.
Напишем программу и запустим ее с помощью большой красной кнопки с надписью "Выполнить".
переменная флаг фон = maze1.gif

поднять перо

место 115, 545

' поиск первой стены

повторять пока датчик > 50 { вперед 12

}

' правило правой руки

повторять пока флаг = 0 {

направо 90

вперед 12

если датчик = 0 то

флаг = 1

иначе если датчик < 50 то

назад 12

налево 90

вперед 12

если датчик < 50 то

назад 12

налево 90

конец условия

}

пиши "цель достигнута"

Если известно, что у лабиринта нет отдельно стоящих стенок, то есть нет замкнутых маршрутов, по которым можно возвращаться в исходную точку, то такой лабиринт называют односвязным и его всегда можно обойти полностью, применив правило "одной руки".
Если же лабиринт содержит отдельно стоящие стенки, то, применяя правило "одной руки", не всегда можно пройти все коридоры и тупики. Лабиринты с отдельно стоящими стенками и с замкнутыми маршрутами называются многосвязными. При этом многосвязные лабиринты можно разделить на две группы: без "петли" вокруг цели (замкнутый маршрут не проходит вокруг цели) и с замкнутой "петлей" вокруг цели (цель можно обойти по замкнутому маршруту).
Д/з: учебник (часть 2) стр. 350-356

09/03 Задачи по моделированию процессов обработки двумерных массивов «Авиаперелеты»

1) создать txt файл с данными из таблицы стр. 352. Дать файлу имя avia.txt

2) создать программный код в среде VB:

Открыть программу Word,
сохранить документ в формате "с поддержкой макросов" в ту же папку, куда сохранили ania.txt,
перейти на ленте на вкладку "Разработчик",
активировать Visual Basic,
дать команду Insert→Module
вставить в появившееся окно программный код:

Sub avia1()
Dim name$(1 To 6)
n = 6
Dim t(1 To 6, 1 To 6)
Dim t2(1 To 6, 1 To 6)
Open "avia.txt" For Input As #1
For i = 1 To n
For j = 1 To n
Input #1, t(j, i)
Next j
Next i
Close #1
For j = 1 To n
For i = 1 To n
MsgBox ((j) & "-я строка " & " элемент " & (i) & ": " & (t(i, j)))
Next i
Next j
End Sub