рекурсия- разбиение и сборка квадрата |
1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code].
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!
рекурсия- разбиение и сборка квадрата |
Екатерина7 |
7.12.2009 19:33
Сообщение
#41
|
Новичок Группа: Пользователи Сообщений: 43 Пол: Женский Репутация: 0 |
спасибо, Lapp)
Добавлено через 5 мин. я в принципе с тобой согласна,я программир плохо знаю.. |
Екатерина7 |
10.12.2009 20:31
Сообщение
#42
|
Новичок Группа: Пользователи Сообщений: 43 Пол: Женский Репутация: 0 |
Lapp, что-то я вообще не могу понять этой программы... точнее ее выполенение.. что-то странно.. какие-то буквы, цифры.. можешь объяснить, пожалуйста.
|
Unconnected |
10.12.2009 21:09
Сообщение
#43
|
mea culpa Группа: Пользователи Сообщений: 1 372 Пол: Мужской Реальное имя: Николай Репутация: 24 |
Екатерина7, какой у тебя уровень программирования в целом? Ты знаешь о типах данных, описании пользовательских типов, функциях, процедурах, операторах в конце концов и т.п.? Просто "буквы, цифры" заставляют задуматься, не рано ли тебе квадраты собирать..
Сообщение отредактировано: Unconnected - 10.12.2009 21:10 -------------------- "Знаешь, стыдно - когда не видно, что услышал всё, что слушал.."
|
Екатерина7 |
11.12.2009 8:43
Сообщение
#44
|
Новичок Группа: Пользователи Сообщений: 43 Пол: Женский Репутация: 0 |
извини, но хватит говорить про мой уровень программир.. не могу понять результата выполнения.вот и просила объяснить.. как и что получается.
|
Lapp |
11.12.2009 11:03
Сообщение
#45
|
Уникум Группа: Модераторы Сообщений: 6 823 Пол: Мужской Реальное имя: Лопáрь (Андрей) Репутация: 159 |
заставляют задуматься, Ты задумывайся, никто не против. Это без ограничений. А вот, прежде чем флудить - .. еще раз задумайся )) извини, но хватит говорить про мой уровень программир.. Совершенно согласен.Кать, мне просто хотелось, чтоб ты поняла, что думать, что в написанной программе легко разобраться - это большая ошибка. Так же, как разбираться в математических выкладках с трехэтажными интегралами. Конечно, с программой все же проще, чем без нее, но все же.. Я, например, сам, когда смотрю на свои (!) старые программы, думаю, что проще написать новую. Вот, свежий случай - в соседней теме ( Игра Калах ) меня попросили пояснить. И я вот уже несколько часов тупо смотрю на нее и думаю: и новую написать, что ли.. Я, конечно, понимаю, что тебе это все не очень важно.. Ладно, объясняю. Коротко. Я прохожу по ВСЕМ клеткам (слева направо, сверху вниз). В каждую клетку я кладу ВСЕ имеющиеся в наличии прямоугольники (каждый дважды: горизонтально и вертикально - если он не квадрат) по очереди. При этом я проверяю, пересекается ли он с уже положенными прямоугольниками. Если да - отбрасываю, если не пересекается - оставляю его там лежать и перехожу к следующей клетке. Если мне удается таким образом уложить ВСЕ прямоугольники - очень хорошо, я вывожу картинку. Это был общий принцип. Теперь, как это организовано. Процедура 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 |
11.12.2009 12:22
Сообщение
#46
|
Новичок Группа: Пользователи Сообщений: 43 Пол: Женский Репутация: 0 |
ммм. да, это поняла.. такой вопрос: то, что выводится в результатах, Done:... квадрат с буквами, это и есть наш лист бумаги , разбитый на прямоугольники? и несовсем пойму,что за колонки букв в начале с цифрами (это тоже в результатах) , это набор , из которого строятся прямоугольники ниже?
|
Lapp |
11.12.2009 13:33
Сообщение
#47
|
Уникум Группа: Модераторы Сообщений: 6 823 Пол: Мужской Реальное имя: Лопáрь (Андрей) Репутация: 159 |
что выводится в результатах, Done:... квадрат с буквами, это и есть наш лист бумаги , разбитый на прямоугольники? Да.Цитата что за колонки букв в начале с цифрами (это тоже в результатах) , это набор , из которого строятся прямоугольники ниже? Да, строИтся. Не прямоугольники, а квадрат.m - число прямоугольников a - размер по x b - размер по y ab - произведение a*b (площадь) s - сумма площадей, которая в конце должна сравняться с n2 (площадь квадрата) -------------------- я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой |
Екатерина7 |
11.12.2009 15:31
Сообщение
#48
|
Новичок Группа: Пользователи Сообщений: 43 Пол: Женский Репутация: 0 |
а почему Done выводится одно и тоже бесконечное количество раз, программа зацикливается кажется.. как сделать выход из рекурсии? или не нужно?
Добавлено через 5 мин. большие заглавные буквы латинские, это ячейки , в смысле эти прямоугольники , которые мы подбираем. так? Добавлено через 1 мин. еще вопрос) а почему вначале параметров а,b,s,там 14 ?там же вроде как квадрат 8*8.. |
Lapp |
11.12.2009 22:10
Сообщение
#49
|
Уникум Группа: Модераторы Сообщений: 6 823 Пол: Мужской Реальное имя: Лопáрь (Андрей) Репутация: 159 |
а почему Done выводится одно и тоже бесконечное количество раз, Не бесконечное, а просто очень большое. Потому что много способов есть собрать квадрат. Если найден один - значит, есть по крайней мере 8 уже (в силу симметрий: поворот и отражение). А в этой программе вообще два прямоугольника с одинаковыми параметрами рассматриваются как разные. Там этих способов тысячи и тысячи.Цитата программа зацикливается кажется.. Прежде чем делать подобные упреки в ошибках, дай себе труд подумать. Спрашивать - одно, делать ТАКИЕ выводы - другое.. Цитата как сделать выход из рекурсии? Нажать Esc. Если хочешь ограничиться выводом одной конфигурации - отработай Halt после вывода квадрата.Цитата большие заглавные буквы латинские, это ячейки , в смысле эти прямоугольники , которые мы подбираем. так? Одна буква - один прямоугольник. Можно отмечать цветом (четырьмя цветами) - но это другая задача..Цитата еще вопрос) а почему вначале параметров а,b,s,там 14 ?там же вроде как квадрат 8*8.. Какое еще 14? я не могу видеть, что там у тебя на экране - слишком далеко. НУ НЕУЖЕЛИ так трудно скопировать? Или словами объяснить поточнее.. Почему я тебе все стараюсь как можно яснее говорить, а ты - в основном намеками? Все, Кать, я устал и обиделся. Это был мой последний пост в этой теме.Успехов тебе. -------------------- я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой |
Екатерина7 |
12.12.2009 9:17
Сообщение
#50
|
Новичок Группа: Пользователи Сообщений: 43 Пол: Женский Репутация: 0 |
результаты выполнения:
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 |
12.12.2009 11:19
Сообщение
#51
|
Уникум Группа: Модераторы Сообщений: 6 823 Пол: Мужской Реальное имя: Лопáрь (Андрей) Репутация: 159 |
результаты выполнения: Это неполный результат.14 строчек получилось потому, что остальные уехали за верх экрана (и, в частности, количество прямоугольников m). Число m (оно же количество строк с a, b, ab и s) в данном случае заведомо больше 26, поскольку букв латинского алфавита не хватило и в картинке задействованы небуквенные символы. Советую перестать пользоваться допотопным полноэкранным режимом. Окомпилируй программу в exe-файл и запусти его в обычном скроллируемом cmd-окне (в его свойствах поставь размер прокрутки побольше). А про окно 80х25 давно пора забыть.. Еще совет: уменьши размер квадрата. Попробуй, скажем, 6х6. Там, думаю, букв должно хватить. Добавлено через 6 мин. Но тут какая-то лажа.. [ [ [ [ [ [ \_ [ [ ] ] ^ ^^_ - так быть не может. Ты уверена, что при копировании не изменила ничего? Ты не вручную ли копировала??.. Чтобы скопировать из дос-окна, кликни правой кнопкой на верхней полоске, выбери Редактировать и Пометить (если я правильно перевел), затем пометь и снова кликни правой кнопкой.. -------------------- я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой |
Екатерина7 |
12.12.2009 17:17
Сообщение
#52
|
Новичок Группа: Пользователи Сообщений: 43 Пол: Женский Репутация: 0 |
нет, не в ручную.. все печатала.. хорошо, проверю.
|
Екатерина7 |
13.12.2009 10:19
Сообщение
#53
|
Новичок Группа: Пользователи Сообщений: 43 Пол: Женский Репутация: 0 |
а что делает function Overlap?
|
Екатерина7 |
13.12.2009 12:38
Сообщение
#54
|
Новичок Группа: Пользователи Сообщений: 43 Пол: Женский Репутация: 0 |
я задала n=6, все получается нормально, без вот этого
[ [ [ [ [ [ \_ [ [ ] ] ^ ^^_ |
Lapp |
14.12.2009 1:54
Сообщение
#55
|
Уникум Группа: Модераторы Сообщений: 6 823 Пол: Мужской Реальное имя: Лопáрь (Андрей) Репутация: 159 |
я задала n=6, все получается нормально, без вот этого Катюш, дело не в том, что там не буквы. Дело в том, что левые (открывающие) скобки там идут углом (я выделяю красным):[ [ [ [ [ [ \_ [ [ ] ] ^ ^^_ [ [ [ [ [ [ \_ [ [ ] ] ^ ^^_ Если это на самом деле так - плохо. Надо мне искать ошибку. Я не могу воспроизвести эти результаты. Проверь, плз. Спасибо. -------------------- я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой |
Екатерина7 |
14.12.2009 23:52
Сообщение
#56
|
Новичок Группа: Пользователи Сообщений: 43 Пол: Женский Репутация: 0 |
так там не должно быть этих скобок? или они должны быть красным? что-то у меня ничего не выделяется.. ничего не пойму:(
Добавлено через 1 мин. я проверяла.. все так же , как я и написала.. результаты такие же.. ааааа.. эти скобочки не должны быть углом? |
Lapp |
15.12.2009 0:20
Сообщение
#57
|
Уникум Группа: Модераторы Сообщений: 6 823 Пол: Мужской Реальное имя: Лопáрь (Андрей) Репутация: 159 |
ааааа.. эти скобочки не должны быть углом? Конечно, не должны. Какой же это тогда прямоугольник? Похоже, ты еще не усвоила общей идеи.. так что - углом они? -------------------- я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой |
Екатерина7 |
15.12.2009 9:41
Сообщение
#58
|
Новичок Группа: Пользователи Сообщений: 43 Пол: Женский Репутация: 0 |
да, если n брать =8, добавляются скобочки и они углом, как и выше нарисовано
|
Unconnected |
15.12.2009 13:00
Сообщение
#59
|
mea culpa Группа: Пользователи Сообщений: 1 372 Пол: Мужской Реальное имя: Николай Репутация: 24 |
У меня при 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 |
15.12.2009 19:49
Сообщение
#60
|
Новичок Группа: Пользователи Сообщений: 43 Пол: Женский Репутация: 0 |
все, получается. да
Добавлено через 7 мин. идея понятна.. несовсем пойму расположение этих бкув и символов. точнее почему кое-где по одной букве.. она считается за прямоугольник? |
Текстовая версия | 16.05.2024 20:58 |