|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
26.04.2009, 12:24 | #1 |
Пользователь
Регистрация: 18.12.2008
Сообщений: 19
|
посмотрите пожалйуста. что посоветуете,с чего начать?
на плоскости расположено N точек. имеется робот,который двигается следующим образом. стартуя с некоторой начальной точки и имея некоторое начальное направление, робот движется до первой встреченной точки на его пути,изменяя в ней свое текущее направление на 90 градусов, т е поворачивая налево или направо. После этого он продолжает движение аналогично. Если робот достиг начальной точки, либо не может достичь новой точки ( которую он еще не посещал), то он останавливается. Определить,может ли робот посетить все N точек,если:а) Определены начальная точка и направление робота; б)опредлена начальная точка,а направление робота можно выбирать; в) начальную точку и направление робота можно выбирать.
координаты точек - целые числа, угол измеряется в радианах относительно оси ОХ. |
22.05.2009, 23:06 | #2 |
Пользователь
Регистрация: 18.12.2008
Сообщений: 19
|
Рассмотрим только случай, когда роботы двигаются только параллельно координатным осям, в других случаях можно сделать преобразование координат.
Легко понять, что если рассмотреть точку, имеющую наибольшую координату Y, причем самую левую (т.е. наименьшую координату Х, если таких несколько), то для нее существует только 2 возможность быть пройденной роботом: робот должен прийти из ближайшей точки А снизу и пойти в ближайшую точку Б справа или наоборот. В любом случае эти 2 отрезка фиксированы для робота. Теперь те же рассуждения можно провести и для точек Б и точки, находящейся правее Б, а также для самых нижних, левых и правых точек. Окончательно получается, что возможный проход робота строго фиксирован. Если упорядочить точки по горизонталям (вертикалям), то первая точка горизонтали (вертикали) должна соединятся со второй, третья с четвертой и т.д. Понятно, что если получившаяся фигура связна (цикл), то решение существует для случаев 2. и 3., а для случая 1. нужно проверить, в нужном ли направлении стоит робот. Однако есть одна трудность в случае, когда существуют горизонталь и вертикаль, содержащие нечетное число точек, а обход существует. Это возможно только в случае, когда это стартовая точка обхода, причем она находится в 'нечетной' горизонтали и вертикали. Удалив ее, можно воспользоваться предыдущей процедурой, при этом фиксированные отрезки не должны пересекаться в удаленной точке. можете пожалуйста помочь хотя бы с началом...вообще не знаю с чего начинать!=(( |
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
С чего начать? | Habarova | Помощь студентам | 3 | 26.02.2009 21:53 |
с чего начать? | jackpatriot | Свободное общение | 3 | 31.12.2008 16:27 |
незнаю с чего начать... а начать очень нужно | ОСЯНЯ | Помощь студентам | 2 | 26.11.2008 20:08 |
что посоветуете против ботов | netoro | PHP | 3 | 10.11.2008 10:03 |
С чего начать | Spirit_of_net | Помощь студентам | 1 | 05.11.2007 13:58 |