2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1, 2
 
 Re: Универсальный путевыводитель из лабиринта.
Сообщение16.08.2013, 16:41 
Заслуженный участник
Аватара пользователя


06/04/10
3152
""Хотел бы в единое слово :wink:

Нетрудно придумать порядок, когда это будет неверным.

 Профиль  
                  
 
 Re: Универсальный путевыводитель из лабиринта.
Сообщение16.08.2013, 16:42 
Заслуженный участник
Аватара пользователя


23/08/07
5420
Нов-ск
Sonic86 в сообщении #755236 писал(а):
Если я задачу понял неверно, просьба сформулировать ее по-человечески.
Человеческую формулировку задачи можно начать с объяснения того, что такое "выход из комнаты". Ну, вышел я из комнаты, а дальше что, провалился в открытый космос?

 Профиль  
                  
 
 Re: Универсальный путевыводитель из лабиринта.
Сообщение16.08.2013, 16:58 
Заслуженный участник


08/04/08
8556
TOTAL в сообщении #755251 писал(а):
Человеческую формулировку задачи можно начать с объяснения того, что такое "выход из комнаты". Ну, вышел я из комнаты, а дальше что, провалился в открытый космос?
:lol: Ну если угодно. Т.е. я дошел до выхода и все, дальше в нем остаюсь навсегда: $U(E)=D(E)=L(E)=R(E)=E$, а для остальных точек - как написано.

Кстати, вот такую тему вспомнил (там есть описание путеводителя для одномерной решетки).

 Профиль  
                  
 
 Re: Универсальный путевыводитель из лабиринта.
Сообщение16.08.2013, 17:12 
Заслуженный участник
Аватара пользователя


23/08/07
5420
Нов-ск
Sonic86 в сообщении #755255 писал(а):
TOTAL в сообщении #755251 писал(а):
Человеческую формулировку задачи можно начать с объяснения того, что такое "выход из комнаты". Ну, вышел я из комнаты, а дальше что, провалился в открытый космос?
:lol: Ну если угодно. Т.е. я дошел до выхода и все, дальше в нем остаюсь навсегда: $U(E)=D(E)=L(E)=R(E)=E$, а для остальных точек - как написано.
Тогда нет задачи, ведь у каждой комнаты есть выход, я выхожу через него, конец.

 Профиль  
                  
 
 Re: Универсальный путевыводитель из лабиринта.
Сообщение16.08.2013, 17:45 
Заслуженный участник
Аватара пользователя


08/11/11
5940
Я предполагал, что алгоритм автоматически прерывается, как только мы дошли до выхода.

Предположим, что лабиринт фиксирован и известен. Пронумеруем его комнаты. Из любой комнаты возможен выход, в том числе из первой. Применим алгоритм выхода из первой комнаты. После этого применим алгоритм выхода из комнаты, получающейся из второй комнаты под действием алгоритма выхода из первой комнаты. Это гарантирует нам выход в случае, если мы изначально были в первой или второй комнате. После этого применим алгоритм выхода из комнаты, получающейся из третьей комнаты под действием всего, что было до этого. И так далее. Количество итераций будет в итоге не больше количества комнат.

Если лабиринт заранее неизвестен, то можно перечислить все возможные лабиринты и к каждому применить предыдущий абзац.

 Профиль  
                  
 
 Re: Универсальный путевыводитель из лабиринта.
Сообщение16.08.2013, 18:08 
Заслуженный участник
Аватара пользователя


03/12/11
640
Україна
nikvic, а Вы можете чётко сформулировать задачу и ответить на следующие вопросы?

1) Лабиринт конечен или бесконечен?
2) Известен ли он заранее?
3) Что означает "выйти из лабиринта"? Выйти в какую-то определённую дверь? Должен ли список команд гарантировать, что мы после этого не войдём обратно в эту же дверь или считается, что выполнение команд после такого "выхода" обрывается?

 Профиль  
                  
 
 Re: Универсальный путевыводитель из лабиринта.
Сообщение16.08.2013, 18:37 
Заслуженный участник


08/04/08
8556
g______d в сообщении #755270 писал(а):
Предположим, что лабиринт фиксирован и известен. Пронумеруем его комнаты. Из любой комнаты возможен выход, в том числе из первой. Применим алгоритм выхода из первой комнаты. После этого применим алгоритм выхода из комнаты, получающейся из второй комнаты под действием алгоритма выхода из первой комнаты. Это гарантирует нам выход в случае, если мы изначально были в первой или второй комнате. После этого применим алгоритм выхода из комнаты, получающейся из третьей комнаты под действием всего, что было до этого. И так далее. Количество итераций будет в итоге не больше количества комнат.

Если лабиринт заранее неизвестен, то можно перечислить все возможные лабиринты и к каждому применить предыдущий абзац.
О! Я понял, благодарю :-)

 Профиль  
                  
 
 Re: Универсальный путевыводитель из лабиринта.
Сообщение16.08.2013, 19:32 
Заслуженный участник
Аватара пользователя


06/04/10
3152
Dave в сообщении #755278 писал(а):
nikvic, а Вы можете чётко сформулировать задачу и ответить на следующие вопросы?

1) Лабиринт конечен или бесконечен?
2) Известен ли он заранее?
3) Что означает "выйти из лабиринта"? Выйти в какую-то определённую дверь? Должен ли список команд гарантировать, что мы после этого не войдём обратно в эту же дверь или считается, что выполнение команд после такого "выхода" обрывается?
1/ По умолчанию, "лабиринт" - конечный лабиринт. Исключений не знаю.
2/ Известен. Например, состоит из всех лабиринтиков, с числом комнат не более 666 в каждом :wink:
3/ Оказаться в спецкомнате, где накрыта "поляна" 8-)

 Профиль  
                  
 
 Re: Универсальный путевыводитель из лабиринта.
Сообщение17.08.2013, 07:54 
Супермодератор
Аватара пользователя


20/11/12
5728
nikvic в сообщении #755294 писал(а):
1/ По умолчанию, "лабиринт" - конечный лабиринт. Исключений не знаю.
2/ Известен. Например, состоит из всех лабиринтиков, с числом комнат не более 666 в каждом :wink:
3/ Оказаться в спецкомнате, где накрыта "поляна" 8-)
nikvic, замечание за малосодержательное сообщение.

 Профиль  
                  
 
 Re: Универсальный путевыводитель из лабиринта.
Сообщение17.08.2013, 08:33 
Заслуженный участник
Аватара пользователя


06/04/10
3152
В условии не предполагается, что граф лабиринта связен, а вершин со свойством "выход" может быть много.

 Профиль  
                  
 
 Re: Универсальный путевыводитель из лабиринта.
Сообщение17.08.2013, 11:27 
Заслуженный участник


29/04/12
268
nikvic
Может вы, наконец, сформулируйте чётко условие задачи и что считается её решением?

 Профиль  
                  
 
 Re: Универсальный путевыводитель из лабиринта.
Сообщение17.08.2013, 11:49 
Заслуженный участник
Аватара пользователя


06/04/10
3152
Её решение весьма кратко и точно изложил g______d - 16, 2013 16:14:10.
Полагаю, по нему можно придумать много точных редакций условия.

 Профиль  
                  
 
 Re: Универсальный путевыводитель из лабиринта.
Сообщение18.08.2013, 18:23 
Супермодератор
Аватара пользователя


20/11/12
5728
 ! 
nikvic в сообщении #755397 писал(а):
В условии не предполагается, что граф лабиринта связен, а вершин со свойством "выход" может быть много.
nikvic в сообщении #755443 писал(а):
Полагаю, по нему можно придумать много точных редакций условия.
nikvic, ещё одно замечание за кривую формулировку задачи. Вы же понимаете, что если граф лабиринта несвязен, то в общем случае решения нет.
Впредь убедительная просьба формулировать задачи в олимпиадном разделе точно (в следующий раз буду тему в Карантин уносить).

 Профиль  
                  
 
 Re: Универсальный путевыводитель из лабиринта.
Сообщение18.08.2013, 18:51 
Заслуженный участник
Аватара пользователя


06/04/10
3152
Deggial в сообщении #755802 писал(а):
Вы же понимаете, что если граф лабиринта несвязен, то в общем случае решения нет.

Вы неправы: нигде не сказано о единственности вершины со свойством "выход". Подразумевается понятие выйти из лабиринта - факт.

 Профиль  
                  
 
 Posted automatically
Сообщение04.11.2013, 01:49 
Основатель
Аватара пользователя


11/05/05
4312
 i  Тема перемещена из форума «Олимпиадные задачи (М)» в форум «Олимпиадные задачи (CS)»
Причина переноса: не указана.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 30 ]  На страницу Пред.  1, 2

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group