0 / 0 / 0
Регистрация: 09.03.2016
Сообщений: 4
|
||||||
1 | ||||||
Прохождение лабиринта с использованием рекурсии09.03.2016, 17:15. Показов 12985. Ответов 9
Помогите написать программу: Реализуйте рекурсивный алгоритм нахождения пути из произвольного исходного пункта лабиринта до заданного выхода.
Принцип следующий: Лабиринт есть множество перекрестков, связанных между собой. Предположим, что каждый перекресток имеет три атрибута, определяющих возможность перемещения налево, прямо и направо. Если значение некоторого атрибута равно единице, то движение в данном направлении возможно. Нуль показывает, что движение в данном направлении заблокировано. Три нулевых значения атрибутов перемещения из некоторого перекрестка представляют тупик. Проход по лабиринту считается успешным при достижении точки “Выход”. Процесс поиска выхода включает ряд рекурсивных шагов. В каждом перекрестке необходимо исследовать возможные варианты. Если возможно, сначала следует пойти налево. Достигнув очередного перекрестка, необходимо снова рассмотреть варианты и попытаться пойти налево. Если выбор левого направления заводит в тупик, следует отступить на один шаг назад и выбрать движение прямо, если это направление не заблокировано. Если этот выбор заводит в тупик, вновь необходимо отступить на один шаг и пойти направо. Если все альтернативы движения из данного перекрестка ведут в тупики, следует вернуться к предыдущему перекрестку и сделать новый выбор. Если произошел возврат к исходной точке, и из нее нет новых путей, задача поиска выхода из лабиринта не имеет решения. Вот что-то написал, но дальше не знаю как:
0
|
09.03.2016, 17:15 | |
Ответы с готовыми решениями:
9
Определить сумму элементов данного массива с использованием цикла и с использованием рекурсии Сумма квадратов чисел с использованием рекурсии Вычисление факториала с использованием рекурсии - найти ошибку в коде Помогите найти ошибку в рекурсии, или переписать программу с использованием List |
5 / 5 / 7
Регистрация: 09.03.2016
Сообщений: 89
|
|
09.03.2016, 18:01 | 2 |
если нет задачи найти кратчайший путь, я бы для поиска выхода исопльзовал древний как мир, метод "левой руки".
суть в том, что человек касается рукой одной стены и идет все время держась за нее. так он обойдет все стены лабиринта и дойдет к выходу. ну либо вернется на место. т.е. проверяем текущее положение, и сосденюю клетку. если упираемся в стену, делаем поворот на 90 градусов. Всё, больше ничего ненадо для поиска. в тупике он повернется один раз, проверит, шаг сделать не может (или может, если "широкий кориодор". и так обходим всё. но это для условия что лабиринт именно лабиринт коридоров. http://image.slidesharecdn.com... 13-728.jpg
0
|
0 / 0 / 0
Регистрация: 09.03.2016
Сообщений: 4
|
|
09.03.2016, 18:09 [ТС] | 3 |
0
|
979 / 874 / 350
Регистрация: 26.04.2012
Сообщений: 2,647
|
|||||||||||
09.03.2016, 23:40 | 4 | ||||||||||
Мой вариант:
Класс "Лабиринт":
0
|
979 / 874 / 350
Регистрация: 26.04.2012
Сообщений: 2,647
|
|
09.03.2016, 23:42 | 5 |
Код особо не отлаживался, местами, возможно, говнокод, но вроде бы все работает
0
|
0 / 0 / 0
Регистрация: 09.03.2016
Сообщений: 4
|
|
10.03.2016, 14:25 [ТС] | 6 |
а можешь архивом кинуть?
Добавлено через 1 минуту и можешь сделать это в консоли, как у меня было?
0
|
979 / 874 / 350
Регистрация: 26.04.2012
Сообщений: 2,647
|
|
10.03.2016, 14:29 | 7 |
SL3W, а нафига это все лепить в консоль? Можно, конечно, и там отобразить, но так неудобно же.
Чего тут кидать-для работы достаточно просто скопипастить код в новый проект. Он не требует расстановки каких-либо контролов. Кнопку я тупо забыл убрать.
0
|
0 / 0 / 0
Регистрация: 09.03.2016
Сообщений: 4
|
||||||
11.03.2016, 11:11 [ТС] | 8 | |||||
да мне именно в консоли надо
Добавлено через 4 часа 32 минуты Есть новый вариант, но все равно работает не полностью
0
|
979 / 874 / 350
Регистрация: 26.04.2012
Сообщений: 2,647
|
|||||||||||
11.03.2016, 15:27 | 9 | ||||||||||
Сообщение было отмечено SL3W как решение
Решение
Ок, никаких винформ, только консоль, только хардкор
Program.cs
2
|
979 / 874 / 350
Регистрация: 26.04.2012
Сообщений: 2,647
|
|
11.03.2016, 15:30 | 10 |
Класс Labyrinth не изменился.
0
|
11.03.2016, 15:30 | |
11.03.2016, 15:30 | |
Помогаю со студенческими работами здесь
10
Определение суммы квадратов последовательных целых чисел с использованием рекурсии (перевести с псевдокода) Прохождение лабиринта с использованием стека Прохождение лабиринта Прохождение лабиринта Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |