How to become an author
Search
Write a publication
Pull to refresh

Comments 36

Ну вроде один из самых простых алгоритмов — идти вдоль стенки
This comment wasn’t rated yet0
_____
|В   |
|  П |
|____|

Идите (простите за кривизну лабиринта)
Total votes 1: ↑1 and ↓0+1
это не лабиринт на «картинке», просто комната.
Total votes 1: ↑0 and ↓1-1
Ну, видимо, имеется в виду случай, когда приз лежит на у стенки, а посередине комнаты. Если идти вдолль стенки, на приз не наткнемся.
Total votes 1: ↑1 and ↓0+1
Лабиринт 3х3, без перегородок. Приз в центре, Вы у стенки.
This comment wasn’t rated yet0
Делать шаги в случайном направлении. Так как время бесконечно — когда-нибудь придем :)
Total votes 3: ↑3 and ↓0+3
Хороший вариант. Но что делать, если у нас нет датчика случайных чисел, чтобы шагать случайно?
Total votes 2: ↑1 and ↓10
Какие ещё ограничения на алгоритм, огласите уж сразу.
This comment wasn’t rated yet0
Алгоритм — это последовательность шагов «влево-вправо-вперед-назад».
This comment wasn’t rated yet0
Можно составить карту, и использовать ее, чтобы пройти все клетки (так как у нас нет информации о местоположении приза). Проверить, есть ли вокруг стенки, отметить их на карте. Допустим, с одной стороны стенка, шагнуть в случайном направлении, а два других пометить, чтобы проверить потом. Так продолжать, пока не упремся в тупик, тогда возвратиться к ближайшей клетке, где остались непроверенные направления и т. д., пока не наткнемся на приз.
Total votes 2: ↑2 and ↓0+2
Простите, ошибся в формулировке. Забыл условие, запрещающее такое простое решение (нельзя использовать условные операторы). Пожалуйста, сильно не бейте.
Total votes 3: ↑1 and ↓2-1
Игра «поиски клада»? Для полного сходства осталось добавить телепорты и реки :-)
This comment wasn’t rated yet0
Обходить в глубину, параллельно рисуя карту. Если квадратики можно различать, то на бумаге в клетку получится.
Total votes 1: ↑1 and ↓0+1
Проверять лень, но можно было бы попробовать:
while(not_found){
go_left(m*n);
go_up(m*n);
go_right(m*n);
go_down(m*n);
}
This comment wasn’t rated yet0
Не работает.
_______
|В |
| -|

(полоска 1x2, вы слева, выход под вами)
This comment wasn’t rated yet0
автору, похоже, дали в качестве ДЗ разработать этот алгоритм, а он подключил Хабравчан. )
Total votes 2: ↑2 and ↓0+2
Я знаю решение. Если хотите — могу написать в личку.
Total votes 1: ↑0 and ↓1-1
А рекурсивная программа считается программой конечной длины или нет?
This comment wasn’t rated yet0
Нет. Программа — это просто последовательность инструкций куда пойти (влево/вправо/вперед/назад).
Total votes 1: ↑0 and ↓1-1
Да. Зачем циклы, если нет условий?)
This comment wasn’t rated yet0
Есть подозрение, что для данной задачки рекурсия и циклы –– не более, чем сокращённая форма записи.

Кстати, автор воткнул решение?
This comment wasn’t rated yet0
Похоже, что решение тут плутание по какому-то однообразному маршруту (круг, замысловатая восьмёрка или спираль, а может их комбинация) большое число раз. Больше идей нет.

Я с вами согласен — это развернутый цикл for
Total votes 1: ↑1 and ↓0+1
Угу. Не думаю, что надо замысловатое решение. Небось, можно просто устроить полный перебор всевозможных путей из данной точки. Ограничений на время нет.
This comment wasn’t rated yet0
Можно составить все возможные лабиринты, со всевозможным начальным стартовым положением и положением приза. После этого перебирать их по очереди.
Сначала идем по первому лабиринту до приза. Потом на 2м лабиринте наносим наш предыдущий путь и идем из конечной точки до приза. После этого на третий лабиринт наносим путь из первых двух лабиринтов и идем из новой конечной точки для третьего лабиринта до приза. И так далее.
Так как лабиринт конечен, то количество вариантов конечно.
Total votes 4: ↑3 and ↓1+2
Вот собственно и правильное решение
Total votes 5: ↑1 and ↓4-3
Не понятно какой смысл в нанесении положения приза. проще уже полный обход лабиринта — решение тогда по идее получится меньше по объему.
Вариантов — лабиринт+исходное положение около n2*2(n-1)*(n-1) — то есть очень много )
При учете положения приза еще домножаем на n2, но ходов надо меньше.
Total votes 2: ↑2 and ↓0+2
А как предполагается возвращаться в нужную точку, с которой начинается ваша последовательность ходов для проверяемого лабиринта и точки старта? Ведь если робот не чувствует стен, то просто выполнить последовательность в обратном порядке не достаточно, а телепортация в исходную точку вроде как в условии не обговорена.
This comment wasn’t rated yet0
Возвращаться не надо. Надо брать новый лабиринт с новым начальным расположением и просчитывать в нем весь предыдущий путь, подразумевая «если бы я был в такой начальной позиции, то сейчас я бы оказался в таком месте». После такого просчета обходить новый лабиринт не из исходного состояния, а из нового, модифицированного предыдущим маршрутом.
This comment wasn’t rated yet0
Стоп. А как это вы собрались «просчитывать» если
условия он проверять не умеет, то, что уперся в стену — не замечает
м?
Имхо, «накладывать» не получиться, хотя бы потому, что не все маршруты являются накладываемыми.

Ну, вот, для примера, есть поле 5х5:

Где ваш робот и где приз, думаю, ясно. :)
Предположим, что робот сделал все возможные варианты карты и просчитал все возможные расположения себя и приза. Первый ход он делает на E5 (согласно его первому предположению — приз справа, в ближайшей клетке). После этого он хочет попасть в точку С5 (возможно приз был слева начального положения, в ближайшей клетке), поэтому он двигается в D5, и пытается двинуться в C5 (но ясно, что у него это не получается). Следующая предположительная точка — D4 (т. е. выше на одну клетку его начального положения), а т. к. он не заметил стены, он делает два хода — сначала вправо на своё начальное положение (но на самом деле, на E5) и вверх на D4 (на самом деле, на E4). И вот с данного момента робот «потерялся». Дальше он не сможет позиционировать себя, даже имея правильную карту стен.

Возможно, в конце концов, после всех движений он таки возьмёт приз, но эта возможность не равняется 100% потому что даже если бы робот точно знал своё положение на карте, он всё равно бы запутался (как я выше показал). А это может значить, что или я где-то допустил ошибку (к сожалению, частенько бывает), или же ваше решение не правильное.

Сможете написать программу (конечной длины) для этого варианта, без использования условий (а значит и циклов) согласно своим рассуждениям и условиям задачи? Я, например, так точно не представляю как это сделать.
Total votes 1: ↑1 and ↓0+1
Назовем конфигурацией лабиринта набор «стены, положение робота, положения приза».
Конфигураций лабиринта MxN конечное число.
Пронумеруем их.
Идем так, чтобы добраться до приза, если первая конфигурация истинна.
С учетом уже сделанных шагов идем так, чтобы добраться до приза, если вторая конфигурация истинна (мы знаем, куда пытались идти, поэтому, если истинна вторая конфигурация — мы знаем где мы).
С учетом уже сделанных шагов идем так, чтобы добраться до приза, если третья конфигурация истинна.

Ваше рассуждение правильно, если перебирать только свою и приза позиции. Если же перебирать конфигурации стен — такой ситуации не возникнет (да, робот будет часто упираться в стены), т.к. как только мы дойдем до истинной конфигурации, маршрут окажется правильным.
Total votes 1: ↑1 and ↓0+1
А. Значит, правильный вариант ответа — перебор всех возможных конфигураций, с «перепрокладыванием» маршрута, учитывая предыдущие попытки двигаться, по каждой [конфигурации] из них, да?
Только «перепрокладыванием», этим самым, занимается не робот, а мы (по этому и нельзя проверять условия — роботу это делать незачем, мы уже всё должны были просчитать) [именно этот момент я упустил]. Ужас, имхо, но под условия задачи подходит. :)

Спасибо за задачку и разъяснение.
This comment wasn’t rated yet0
Это же простая задачка со всероссийской. Перечисляем все лабиринты и возможные начальные положения нас и приза. Берем одно из них, идем к призу по какому-либо пути. Потом смотрим куда преобразовалось наше множество троек (лабиринт, начальное положение, приз) под действием этой комбинации (если под действием комбинации мы прошли через приз, то эту тройку откидываем). Берем следующий элемент и идем к призу по какому-нибудь пути и.т.д. На каждом шаге мощность множества уменьшается по крайней мере на единицу и потому длина программы будет не больше (количество лабиринтов)*(M*N)^3 (не самопересекающийся путь не может быть длиннее M*N).
Total votes 2: ↑1 and ↓10
Sign up to leave a comment.

Articles

Show the best of all time

Your account

Sections

Information

Services

Support
© 2006–2024, Habr