рекурсия- разбиение и сборка квадрата Опции

[Екатерина7]

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

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

(число N не задано, можно брать любое)

[Unconnected]

const
r0: tRectangle=(a:1; b:1);
l0: tLocation=(x: 0; y: 0);

Объявление переменных r0 и l0 типами tRectangle и TLocation соответственно (только почему-то он сделал это в секции констант). Сразу же эти переменные инициализируются, т.е. им присваиваются начальные значения (вот эти части: "=(a:1; b:1);=(x: 0; y: 0);").

еще хотела спросить, а что делает эта функция
function Overlap(r1: tRectangle; l1: tLocation; r2: tRectangle; l2: tLocation): boolean;

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

var
r: array[1..n*n+10]of tRectangle;
l: array[1..n*n+10]of tLocation;
s,i,m,k,done: integer;
t: tRectangle;
u: tLocation;
Clear: boolean;

Секция описания переменных, тут всё должно быть понятно.

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

[Екатерина7]

заметила. а что такое NoOne?

Добавлено через 9 мин.
например, вот тут

Код

begin
  if y<=n then begin
    li.x:=x;
    li.y:=y;
    NoOne:=true;

или тут

Код

for j:=1 to m do if l[j].x>0 then Clear:=Clear and not Overlap(r[i],li,r[j],l[j]);
          if Clear then begin
            Inc(k);
            l[i]:=li;
            if k<>m then Put(x mod n+1,y+x div n);
            l[i]:=l0;
            Dec(k);
            NoOne:=false
          end
        end;
        j:=a;
        a:=b;
        b:=j;
      end
    end;
    if NoOne then Put(x mod n+1,y+x div n)
  end
end;

[Екатерина7]

я так поняла, что function Overlap(r1: tRectangle; l1: tLocation; r2: tRectangle; l2: tLocation): boolean; -функция, которая выдает True, если прямоугольники пересекаются и False,если нет. так? только если честно, этого я в программе не вижу, в смысле где именно это описывается..

Добавлено через 1 мин.
ааа.. спасибо большое!

Добавлено через 5 мин.
можешь еще объяснить хотя бы в кратце, что делает procedure JustSet; {подготовка входных данных}
вот тут

with t do repeat
    a:=Random(k)+1;
    b:=Random(k)+1;
    q:=s+a*b;
    if q<=n*n then begin
      Inc(m);
      r[m]:=t;
      l[m]:=u;
      s:=q
    end
  until s=n*n
end;

Добавлено через 1 мин.

[Lapp]

я так поняла, что function Overlap(r1: tRectangle; l1: tLocation; r2: tRectangle; l2: tLocation): boolean; -функция, которая выдает True, если прямоугольники пересекаются и False,если нет. так? только если честно, этого я в программе не вижу, в смысле где именно это описывается..

Это не описывается. Это делается внутри самой функции. Алгоритм я подробно объяснил в одном из постов, посмотри выше.

можешь еще объяснить хотя бы в кратце, что делает procedure JustSet; {подготовка входных данных}

конечно.
Это просто случайный выбор набора прямоугольников с условием, что их суммарная площадь равна площади квадрата (ну и каждая сторона не превосходит стороны квадрата). То, что из них действительно можно составить квадрат - не гарантируется (поэтому название JustSet - ПростоНабор).

with t do repeat
// случайным образом выбираем размеры прямоугольника
    a:=Random(k)+1;
    b:=Random(k)+1;
// вычисляем общую сумму площадей
    q:=s+a*b;
// если она меньше, чем площадь разрезаемого квадрата - прямоугольник годится, записываем его в набор
    if q<=n*n then begin
      Inc(m);     // увеличиваем число прямоугольников в наборе
      r[m]:=t;    // записывем прямоугольник в набор
      l[m]:=u;    // приписываем ему нулевое положение (означает, что он не положен внутрь квадрата)
      s:=q    // запоминаем новое значение суммарной площади
    end
  until s=n*n  // до тех пор, пока суммарная площадь не сравняется с площадбю квадрата
end;

[Екатерина7]

спасибо всем огромное, кто принимал участие в решении этой задачи!!!