Удав, Задача на координаты и направление |
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 |
Сообщение
#2
|
Уникум Группа: Пользователи Сообщений: 6 823 Пол: Мужской Реальное имя: Лопáрь (Андрей) Репутация: 159 |
Я тоже не придумал, как тут использовать матрицы, кроме заполнения поля единицами на месте его тела, но этот способ сильно ограничивает размеры удава и крайне неэффективен по использованию памяти. Была у меня мыслишка сжимать эту "матрицу" на лету, но я все же решил пойти другим путем - традиционным, геометрическим.
Учитывая структуру входной строки, звенья удава все время чередуются: горизонтальное - вертикальное, и снова. Мой алгоритм прост: 1. иду по удаву с начала и до конца 2. координаты текущего звена сравниваю: - если четное, с нечетными; - если нечетное, с четными 3. сравнение заключается в оценке на отрицательность или равенство нулю произведения: (Xi - Xj)*(Xi-1 - Xj) - это для нечетных, (Yi - Yj)*(Yi-1 - Yj) - это для четных. Здесь Xi, Xi-1 - координаты текущего звена, а Xj - координата звена, с которым сравниваем (то же самое для Y). Замечу, что я считаю первое звено расположенное началом в т. 0,0 , а конец - в положительном направлении по оси Х. Сиситема координат обычная математическая (х - вправо, у - вверх). Чуть ли не больше половины занимает парсинг входной строки (простейший) с заполнением массивов координат X и Y. Он делается с помощью поворотов вектора направлений (Dir). Для этого использую матрицу поворотов (аналогично как в теме Лабиринт , но без выделения в отдельную процедуру). Программа читает из файла boa.dat, в нем не должно быть никаких других символов, кроме L, R и цифр (даже концов строк!). Находит (простите - должна находить! ) все пересечения и сообщает номера пересекающихся звеньев. Если ничего не пересекается - выходит молча . Я проверял на такой вот строчке: 10R5L6L3L12R5 В ней два пересечения: 2х5, 1х6 Вот сам код: { Searching self-crossings of a Boa } Добавлено через 8 мин. Да, еще забыл ответить Michael_Rybak'у.. Я не склонен тут выделять касания, поскольку все происходит на дискретной сетке. Я понимаю, что ты хочешь сказать (это, видимо, относится к топологии), но не думаю, что условие задачи трактовалось так. Любое совпадение точек, принадлежащим звеньям (кроме сочленений соседних звеньев) считаю пересечением. Но я не говорю, что топологический аспект не представляет интереса! Вполне даже может быть.. -------------------- я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой |
Текстовая версия | 24.04.2024 1:03 |