Удав, Задача на координаты и направление |
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 - |
мисс_граффити |
Сообщение
#2
|
просто человек Группа: Пользователи Сообщений: 3 641 Пол: Женский Реальное имя: Юлия Репутация: 55 |
С матрицами...
Единственная идея: берем матрицу из нулей и начинаем заполнять ее удавом (как бы рисуем его по клеточкам). Где он есть - ставим 1. Если клеточка, куда хотим поставить 1, уже равна 1 - значит, он пересекает себя. Минусы метода: ограниченность размера удава (а по этому поводу ничего у нас не говорится), затраты по памяти (удав может быть из 4 клеток, а массив 100*100). я бы пошла другим путем... но для этого надо знать: 1. является ли использование матриц обязательным условием? 2. можно ли пользоваться динамическими структурами? -------------------- Все содержимое данного сообщения (кроме цитат) является моим личным скромным мнением и на статус истины в высшей инстанции не претендует.
На вопросы по программированию, физике, математике и т.д. в аське и личке не отвечаю. Даже "один-единственный раз" в виде исключения! |
1qsd |
Сообщение
#3
|
Новичок Группа: Пользователи Сообщений: 11 Пол: Мужской Реальное имя: Kost Репутация: 0 |
1) можно и не через матрицы
2) можно пользоваться динамическими структурами |
мисс_граффити |
Сообщение
#4
|
просто человек Группа: Пользователи Сообщений: 3 641 Пол: Женский Реальное имя: Юлия Репутация: 55 |
Идея такая: разбиваем удавчика на отрезки, которые записываются в массив (или список). Отдельно горизонтальные, отдельно вертикальные.
Потом сопоставляем каждую вертикальную с каждой горизонтальной и смотрим, пересекаются ли они. -------------------- Все содержимое данного сообщения (кроме цитат) является моим личным скромным мнением и на статус истины в высшей инстанции не претендует.
На вопросы по программированию, физике, математике и т.д. в аське и личке не отвечаю. Даже "один-единственный раз" в виде исключения! |
1qsd |
Сообщение
#5
|
Новичок Группа: Пользователи Сообщений: 11 Пол: Мужской Реальное имя: Kost Репутация: 0 |
давайте по порядку
1) как записывать в массив: сами числа или их координаты или еще что-то?? 2) и как их же сопоставлять?? мне еще понравилась идея с клеточками. Если заполнять, то наверное из центра матрицы? Не думаю, что удав будет слишком большой... |
мисс_граффити |
Сообщение
#6
|
просто человек Группа: Пользователи Сообщений: 3 641 Пол: Женский Реальное имя: Юлия Репутация: 55 |
1) мне кажется, тут подойдет запись с тремя полями: координата конца, координата начала и уровень.
то есть для вертикальных линий координата х - константа, она будет уровнем. координата у начала и конца отличается, их и запишем. аналогично для горизонтальных. 2) если уровень вертикальной находится между началом и концом горизонтальной, а уровень горизонтальной - между началом и концом вертикальной, то их можно считать пересекшимися. да, из центра - самое логичное. с клеточками, как мне кажется, будет проще написать... но как формализовать ограничения на размер - я пока не знаю. -------------------- Все содержимое данного сообщения (кроме цитат) является моим личным скромным мнением и на статус истины в высшей инстанции не претендует.
На вопросы по программированию, физике, математике и т.д. в аське и личке не отвечаю. Даже "один-единственный раз" в виде исключения! |
1qsd |
Сообщение
#7
|
Новичок Группа: Пользователи Сообщений: 11 Пол: Мужской Реальное имя: Kost Репутация: 0 |
А вы можете код с клеточками (во втором сообщении вы предлагали такой способ) хотя бы примерно набросать для матрицы 1000 на 1000??
или, например, для 100 на 100, если нельзя создать 1000x1000?? Сообщение отредактировано: 1qsd - |
мисс_граффити |
Сообщение
#8
|
просто человек Группа: Пользователи Сообщений: 3 641 Пол: Женский Реальное имя: Юлия Репутация: 55 |
а сам не хочешь попробовать хотя бы?
-------------------- Все содержимое данного сообщения (кроме цитат) является моим личным скромным мнением и на статус истины в высшей инстанции не претендует.
На вопросы по программированию, физике, математике и т.д. в аське и личке не отвечаю. Даже "один-единственный раз" в виде исключения! |
Michael_Rybak |
Сообщение
#9
|
Michael_Rybak Группа: Пользователи Сообщений: 1 046 Пол: Мужской Реальное имя: Michael_Rybak Репутация: 32 |
И уточни еще, что если он не пересекает себя, но касается.
|
Lapp |
Сообщение
#10
|
Уникум Группа: Пользователи Сообщений: 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'у.. Я не склонен тут выделять касания, поскольку все происходит на дискретной сетке. Я понимаю, что ты хочешь сказать (это, видимо, относится к топологии), но не думаю, что условие задачи трактовалось так. Любое совпадение точек, принадлежащим звеньям (кроме сочленений соседних звеньев) считаю пересечением. Но я не говорю, что топологический аспект не представляет интереса! Вполне даже может быть.. -------------------- я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой |
Lapp |
Сообщение
#11
|
Уникум Группа: Пользователи Сообщений: 6 823 Пол: Мужской Реальное имя: Лопáрь (Андрей) Репутация: 159 |
Идея такая: разбиваем удавчика на отрезки, которые записываются в массив (или список). Отдельно горизонтальные, отдельно вертикальные. Потом сопоставляем каждую вертикальную с каждой горизонтальной и смотрим, пересекаются ли они. ... 1) мне кажется, тут подойдет запись с тремя полями: координата конца, координата начала и уровень. то есть для вертикальных линий координата х - константа, она будет уровнем. координата у начала и конца отличается, их и запишем. аналогично для горизонтальных. 2) если уровень вертикальной находится между началом и концом горизонтальной, а уровень горизонтальной - между началом и концом вертикальной, то их можно считать пересекшимися. мисс_граффити, по сути я релизовал твою идею (как заметил позже ). Причем, я тоже хотел сначала делать два разных массива, и организовывать рекордом, как ты пишешь. В процессе я все упростил и унифицировал - ушел от рекорда, оставил обычные два массива Х и Y. Процедура-то симметричная.. А пункт 2 просто идентичным получился.. Одинаково мыслим! . Интересно было бы сделать и матрицу и сравнить размер кода. Так или иначе, парсер строки делать надо.. А сам алгоритм совсем небольшой. -------------------- я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой |
Michael_Rybak |
Сообщение
#12
|
Michael_Rybak Группа: Пользователи Сообщений: 1 046 Пол: Мужской Реальное имя: Michael_Rybak Репутация: 32 |
Цитата Да, еще забыл ответить Michael_Rybak'у.. Я не склонен тут выделять касания, поскольку все происходит на дискретной сетке. Я понимаю, что ты хочешь сказать (это, видимо, относится к топологии), но не думаю, что условие задачи трактовалось так. Любое совпадение точек, принадлежащим звеньям (кроме сочленений соседних звеньев) считаю пересечением. В таком случае горизонтальные нельзя проверять только с вертикальными. Он ведь может и пройтись как бы вдоль себя. |
Malice |
Сообщение
#13
|
Профи Группа: Пользователи Сообщений: 705 Пол: Мужской Репутация: 20 |
В таком случае горизонтальные нельзя проверять только с вертикальными. Он ведь может и пройтись как бы вдоль себя. Такое может случится в одном единственном случае, если последний частично залезет на первый со стороны его начала (20L10L30L10L15) Иначе чтоб ему так пройтись ему придется пересечь и один из смежных (и уже перпендикулярного направления) отрезков.. У Lapp-а обрабатывается неправильно, хотя и 20L10L30L10R15, (где пересечения нет) тоже.. |
Michael_Rybak |
Сообщение
#14
|
Michael_Rybak Группа: Пользователи Сообщений: 1 046 Пол: Мужской Реальное имя: Michael_Rybak Репутация: 32 |
10L10L10R10R10R30
|
Гость |
Сообщение
#15
|
Гость |
О чем я и говорил. Пересекает еще и смежные отрезки - достаточно для того, чтобы сделать вывод.
|
Malice |
Сообщение
#16
|
Профи Группа: Пользователи Сообщений: 705 Пол: Мужской Репутация: 20 |
Эт я был.. Я же имел ввиду случай типа:
|
Michael_Rybak |
Сообщение
#17
|
Michael_Rybak Группа: Пользователи Сообщений: 1 046 Пол: Мужской Реальное имя: Michael_Rybak Репутация: 32 |
Он не пересекает смежные отрезки. Я ведь специально спрашивал, считаются ли касания пересечениями.
Добавлено через 42 сек. Еще ведь можно 10L10L10L20, и тут всё чисто. |
Malice |
Сообщение
#18
|
Профи Группа: Пользователи Сообщений: 705 Пол: Мужской Репутация: 20 |
Гы В таком случает надо определьтся - включает ли в свою длину очередной отрезок последнюю точку предыдущего. На твоем примере получается квардрат 11х11, пересечения нет, т.к. никто ширину удава в 1-цу не устанавливал и сливаются отрезки только из-за рисования по клеткам. Я думал, что квадрат будет 10х10 и, соответственно, будет иметь общую точку..
|
Michael_Rybak |
Сообщение
#19
|
Michael_Rybak Группа: Пользователи Сообщений: 1 046 Пол: Мужской Реальное имя: Michael_Rybak Репутация: 32 |
У меня не получался нигде квадрат 11х11. Получалось то, что ты нарисовал.
|
Lapp |
Сообщение
#20
|
Уникум Группа: Пользователи Сообщений: 6 823 Пол: Мужской Реальное имя: Лопáрь (Андрей) Репутация: 159 |
Критику принял.
Думаю.. -------------------- я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой |
Текстовая версия | 7.10.2024 2:44 |