Удав, Задача на координаты и направление |
1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!
Удав, Задача на координаты и направление |
1qsd |
Сообщение
#1
|
Новичок Группа: Пользователи Сообщений: 11 Пол: Мужской Реальное имя: Kost Репутация: 0 |
Помогите решить вот эту несложную задачу. Преподаватель говорит, что решать её нужно как то через матрицы.
Удав расположен в виде нескольких линий, из которых каждая следущая перпендикулярна предыдущей. Направление каждой линии и её протяженность задаются буквами "L" , "R" и числом. Например 25L15R5 ("25" - длина линии = 25, "L" - поворачивает на 90 градусов влево, "15" - длина линии = 15 , "R" - поворачивает на 90 градусов вправо , "5" - длина линии = 5). Определить, пересечет ли он себя. Сообщение отредактировано: 1qsd - |
Lapp |
Сообщение
#21
|
Уникум Группа: Пользователи Сообщений: 6 823 Пол: Мужской Реальное имя: Лопáрь (Андрей) Репутация: 159 |
Коллеги, я не вполне все же вас понял..
Michael_Rybak, если одно звено полностью включает другое (этот случай ты называешь "касанием"?) то это значит, что подходящие к внутреннему (полностью включенному другим) дадут то, что я называю пересечением (наличие общих точек, включая концы). Поскольку в задаче спрашивается, самопересекается удав или нет - то этого будет достаточно, чтобы ответить "ДА". Вывод программой конкретных пересечений - это моя блажь, отладочная инфа. Другое дело, что у меня в релизации была откровенная ошибка, в результате чего находились несуществующие пересечения - признаю и извиняюсь.. Я просто недописал формулы для пересечения. Сейчас исправлено, код ниже.. Как водится, в результате прога стала только короче . Malice, твой первый тест (10L10L10R10R10R30) я прохожу нормально. А второй (ботинок с красным каблуком) я что-то не пойму.. Напиши его строчкой, плз. Ааааа... понял. Приход обратно сзади... подкрасться тмхой сапой, и... O'kay, подумаю. Остается одна проблема... Вот такая: 10L0L5 То есть звено нулевой длины и поворот назад. Такую ситуацию я не отлавливаю.. Но работаю над этим! const -------------------- я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой |
Lapp |
Сообщение
#22
|
Уникум Группа: Пользователи Сообщений: 6 823 Пол: Мужской Реальное имя: Лопáрь (Андрей) Репутация: 159 |
2 Malice:
Случай с подходом к хвосту сзади лечится добавлением минус-первой точки к массиву координат; ее координаты, как и координаты нулевой точки, нулевые: 0,0. Остальные звенья это нулевое звено не пересечет, так как оно нулевой длины. Соответственно, цикл while нужно начинать с (i+1)mod 2. 2 Lapp: (разговоры самого-с-собой - первый признак помешательства.. ) Проверка на разворот не спасает: разворот может быть долгий: 10L0R0L0L5 Исключать пары нулевых звеньев типа L0R0 ? нет.. Ведь может и не быть пересечения после разворота: 10L0L0L5 - это просто поворот направо.. Неужели Michael_Rybak все же прав (сам того не зная ), и придется проверять параллельные звенья тоже??.. -------------------- я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой |
Lapp |
Сообщение
#23
|
Уникум Группа: Пользователи Сообщений: 6 823 Пол: Мужской Реальное имя: Лопáрь (Андрей) Репутация: 159 |
Неужели Michael_Rybak все же прав (сам того не зная ), и придется проверять параллельные звенья тоже??.. "Долгие повороты" не нужно учитывать никаким специальным образом при исследовании разворота. Дело в том, что последовательность L0R0L0L0 - уже содержит перпендикулярное звено, которое будет учтено. Так что нужно отслеживать только действительный (быстрый) поворот назад, типа 10L0L5. Это я вставил, и оно, вроде, работает, но.. ..Но тут другая проблема вылезает . Действительно, чередующаяся последовательность нулевых звеньев вызовет ложное срабатывание: 10L0R0L0R0L5 - представляет собой прямую линию, но в середине есть три нулевых звена, которые все имеют общую точку с ненулевыми... Вот такая фигня.. Может, запретить нулевые звенья совсем?.. Или убирать их при парсинге.. -------------------- я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой |
Lapp |
Сообщение
#24
|
Уникум Группа: Пользователи Сообщений: 6 823 Пол: Мужской Реальное имя: Лопáрь (Андрей) Репутация: 159 |
2 Lapp:
(а с кем еще и поговорить-то ночью.. ) Вставил блок, убирающий парные повторы в массивах координат - после парсинга, но до основного алгоритма. Тем самым, проблема решена.. пока Ну, кто найдет еще баг?.. { Finding self-crossings of a Boa } Добавлено через 2 мин. Да, еще: программа теперь останавливается сразу после нахождения первого пересечения (правда, пишет, чего с чем). Если пересечений нет - тоже сообщает об этом. Исправлено (см. следующее сообщение) Сообщение отредактировано: Lapp - -------------------- я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой |
1qsd |
Сообщение
#25
|
Новичок Группа: Пользователи Сообщений: 11 Пол: Мужской Реальное имя: Kost Репутация: 0 |
Если удав выглядит как спираль, например так 1R2R3R4R5R6
то программма не работает (пишет что пересечение 3 и 4, хотя на самом деле никаких пересечений быть не должно) |
Lapp |
Сообщение
#26
|
Уникум Группа: Пользователи Сообщений: 6 823 Пол: Мужской Реальное имя: Лопáрь (Андрей) Репутация: 159 |
например так 1R2R3R4R5R6 ... программма не работает Ошибка в этой строчке: while not Cross and(i>3)and(j<i-2) do begin Нужно 2 заменить на 4. Я переставил увеличение j в начало цикла, нижний предел изменил, а верхний - забыл.. Сейчас исправлю в последнем тексте. -------------------- я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой |
Lapp |
Сообщение
#27
|
Уникум Группа: Пользователи Сообщений: 6 823 Пол: Мужской Реальное имя: Лопáрь (Андрей) Репутация: 159 |
По ходу дела, посмотрев на все сложности, возникшие в геометрическом методе (надеюсь, они все все же преодолены ), я решил написать программку по методу "матрицы".
Получилось действительно намного проще, на ее написание ушло замееееетно меньше времени. Я использую симметричный байтовый массив, который, если удовлетворять ограничениям ТР, не должен превышать 64К. Это значит, если округлить, что поле выходит примерно от -100 до 100 по каждой координате.. Разумеется, ситуация намного улучшится в FPC (например на 1 ГБ памяти можно сделать поле от -15000 до +15000), но все равно вряд ли кто станет спорить, что геометрическое решение лучше в смысле эффективности (хотя, при большом количестве поворотов и небольшом диаметре они все же могут конкурировать).. Правда, остается еще вариант со сжатием матрицы на лету - но это уже извращение.. Хотя, разве не извращение уже и то, что я потратил несколько часов на эту задачу? Надеюсь, не совсем зря.. {Search for Boa crossings, matrix method} -------------------- я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой |
Malice |
Сообщение
#28
|
Профи Группа: Пользователи Сообщений: 705 Пол: Мужской Репутация: 20 |
Теперь я думаю, как говорится, тема раскрыта Я б вчера ответил и поговорил на эту тему, но, блин, пошел ребенка укладывать и сам заснул Но все же для меня вопрос остался открыт: как правильно представить удава - в векторном виде (тогда имеются общие точки в углах и начало в точке 0х0) или кубиками (тогда по идее 0х0 не занята (хотя в последнем примере ты ее занял, что не дало пройти тест by Michael_Rybak 10L10L10L20) и отрезки друг к другу прикасаются, но общих точек не имеют.. Наверно правилен матричный способ (я сначала тоже векторным начал (к рекурсии свалился ) и на нем остановиться, жаль только с размерностью неуниверсально получается
|
Michael_Rybak |
Сообщение
#29
|
Michael_Rybak Группа: Пользователи Сообщений: 1 046 Пол: Мужской Реальное имя: Michael_Rybak Репутация: 32 |
Я считаю, что нужно строго определить самопересечение, и тогда проблем не будет Простите если слишком кратко, но мне кажется что ОП мог бы потрудиться и уточнить.
|
Lapp |
Сообщение
#30
|
Уникум Группа: Пользователи Сообщений: 6 823 Пол: Мужской Реальное имя: Лопáрь (Андрей) Репутация: 159 |
Мужики, не драматизируйте ситуацию. Не забывайте - пространство сеточное, дискретное! Любое пресечение - это наличие общих точек (то есть занятие одной точки дважды), и наоборот. Не вижу смысла в уточнении понятия касания.
Я упускаю что-то? что-то важное?.. -------------------- я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой |
Текстовая версия | 4.06.2024 7:12 |