IPB
ЛогинПароль:

> Прочтите прежде чем задавать вопрос!

1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!

2 страниц V  1 2 >  
 Ответить  Открыть новую тему 
> Удав, Задача на координаты и направление
сообщение
Сообщение #1


Новичок
*

Группа: Пользователи
Сообщений: 11
Пол: Мужской
Реальное имя: Kost

Репутация: -  0  +


Помогите решить вот эту несложную задачу. Преподаватель говорит, что решать её нужно как то через матрицы.

Удав расположен в виде нескольких линий, из которых каждая следущая перпендикулярна предыдущей. Направление каждой линии и её протяженность задаются буквами "L" , "R" и числом.

Например 25L15R5 ("25" - длина линии = 25, "L" - поворачивает на 90 градусов влево, "15" - длина линии = 15 , "R" - поворачивает на 90 градусов вправо , "5" - длина линии = 5).

Определить, пересечет ли он себя.

Сообщение отредактировано: 1qsd -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2


просто человек
******

Группа: Пользователи
Сообщений: 3 641
Пол: Женский
Реальное имя: Юлия

Репутация: -  55  +


С матрицами...
Единственная идея: берем матрицу из нулей и начинаем заполнять ее удавом (как бы рисуем его по клеточкам). Где он есть - ставим 1. Если клеточка, куда хотим поставить 1, уже равна 1 - значит, он пересекает себя.

Минусы метода: ограниченность размера удава (а по этому поводу ничего у нас не говорится), затраты по памяти (удав может быть из 4 клеток, а массив 100*100).

я бы пошла другим путем... но для этого надо знать:
1. является ли использование матриц обязательным условием?
2. можно ли пользоваться динамическими структурами?


--------------------
Все содержимое данного сообщения (кроме цитат) является моим личным скромным мнением и на статус истины в высшей инстанции не претендует.
На вопросы по программированию, физике, математике и т.д. в аське и личке не отвечаю. Даже "один-единственный раз" в виде исключения!
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


Новичок
*

Группа: Пользователи
Сообщений: 11
Пол: Мужской
Реальное имя: Kost

Репутация: -  0  +


1) можно и не через матрицы
2) можно пользоваться динамическими структурами
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


просто человек
******

Группа: Пользователи
Сообщений: 3 641
Пол: Женский
Реальное имя: Юлия

Репутация: -  55  +


Идея такая: разбиваем удавчика на отрезки, которые записываются в массив (или список). Отдельно горизонтальные, отдельно вертикальные.
Потом сопоставляем каждую вертикальную с каждой горизонтальной и смотрим, пересекаются ли они.


--------------------
Все содержимое данного сообщения (кроме цитат) является моим личным скромным мнением и на статус истины в высшей инстанции не претендует.
На вопросы по программированию, физике, математике и т.д. в аське и личке не отвечаю. Даже "один-единственный раз" в виде исключения!
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #5


Новичок
*

Группа: Пользователи
Сообщений: 11
Пол: Мужской
Реальное имя: Kost

Репутация: -  0  +


давайте по порядку
1) как записывать в массив: сами числа или их координаты или еще что-то??
2) и как их же сопоставлять??

мне еще понравилась идея с клеточками. Если заполнять, то наверное из центра матрицы?
Не думаю, что удав будет слишком большой...
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #6


просто человек
******

Группа: Пользователи
Сообщений: 3 641
Пол: Женский
Реальное имя: Юлия

Репутация: -  55  +


1) мне кажется, тут подойдет запись с тремя полями: координата конца, координата начала и уровень.
то есть для вертикальных линий координата х - константа, она будет уровнем. координата у начала и конца отличается, их и запишем. аналогично для горизонтальных.
2) если уровень вертикальной находится между началом и концом горизонтальной, а уровень горизонтальной - между началом и концом вертикальной, то их можно считать пересекшимися.

да, из центра - самое логичное.
с клеточками, как мне кажется, будет проще написать... но как формализовать ограничения на размер - я пока не знаю.


--------------------
Все содержимое данного сообщения (кроме цитат) является моим личным скромным мнением и на статус истины в высшей инстанции не претендует.
На вопросы по программированию, физике, математике и т.д. в аське и личке не отвечаю. Даже "один-единственный раз" в виде исключения!
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #7


Новичок
*

Группа: Пользователи
Сообщений: 11
Пол: Мужской
Реальное имя: Kost

Репутация: -  0  +


А вы можете код с клеточками (во втором сообщении вы предлагали такой способ) хотя бы примерно набросать для матрицы 1000 на 1000??
или, например, для 100 на 100, если нельзя создать 1000x1000??

Сообщение отредактировано: 1qsd -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #8


просто человек
******

Группа: Пользователи
Сообщений: 3 641
Пол: Женский
Реальное имя: Юлия

Репутация: -  55  +


а сам не хочешь попробовать хотя бы?


--------------------
Все содержимое данного сообщения (кроме цитат) является моим личным скромным мнением и на статус истины в высшей инстанции не претендует.
На вопросы по программированию, физике, математике и т.д. в аське и личке не отвечаю. Даже "один-единственный раз" в виде исключения!
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #9


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


И уточни еще, что если он не пересекает себя, но касается.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #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 и цифр (даже концов строк!). Находит (простите - должна находить! smile.gif) все пересечения и сообщает номера пересекающихся звеньев. Если ничего не пересекается - выходит молча smile.gif.

Я проверял на такой вот строчке:
10R5L6L3L12R5
В ней два пересечения: 2х5, 1х6

Вот сам код:
{ Searching self-crossings of a Boa }
{ by Lapp }
const
m=100;

var
x,y:array[0..m]of integer;
Dir:record
x,y:integer
end;
i,j,n,e,l,z:integer;
Cross:boolean;
c:char;
s:string;
f:file of char;

begin
{ Data input }
x[0]:=0; y[0]:=0;
Dir.x:=1; Dir.y:=0;
Assign(f,'boa.dat');
Reset(f);
n:=0;
while not EoF(f) do begin
Read(f,c);
c:=UpCase©;
if (c in ['L','R'])or EoF(f) then begin
Inc(n);
if EoF(f) then s:=s+c;
Val(s,l,e);
x[n]:=x[n-1]+Dir.x*l;
y[n]:=y[n-1]+Dir.y*l;
s:='';
with Dir do case c of
'L':begin z:=x; x:=-y; y:=z end;
'R':begin z:=x; x:=y; y:=-z end;
end
end
else s:=s+c
end;
{ Start working}
for i:=2 to n do begin
Cross:=false;
j:=i mod 2;
while not Cross and (j<i-2) do begin
if Odd(i) then
Cross:=Odd(j) and ((x[i]-x[j])*(x[i-1]-x[j])<=0)
else
Cross:=not Odd(j) and ((y[i]-y[j])*(y[i-1]-y[j])<=0);
if Cross then begin
WriteLn('Bonds #',j+1,' and #',i,' are crossed over');
Cross:=false
end;
Inc(j,2)
end
end
end.


Добавлено через 8 мин.
Да, еще забыл ответить Michael_Rybak'у..
Я не склонен тут выделять касания, поскольку все происходит на дискретной сетке. Я понимаю, что ты хочешь сказать (это, видимо, относится к топологии), но не думаю, что условие задачи трактовалось так. Любое совпадение точек, принадлежащим звеньям (кроме сочленений соседних звеньев) считаю пересечением.
Но я не говорю, что топологический аспект не представляет интереса! smile.gif Вполне даже может быть..


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #11


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


Цитата(мисс_граффити @ 26.03.2007 20:15) *

Идея такая: разбиваем удавчика на отрезки, которые записываются в массив (или список). Отдельно горизонтальные, отдельно вертикальные.
Потом сопоставляем каждую вертикальную с каждой горизонтальной и смотрим, пересекаются ли они.
...
1) мне кажется, тут подойдет запись с тремя полями: координата конца, координата начала и уровень.
то есть для вертикальных линий координата х - константа, она будет уровнем. координата у начала и конца отличается, их и запишем. аналогично для горизонтальных.
2) если уровень вертикальной находится между началом и концом горизонтальной, а уровень горизонтальной - между началом и концом вертикальной, то их можно считать пересекшимися.

мисс_граффити, по сути я релизовал твою идею (как заметил позже smile.gif). Причем, я тоже хотел сначала делать два разных массива, и организовывать рекордом, как ты пишешь. В процессе я все упростил и унифицировал - ушел от рекорда, оставил обычные два массива Х и Y. Процедура-то симметричная.. smile.gif А пункт 2 просто идентичным получился.. Одинаково мыслим! smile.gif.

Интересно было бы сделать и матрицу и сравнить размер кода. Так или иначе, парсер строки делать надо.. А сам алгоритм совсем небольшой.


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #12


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


Цитата
Да, еще забыл ответить Michael_Rybak'у..
Я не склонен тут выделять касания, поскольку все происходит на дискретной сетке. Я понимаю, что ты хочешь сказать (это, видимо, относится к топологии), но не думаю, что условие задачи трактовалось так. Любое совпадение точек, принадлежащим звеньям (кроме сочленений соседних звеньев) считаю пересечением.


В таком случае горизонтальные нельзя проверять только с вертикальными. Он ведь может и пройтись как бы вдоль себя.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #13


Профи
****

Группа: Пользователи
Сообщений: 705
Пол: Мужской

Репутация: -  20  +


Цитата(Michael_Rybak @ 27.03.2007 14:43) *

В таком случае горизонтальные нельзя проверять только с вертикальными. Он ведь может и пройтись как бы вдоль себя.

Такое может случится в одном единственном случае, если последний частично залезет на первый со стороны его начала smile.gif (20L10L30L10L15) Иначе чтоб ему так пройтись ему придется пересечь и один из смежных (и уже перпендикулярного направления) отрезков.. У Lapp-а обрабатывается неправильно, хотя и 20L10L30L10R15, (где пересечения нет) тоже..
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #14


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


10L10L10R10R10R30
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #15


Гость






О чем я и говорил. Пересекает еще и смежные отрезки - достаточно для того, чтобы сделать вывод.
Прикрепленное изображение
 К началу страницы 
+ Ответить 
сообщение
Сообщение #16


Профи
****

Группа: Пользователи
Сообщений: 705
Пол: Мужской

Репутация: -  20  +


Эт я был.. Я же имел ввиду случай типа:
Прикрепленное изображение
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #17


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


Он не пересекает смежные отрезки. Я ведь специально спрашивал, считаются ли касания пересечениями.

Добавлено через 42 сек.
Еще ведь можно 10L10L10L20, и тут всё чисто.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #18


Профи
****

Группа: Пользователи
Сообщений: 705
Пол: Мужской

Репутация: -  20  +


Гы smile.gif В таком случает надо определьтся - включает ли в свою длину очередной отрезок последнюю точку предыдущего. На твоем примере получается квардрат 11х11, пересечения нет, т.к. никто ширину удава в 1-цу не устанавливал и сливаются отрезки только из-за рисования по клеткам. Я думал, что квадрат будет 10х10 и, соответственно, будет иметь общую точку..
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #19


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


У меня не получался нигде квадрат 11х11. Получалось то, что ты нарисовал.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #20


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


Критику принял.
Думаю..


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

2 страниц V  1 2 >
 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 19.09.2020 19:22
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name