Помощь - Поиск - Пользователи - Календарь
Полная версия: рекурсия- разбиение и сборка квадрата
Форум «Всё о Паскале» > Pascal, Object Pascal > Задачи
Страницы: 1, 2
Lapp
Цитата(Екатерина7 @ 12.12.2009 9:17) *
результаты выполнения:
Это неполный результат.
14 строчек получилось потому, что остальные уехали за верх экрана (и, в частности, количество прямоугольников m). Число m (оно же количество строк с a, b, ab и s) в данном случае заведомо больше 26, поскольку букв латинского алфавита не хватило и в картинке задействованы небуквенные символы. Советую перестать пользоваться допотопным полноэкранным режимом. Окомпилируй программу в exe-файл и запусти его в обычном скроллируемом cmd-окне (в его свойствах поставь размер прокрутки побольше). А про окно 80х25 давно пора забыть..

Еще совет: уменьши размер квадрата. Попробуй, скажем, 6х6. Там, думаю, букв должно хватить.

Добавлено через 6 мин.
Но тут какая-то лажа..
Цитата(Екатерина7 @ 12.12.2009 9:17) *

[ [ [ [ [ [ \_
[ [ ] ] ^ ^^_

- так быть не может. Ты уверена, что при копировании не изменила ничего? Ты не вручную ли копировала??..

Чтобы скопировать из дос-окна, кликни правой кнопкой на верхней полоске, выбери Редактировать и Пометить (если я правильно перевел), затем пометь и снова кликни правой кнопкой..
Екатерина7
нет, не в ручную.. все печатала.. хорошо, проверю.
Екатерина7
а что делает function Overlap?
Екатерина7
я задала n=6, все получается нормально, без вот этого
[ [ [ [ [ [ \_
[ [ ] ] ^ ^^_
Lapp
Цитата(Екатерина7 @ 13.12.2009 12:38) *
я задала n=6, все получается нормально, без вот этого
[ [ [ [ [ [ \_
[ [ ] ] ^ ^^_
Катюш, дело не в том, что там не буквы. Дело в том, что левые (открывающие) скобки там идут углом (я выделяю красным):

[ [ [ [ [ [ \_
[ [ ] ] ^ ^^_

Если это на самом деле так - плохо. Надо мне искать ошибку.
Я не могу воспроизвести эти результаты. Проверь, плз. Спасибо.
Екатерина7
так там не должно быть этих скобок? или они должны быть красным? что-то у меня ничего не выделяется.. ничего не пойму:(

Добавлено через 1 мин.
я проверяла.. все так же , как я и написала.. результаты такие же..
ааааа.. эти скобочки не должны быть углом?
Lapp
Цитата(Екатерина7 @ 14.12.2009 23:52) *
ааааа.. эти скобочки не должны быть углом?
Конечно, не должны. Какой же это тогда прямоугольник? blink.gif
Похоже, ты еще не усвоила общей идеи..

так что - углом они?
Екатерина7
да, если n брать =8, добавляются скобочки и они углом, как и выше нарисовано
Unconnected
У меня при N=8 первая комбинация такая получается (скопировал из cmd):

Код
a= 2     b= 2     ab=   4     s=  32
a= 1     b= 2     ab=   2     s=  34
a= 2     b= 1     ab=   2     s=  36
a= 1     b= 1     ab=   1     s=  37
a= 2     b= 1     ab=   2     s=  39
a= 2     b= 1     ab=   2     s=  41
a= 2     b= 2     ab=   4     s=  45
a= 2     b= 2     ab=   4     s=  49
a= 2     b= 1     ab=   2     s=  51
a= 2     b= 2     ab=   4     s=  55
a= 2     b= 2     ab=   4     s=  59
a= 2     b= 1     ab=   2     s=  61
a= 2     b= 1     ab=   2     s=  63
a= 1     b= 1     ab=   1     s=  64
Done   1
ABBCDEFG
HIICJJLG
KKMNOOLP
KKQQRRST
UVVWRRST
XX_WYYZZ
XX[[YY\\
]][[^^\\


Угла из скобок нет.
Екатерина7
все, получается. да

Добавлено через 7 мин.
идея понятна.. несовсем пойму расположение этих бкув и символов. точнее почему кое-где по одной букве.. она считается за прямоугольник?
Lapp
Цитата(Unconnected @ 15.12.2009 13:00) *
У меня при N=8 первая комбинация такая получается (скопировал из cmd):
...
Угла из скобок нет.
Спасибо, Unconnected. Я все никак не мог добраться до машины с ТР.
+1 тебе. Еще раз спасибо smile.gif


Цитата(Екатерина7 @ 15.12.2009 19:49) *
все, получается. да
Так зачем тогда было говорить то, чего нет? blink.gif

Цитата
почему кое-где по одной букве.. она считается за прямоугольник?
Конечно. А чем он провинился?.. Не дорос?.. В условии нет границы снизу на размер.
Екатерина7
потому что сначала не получалось..(

Добавлено через 6 мин.
а можно процедуру Put пошагово объяснить, конкретнее,если можно.. blush.gif
и что такое Inc(k);

Добавлено через 1 мин.
tRectangle, tLocation это какой-то тип?
Lapp
Цитата(Екатерина7 @ 16.12.2009 7:33) *
потому что сначала не получалось..(
Что не получалось? Так были скобки углом или не были? Как же трудно от тебя получить ответ на простейший вопрос..

Цитата
а можно процедуру Put пошагово объяснить, конкретнее,если можно..
Можно, конечно. Перечитай пост #45 ( рекурсия- разбиение и сборка квадрата ). Я не хочу копипастить его сюда. Более конкретно - на более конкретные вопросы..

Цитата
и что такое Inc(k);
Inc(x) эквивалентно x:=x+1 .

Цитата
tRectangle, tLocation это какой-то тип?
Да, типы. Смотри программный код, а также пост #6 ( рекурсия- разбиение и сборка квадрата ).
Екатерина7
а для чего вот это?
const
r0: tRectangle=(a:1; b:1);
l0: tLocation=(x: 0; y: 0);

что такое r0 и l0?

Добавлено через 4 мин.
еще хотела спросить, а что делает эта функция
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;

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;



Добавлено через 16 мин.
function Overlap- эта функция проверяет пересекаются ли прямоугольники?
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;


Секция описания переменных, тут всё должно быть понятно.
Екатерина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;
Unconnected
Ну, насколько я понял, NoOne - булевая переменная, обеспечивающая условие выхода из рекурсии. Т.е. если рекурсивная функция находит очередной вариант, то рекурсивно вызывается эта же функция с изменёнными параметрами, иначе рекурсия кончается.

Условие выхода из рекурсии:

    if NoOne then Put(x mod n+1,y+x div n)

Екатерина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 мин.
blush.gif
Lapp
Цитата(Екатерина7 @ 22.12.2009 23:07) *
я так поняла, что 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
спасибо всем огромное, кто принимал участие в решении этой задачи!!! good.gif
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.