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

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

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

4 страниц V  1 2 3 > »   
 Ответить  Открыть новую тему 
> рекурсия- разбиение и сборка квадрата
сообщение
Сообщение #1


Новичок
*

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

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


помогите, пожалуйста, разобраться с задачей

Лист бумаги в клетку квадратной формы размера NxN произвольно разрезан на прямоугольные части, каждая из которых имеет целое число клеток. Полученные прямоугольные куски перемешаны. Требуется из заданных прямоугольников снова составить квадрат. Квадрат не обязательно должен быть составлен из прямоугольников в том же порядке, в каком он разрезан. При сборке прямоугольники можно поворачивать.

(число N не задано, можно брать любое)
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2


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

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

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


Цитата(Екатерина7 @ 23.11.2009 18:18) *
(число N не задано, можно брать любое)
Любое - какое? Например, случаи N=10 и N=100 могут оказаться существенно разными..
Пожалуйста, уточни верхний предел.


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


Новичок
*

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

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


хорошо, допустим N=10
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


mea culpa
*****

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

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


А как входные данные выглядят? smile.gif


--------------------
"Знаешь, стыдно - когда не видно, что услышал всё, что слушал.."
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #5


Гость






может входными данными могут быть массивы этих прямоугольников,состоящие из клеточек?
 К началу страницы 
+ Ответить 
сообщение
Сообщение #6


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

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

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


Цитата(Гость @ 24.11.2009 10:05) *
может входными данными могут быть массивы этих прямоугольников,состоящие из клеточек?
Unconnected верно заметил - в этой проге подготовка входных данных - это, считай, отдельная задача. Собственно, я поэтому посоветовал именно такое название для этой темы.. )) Но об этом потом.

Общая стратегия состоит в том, что мы (используя полный перебор, организованный рекурсией) набрасываем прямоугольники из имеющегося у нас набора на квадрат, а в процессе этого смотрим, пересекаются они или нет. Если мы находим такое их распределение, что они не пересекаются - все, задача решена. Так что нам нужно уметь делать - смотреть, пересекаются ли два определенных прямоугольника.

Представлений информации в этой задаче может быть несколько. Во-первых, сам прямоугольник может быть представлен своими размерами: длиной и шириной. Затем, есть по крайней мере два способа привязать прямоугольник к координатной сетке (то есть "положить"). Первое, что приходит в голову - сразу завести массив NxN скажем, из целых, и каждую клетку помечать номером того прямоугольника разбиения, к которому она принадлежит. Этот способ требует довольно много памяти.. А другой подход состоит в том, чтобы задавать прямоугольник координатами его двух противоположных вершин либо координатами одной вершины (с минимальными координатами) плюс все те же длина и ширина.

Итак, давай остановимся на следющем. Каждый прямоугольник сам по себе обозначаем длиной и ширинойобозначаем по двум противоположным углам (вершинам). Таким образом, прямоугольник представляется переменной такого типа:
type
tRectangle=record
lx,ly: integer;
end;
tLocation=record
x,y: integer
end;
, где lx - размер по x, а ly - размер по y, а x,y - положение угла с минимальными координатами. У нас координаты будут идти так:
x - слева направо;
y - сверху вниз.
То есть как в матрице (или, если хотите, на графическом экране). Это будет важно только для вывода информации (псевдографика в основном), но если уж так, то будем называть угол по которому мы указываем положение прямоугольника левым-верхним (top-left).

Теперь, когда у нас есть, с чем иметь дело, будем иметь дело. Вопрос, который стоит перед нами, я уже поставил выше:
Допустим, у нас есть два прямоугольника, а также их положения; нужно найти способ определения, пересекаются они или нет.

Или, более конкретно:
var
r1,r2: tRectangle;
l1,l2: tLocation;

function Overlap(r1,l1,r2,l2): boolean;

То есть прежде всего нужно написать функцию, которая выдает TRUE, если два прямоугольника, переданные в параметрах, пересекаются и FALSE, если они не пересекаются.

Перед написанием, конечно, неплохо было бы описать, как будет работать эта функция, словами плюс обычная математика. То есть пока без программирования, просто основные принципы работы. Вот с этого и начнем. Ekaterina7, какие у тебя соображения на этот счет?


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


Новичок
*

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

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


может просто сравнивать положения этих прямоугольников, их воординаты? если совпадут-то пересекаются.. может там цикл нужен?
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #8


mea culpa
*****

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

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


Ага, надо сравнивать, ну он видимо спрашивал про конкретные соотношения, что с чем и как сравнивать.


--------------------
"Знаешь, стыдно - когда не видно, что услышал всё, что слушал.."
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #9


Новичок
*

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

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


да я в приниципе поняла про что.. думаю конкретно как..

Добавлено через 11 мин.
походу нужно какое-то условие..

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


mea culpa
*****

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

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


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

type
tRectangle=record
lx,ly:integer;
end;
tLocation=record
x,y:integer;
end;

function overlapp(r1,r2:tRectangle; l1,l2:tLocation):boolean;
begin
overlapp:=false; //заранее присваиваем функции значение false, т.е. что прям-ки не пересекаются. Оно может
//измениться в процессе выполнения. Не изменится - значит, не пересекаются.

if ((l1.x=l2.x) and (l1.y=l2.y)) then overlapp:=true; //самая первая проверка. Если координаты совпадают,
//то прям-ки пересекаются

if (l1.x>=l2.x) then if (l2.x+r2.lx)>=l1.x then overlapp:=true;
if (l2.x>=l1.x) then if (l1.x+r1.lx)>=l2.x then overlapp:=true; //далее. Если сумма координаты X одного
//прям-ка и его длины больше или равна координате X второго прям-ка, то они пересекаются.

if (l1.y>=l2.y) then if (l2.y+r2.ly)>=l1.y then overlapp:=true;
if (l2.y>=l1.y) then if (l1.y+r1.ly)>=l2.y then overlapp:=true; //и ещё пара условий. Если сумма
//координаты Y одного прям-ка и его ширины больше или равна координате Y второго прям-ка, то
//они пересекаются.

end;



Сообщение отредактировано: Unconnected -


--------------------
"Знаешь, стыдно - когда не видно, что услышал всё, что слушал.."
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #11


Гость






Цитата
//далее. Если сумма координаты X одного
//прям-ка и его длины больше или равна координате X второго прям-ка, то они пересекаются.
blink.gif То есть, ордината тут как бы не при делах? Хорошенькое дело. А если один прямоугольник - прямо надо осью OX, а второй - гораздо выше? Так что не проходит это условие. Равно как и следующее, с координатами Y. Комбинировать их надо, ага...

А я бы вообще в другую сторону смотрел для написания этой функции.
 К началу страницы 
+ Ответить 
сообщение
Сообщение #12


mea culpa
*****

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

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


volvo,
Цитата

У нас координаты будут идти так:
x - слева направо;
y - сверху вниз.


Добавлено: Но сути это не меняет..

Добавлено через 18 мин.
type
tRectangle=record
lx,ly:integer;
end;
tLocation=record
x,y:integer;
end;

function overlapp(r1,r2:tRectangle; l1,l2:tLocation):boolean;
begin
overlapp:=false;
if ((l1.x=l2.x) and (l1.y=l2.y)) then overlapp:=true;

if (l1.x>l2.x) then if (l2.x+r2.lx)>l1.x then
begin
if (l1.y>l2.y) then if (l2.y+r2.ly)>l1.y then overlapp:=true;
if (l1.y<l2.y) then if (l1.y+r1.ly)>l2.y then overlapp:=true;
end;

if (l2.x>l1.x) then if (l1.x+r1.lx)>l2.x then
begin
if (l2.y>l1.y) then if (l1.y+r1.ly)>l2.y then overlapp:=true;
if (l2.y<l1.y) then if (l2.y+r2.ly)>l1.y then overlapp:=true;
end;

end;





Сообщение отредактировано: Unconnected -


--------------------
"Знаешь, стыдно - когда не видно, что услышал всё, что слушал.."
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #13


Гость






Цитата
Добавлено через 18 мин.
Это тоже сути не меняет, функция как не работала, так и не работает:

const
r1: trectangle = (lx:10; ly:5);
r2: trectangle = (lx:10; ly:5);
l1: tlocation = (x:0; y:0);
l2: tlocation = (x:11; y:5);

begin
writeln(overlapp(r1, r2, l1, l2));
end.
, и почему у меня ощущение, что должно быть False, а выдается True?

Кстати, Unconnected, это ты специально функцию переназвал? cool.gif

 К началу страницы 
+ Ответить 
сообщение
Сообщение #14


mea culpa
*****

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

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


volvo, у нас квадрат ограничивается 10 smile.gif

Я написал такой код, принцип у него другой, нежели у первого, но вот почему-то в конце массивов не координаты а чушь какая-то вперемешку с ними, и на введённых данных тоже True выдаёт:

type
tRectangle=record
lx,ly:integer;
end;
tLocation=record
x,y:integer;
end;

const n=10;
r1:trectangle=(lx:10;ly:5);
r2:trectangle=(lx:10;ly:5);
l1:TLocation=(x:0;y:0);
l2:TLocation=(x:11;y:5);

function overlapp(r1,r2:tRectangle; l1,l2:tLocation):boolean;
var rec1,rec2:array[0..500] of tLocation;
i,j,k,l:byte;
begin
k:=0;
for i:=l1.x to l1.x+r1.lx do
for j:=l1.y to l1.y+r1.ly do begin
rec1[k].x:=i;
rec1[k].y:=j;
inc(k);
end;
k:=1;
for i:=l2.x to l2.x+r2.lx do
for j:=l2.y to l2.y+r2.ly do begin
rec2[k].x:=i;
rec2[k].y:=j;
inc(k);
end;
overlapp:=false;
for i:=0 to k do
for j:=0 to k do
begin
if (rec1[i].x=rec2[i].x) and (rec1[i].y=rec2[i].y) then begin
overlapp:=true;
break;
end;
end;
end;
begin
writeln(overlapp(r1,r2,l1,l2));
readln;
end.


Цитата

Кстати, Unconnected, это ты специально функцию переназвал? cool.gif


Случайно cool.gif

Сообщение отредактировано: Unconnected -


--------------------
"Знаешь, стыдно - когда не видно, что услышал всё, что слушал.."
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #15


Новичок
*

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

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


-что-то я не пойму, а какой тут принцип?
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #16


mea culpa
*****

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

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


type
tRectangle=record
lx,ly:integer;
end;
tLocation=record
x,y:integer;
end;

const n=10;
r11:trectangle=(lx:10;ly:5);
r22:trectangle=(lx:10;ly:5);
l11:TLocation=(x:0;y:0);
l22:TLocation=(x:9;y:5);

function overlapp(r1,r2:tRectangle; l1,l2:tLocation):boolean;
var rec1,rec2:array[0..n*n] of tLocation;
i,j,k,l:integer;
begin
k:=0;
fillchar(rec1,n*n*sizeof(tLocation),0);
fillchar(rec2,n*n*sizeof(tLocation),0);
for i:=l1.x to l1.x+r1.lx do
for j:=l1.y to l1.y+r1.ly do begin
rec1[k].x:=i;
rec1[k].y:=j;
inc(k);
end;
l:=0;
for i:=l2.x to l2.x+r2.lx do
for j:=l2.y to l2.y+r2.ly do begin
rec2[l].x:=i;
rec2[l].y:=j;
inc(l);
end;
overlapp:=false;
for i:=1 to k-1 do
for j:=1 to l-1 do
begin
if (rec1[i].x=rec2[j].x) and (rec1[i].y=rec2[j].y) then begin
overlapp:=true;
break;
end;
end;
end;


Вот эта вроде как работает. На данных volvo выдала false, на немного изменённых - true.

toЕкатерина7, принцип следующий. Проходим в циклах по обоим прямоугольникам и заносим в два массива соответственно координаты каждой клетки каждого прямоугольника. Потом проверяем, если в одном массиве есть координаты, которые есть и во втором массиве, то прямоугольники пересекаются, если нету - не пересекаются..


--------------------
"Знаешь, стыдно - когда не видно, что услышал всё, что слушал.."
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #17


Профи
****

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

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


Unconnected, что-то сложновато smile.gif.

Hint: условие того, что прямоугольники не пересекаются: (r1.Right < r2.Left) or (r1.Left > r2.Right) or (r1.Top > r2.Bottom) or (r1.Bottom < r2.Top).


--------------------
Close the World...txeN eht nepO
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #18


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

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

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


Не знаю, как с точки зрения Екатерина7, но лично мне нравится, что обсуждение получилось оживленным )). Также спасибо volvo за осторожные коррекции направлений.

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

Archon говорит в принципе верные вещи, но они мало отличаются от того, что завело в тупик Неприсоединенного. Слишком много проверок.

Катя, дальше следи внимательно, и если что-то неясно - говори.

Мы немного отойдем от условия и будем пока рассматривать не прямоугольники, а , скажем, круги на плоскости. Поначалу кажется, что ситуация только усложнилась - круг со многих точек зрения сложнее прямоугольника. Но на самом деле, после первого взгляда на чертеж (даже в уме)) становится ясно, что нужно сравнивать не координаты точек на окружности, а координаты центров. А именно: если расстояние между центрами больше, чем сумма радиусов этих кругов, то круги не пересекаются. Если меньше (либо равно) - пересекаются (касаются). Вот и все. Это понятно?

Теперь обсудим другую ситуацию, тоже не совсем прямо вытекающую из условий задачи; а именно - отрезки на прямой. По сути, отрезок на прямой - это есть КРУГ в одномерном пространстве. И хотя обычно, говоря об отрезке, мало кто специально указывает положение его центра (как в случае окружности), он у него все же есть )). Давайте будем описывать отрезки не как обычно (началом и концом), а их центрами и радиусами (радиус отрезка равен половине его длины). И сразу же становится понятно, что условие пересечения двух отрезков на прямой записывается точно так же, как и кругов на плоскости. И не надо проверять несколько случаев.. ))

Дальше. Фактически, условие пересечения двух прямоугольников распадается на два условия по координатам, причем нужно брать их логическое пересечение (условие выполнено только когда оба условия по координатам отдельно выполнены) - это легко понять, нарисовав несколько случаев на бумажке(или снова в уме)).

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

Прикрепленное изображение

|C2 - C1| <= L1/2 + L2/2

Это соотношение нужно проверить по X и по Y, и если в обоих случаях условия выполняются - значит, прямоугольники пересекаются. Прежде чем выписать окончательное выражение, я замечу еще вот, что. В выражении присутствует деление на два, которое добавляет ложку дегтя в нашу бочку с медом, так как требует введения переменных действительного типа со всеми вытекающими (сравнение действительных переменных протекает сложнее..) Поэтому мы заменим эту формулу эквивалентной, умноженной на два.
Итак, в результате имеем:

( 2*|Cx2-Cx1| <= Lx1 + Lx2 ) /\ ( 2*|Cy2-Cy1| <= Ly1 + Ly2 )


Катя, ты поняла математику? пожалуйста, ответь.


Ну вот, теперь можно переходить к программированию..
Я немного изменил названия переменных - извиняюсь за это, просто я тогда поспешил. Для однообразия лучше иметь вместо lx и ly однобуквенные идентификаторы a и b для длины и ширины. Вллюще, это не в полном смысле длина и ширина, а просто размер по x (это a) и по y (это b).

В итоге пресловутая функция будет выглядеть примерно так:
type
tRectangle=record
a,b: integer
end;
tLocation=record
x,y: integer
end;

function Overlap(r1: tRectangle; l1: tLocation; r2: tRectangle; l2: tLocation): boolean;
begin
Overlap:=
(Abs(l2.x*2+r2.a-l1.x*2-r1.a) < r1.a+r2.a) and
(Abs(l2.y*2+r2.b-l1.y*2-r1.b) < r1.b+r2.b)
end;


Unconnected, спасибо за аллюзию, я appreciate that )).

Катя, пожалуйста, посмотри все и задавай вопросы. В принципе, мы готовы двигаться дальше, и следующим шагом будет как раз та подготовка входных данных, о которой шла речь выше. У кого какие соображения? smile.gif


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


mea culpa
*****

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

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


Цитата
У кого какие соображения? smile.gif


Мм, ну, возможно, следует описать некий тип и в него занести информацию о каждом прямоугольнике (можно так же, как и здесь, длина, ширина и координаты верхнего угла), и главное, чтобы в этой инфе было указано, с какими прямоугольниками он пересекается.

Добавлено через 11 мин.
Цитата
Archon говорит в принципе верные вещи, но они мало отличаются от того, что завело в тупик Неприсоединенного. Слишком много проверок.


По сравнению с количеством проверок в моих функциях 4 проверки очень даже мобильными кажутся)


--------------------
"Знаешь, стыдно - когда не видно, что услышал всё, что слушал.."
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #20


mea culpa
*****

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

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


Хотя, по словам Lapp'а,
Цитата

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


функция для определения пересечений есть, остаётся перебирать?)


--------------------
"Знаешь, стыдно - когда не видно, что услышал всё, что слушал.."
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

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

 





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