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

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

спасибо, Lapp)

Добавлено через 5 мин.
я в принципе с тобой согласна,я программир плохо знаю..

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

Lapp, что-то я вообще не могу понять этой программы... точнее ее выполенение.. что-то странно.. какие-то буквы, цифры.. можешь объяснить, пожалуйста.

[Unconnected]

Екатерина7, какой у тебя уровень программирования в целом? Ты знаешь о типах данных, описании пользовательских типов, функциях, процедурах, операторах в конце концов и т.п.? Просто "буквы, цифры" заставляют задуматься, не рано ли тебе квадраты собирать..

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

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

извини, но хватит говорить про мой уровень программир.. не могу понять результата выполнения.вот и просила объяснить.. как и что получается.

[Lapp]

заставляют задуматься,

Ты задумывайся, никто не против. Это без ограничений. А вот, прежде чем флудить - .. еще раз задумайся ))

извини, но хватит говорить про мой уровень программир..

Совершенно согласен.

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

Ладно, объясняю. Коротко.
Я прохожу по ВСЕМ клеткам (слева направо, сверху вниз). В каждую клетку я кладу ВСЕ имеющиеся в наличии прямоугольники (каждый дважды: горизонтально и вертикально - если он не квадрат) по очереди. При этом я проверяю, пересекается ли он с уже положенными прямоугольниками. Если да - отбрасываю, если не пересекается - оставляю его там лежать и перехожу к следующей клетке. Если мне удается таким образом уложить ВСЕ прямоугольники - очень хорошо, я вывожу картинку.

Это был общий принцип. Теперь, как это организовано.
Процедура Put перебирает в цикле (первый for) все прямоугольники. Если он еще не лежит (l[i]=0), то прикладываем его так, чтоб верхний левый угол попал в клетку x,y.
Затем в цикле (второй for) проверяем его на пересечение с теми, которые уже лежат (l[j]>0). Переменная Clear равна true в том случае, если не было ни одного пересечения.

Дальше.
Если Clear, то мы приделываем этот прямоугольник к этому месту (l[i]:=li) и увеличиваем число положенных прямоугольников k.
Если при этом число k достигло m (число всех прямоугольников), то это значит, что все прямоугольники уложены - в этом случае мы выводим картинку.
Если k<m , то вызываем процедуоу Put для следующей клетки (расчет ее координат непосредственно в вызове).
После вызова восстанавливаем прежнее состояние массива положений l и число k.
Затем поворачиваем прямоугольник (меняем местами a и b) и делаем все то же самое с повернутым.
Все.

Рекурсия делает полный перебор по дереву сама, безо всяких дополнительных циклов. Она, правда, медленная и требует много ресурсов, но зато программа простая.
Стало понятнее?

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

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

[Lapp]

что выводится в результатах, Done:... квадрат с буквами, это и есть наш лист бумаги , разбитый на прямоугольники?

Да.

что за колонки букв в начале с цифрами (это тоже в результатах) , это набор , из которого строятся прямоугольники ниже?

Да, строИтся. Не прямоугольники, а квадрат.
m - число прямоугольников
a - размер по x
b - размер по y
ab - произведение a*b (площадь)
s - сумма площадей, которая в конце должна сравняться с n² (площадь квадрата)

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

а почему Done выводится одно и тоже бесконечное количество раз, программа зацикливается кажется.. как сделать выход из рекурсии? или не нужно?

Добавлено через 5 мин.
большие заглавные буквы латинские, это ячейки , в смысле эти прямоугольники , которые мы подбираем. так?

Добавлено через 1 мин.
еще вопрос) а почему вначале параметров а,b,s,там 14 ?там же вроде как квадрат 8*8..

[Lapp]

а почему Done выводится одно и тоже бесконечное количество раз,

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

программа зацикливается кажется..

Прежде чем делать подобные упреки в ошибках, дай себе труд подумать. Спрашивать - одно, делать ТАКИЕ выводы - другое..

как сделать выход из рекурсии?

Нажать Esc. Если хочешь ограничиться выводом одной конфигурации - отработай Halt после вывода квадрата.

большие заглавные буквы латинские, это ячейки , в смысле эти прямоугольники , которые мы подбираем. так?

Одна буква - один прямоугольник. Можно отмечать цветом (четырьмя цветами) - но это другая задача..

еще вопрос) а почему вначале параметров а,b,s,там 14 ?там же вроде как квадрат 8*8..

Какое еще 14? я не могу видеть, что там у тебя на экране - слишком далеко. НУ НЕУЖЕЛИ так трудно скопировать? Или словами объяснить поточнее.. Почему я тебе все стараюсь как можно яснее говорить, а ты - в основном намеками? Все, Кать, я устал и обиделся. Это был мой последний пост в этой теме.
Успехов тебе.

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

результаты выполнения:

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
ABBCDE FG
HI I I J J MM
KKL LN O OP
KKQQR R SU
T TVVV V V_
WWXXY Y Z_
[ [ [ [ [ [ \_
[ [ ] ] ^ ^^_

[Lapp]

результаты выполнения:

Это неполный результат.
14 строчек получилось потому, что остальные уехали за верх экрана (и, в частности, количество прямоугольников m). Число m (оно же количество строк с a, b, ab и s) в данном случае заведомо больше 26, поскольку букв латинского алфавита не хватило и в картинке задействованы небуквенные символы. Советую перестать пользоваться допотопным полноэкранным режимом. Окомпилируй программу в exe-файл и запусти его в обычном скроллируемом cmd-окне (в его свойствах поставь размер прокрутки побольше). А про окно 80х25 давно пора забыть..

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

Добавлено через 6 мин.
Но тут какая-то лажа..

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

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

Чтобы скопировать из дос-окна, кликни правой кнопкой на верхней полоске, выбери Редактировать и Пометить (если я правильно перевел), затем пометь и снова кликни правой кнопкой..

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

нет, не в ручную.. все печатала.. хорошо, проверю.

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

а что делает function Overlap?

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

я задала n=6, все получается нормально, без вот этого
[ [ [ [ [ [ \_
[ [ ] ] ^ ^^_

[Lapp]

я задала n=6, все получается нормально, без вот этого
[ [ [ [ [ [ \_
[ [ ] ] ^ ^^_

Катюш, дело не в том, что там не буквы. Дело в том, что левые (открывающие) скобки там идут углом (я выделяю красным):

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

Если это на самом деле так - плохо. Надо мне искать ошибку.
Я не могу воспроизвести эти результаты. Проверь, плз. Спасибо.

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

так там не должно быть этих скобок? или они должны быть красным? что-то у меня ничего не выделяется.. ничего не пойму:(

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

[Lapp]

ааааа.. эти скобочки не должны быть углом?

Конечно, не должны. Какой же это тогда прямоугольник?
Похоже, ты еще не усвоила общей идеи..

так что - углом они?

[Екатерина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 мин.
идея понятна.. несовсем пойму расположение этих бкув и символов. точнее почему кое-где по одной букве.. она считается за прямоугольник?