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

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

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

> рекурсия- разбиение и сборка квадрата
Екатерина7
сообщение 23.11.2009 18:18
Сообщение #1


Новичок
*

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

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


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

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

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


mea culpa
*****

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

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


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

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


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


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


Новичок
*

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

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


да,Lapp, с математикой все понятно.. да и с кусочком программы вроде бы тоже..)

Добавлено через 2 мин.
извиняюсь,у меня пару дней с инетом проблемы были,не могла ответить..(( все нормально..вроде бы понятно.. все остается так же актуальным..

Добавлено через 9 мин.
входные данные- параметры прямоугольников,как говорил Unconnected.так?
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
Lapp
сообщение 30.11.2009 9:26
Сообщение #4


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

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

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


Цитата(Екатерина7 @ 30.11.2009 7:38) *
входные данные- параметры прямоугольников,как говорил Unconnected.так?
Да, так. Вопрос, как. smile.gif

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

У набора, из которого можно построить квадрат есть одно обязательное свойство: сумма всех клеток всех его прямоугольников равна количеству клеток в квадрате, то есть N*N. Но это не есть достаточное условие.

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

То, что я предложил выше - это видоизменение условия. Я не знаю, насколько такие зменения допустимы. Поэтому я предлагаю: Катя, спроси преподавателя:
1. существует ли набор входных данных для проверки? Если да, то где его взять и в каком он формате.
2. если нет, то возможно ли вместо повторной сборки просто брать случайный набор (с суммарной площадью N*N) и говорить, можно ли из него собрать квадрат (с выдачей порядка сборки в случае удачи).

Либо спроси, либо сама скажи, что делать, потому что от этого зависит программа. Ok? smile.gif




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


Новичок
*

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

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


набора входных данных нет.. думаю, что можно брать вместо повторной сборки просто случайный набор..
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
Lapp
сообщение 2.12.2009 7:39
Сообщение #6


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

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

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


Цитата(Екатерина7 @ 30.11.2009 14:20) *
думаю, что можно брать вместо повторной сборки просто случайный набор..
Хорошо. Ну, давай тогда делать случайный набор. Создать и записать в файл square.dat в таком формате: длина и ширина на одной строке; строк стролько, сколько прямоугольников.
Сможешь сделать?


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

Сообщений в этой теме
Екатерина7   рекурсия- разбиение и сборка квадрата   23.11.2009 18:18
Lapp   (число N не задано, можно брать любое)Любое - како...   23.11.2009 18:41
Екатерина7   хорошо, допустим N=10   23.11.2009 18:45
Unconnected   А как входные данные выглядят? :)   23.11.2009 22:21
Гость   может входными данными могут быть массивы этих пря...   24.11.2009 10:05
Lapp   может входными данными могут быть массивы этих пря...   26.11.2009 12:20
Екатерина7   может просто сравнивать положения этих прямоугольн...   26.11.2009 18:30
Unconnected   Ага, надо сравнивать, ну он видимо спрашивал про к...   26.11.2009 20:16
Екатерина7   да я в приниципе поняла про что.. думаю конкретно ...   26.11.2009 23:50
Unconnected   Ну да, координаты нужно сравнивать, но нельзя забы...   27.11.2009 0:58
volvo   :blink: То есть, ордината тут как бы не при делах...   27.11.2009 1:08
Unconnected   volvo, Добавлено: Но сути это не меняет.. [b]До...   27.11.2009 10:22
volvo   Это тоже сути не меняет, функция как не работала, ...   27.11.2009 13:44
Unconnected   volvo, у нас квадрат ограничивается 10 :) Я напи...   27.11.2009 17:04
Екатерина7   -что-то я не пойму, а какой тут принцип?   27.11.2009 19:09
Unconnected   type tRectangle=record lx,ly:integer; end;...   27.11.2009 23:01
Archon   Unconnected, что-то сложновато :). Hint: условие ...   27.11.2009 23:31
Lapp   Не знаю, как с точки зрения Екатерина7, но лично м...   28.11.2009 9:34
Unconnected   Мм, ну, возможно, следует описать некий тип и в ...   28.11.2009 10:34
Unconnected   Хотя, по словам Lapp'а, функция для определе...   28.11.2009 11:08
Lapp   функция для определения пересечений есть, остаётся...   28.11.2009 14:44
Екатерина7   да,Lapp, с математикой все понятно.. да и с кусоч...   30.11.2009 7:38
Lapp   входные данные- параметры прямоугольников,как гово...   30.11.2009 9:26
Екатерина7   набора входных данных нет.. думаю, что можно брать...   30.11.2009 14:20
Lapp   думаю, что можно брать вместо повторной сборки про...   2.12.2009 7:39
Екатерина7   если честно, несовсем:( у меня с этим возникли тру...   2.12.2009 18:03
Lapp   Кать, если тебе не актуально уже, ты скажи. А если...   30.11.2009 6:25
Lapp   Ну, начать я тебе помогу var s,q: integer; t:...   2.12.2009 18:12
Екатерина7   наверно нет.. затрудняюсь.. в написанном могу разо...   4.12.2009 14:59
Unconnected   Екатерина7, ты какой курс, если не секрет? Просто...   4.12.2009 22:33
Екатерина7   не секрет- 4-й.. да.. нас плохо научили программи...   4.12.2009 23:42
Екатерина7   :wacko:   5.12.2009 16:03
klem4   Перебор с рекурсией, код неважнецкий, но работает ...   6.12.2009 17:02
Lapp   Перебор с рекурсией, код неважнецкий, но работаетК...   6.12.2009 19:34
klem4   f[1]._new(2,1,'a'); f...   6.12.2009 21:07
Unconnected   А теперь возникает вопрос: с какой вероятностью Ек...   6.12.2009 21:26
Екатерина7   поверят, я постараюсь разобраться)) Добавлено чер...   6.12.2009 21:51
Lapp   проверим потом на практике с какой вероятностью))Е...   6.12.2009 22:36
volvo   Ну, так со включенным-то работать не будет :) Выле...   6.12.2009 23:43
klem4   К сожалению не знаю как еще дин. массивы в таком в...   7.12.2009 8:31
Екатерина7   спасибо, Lapp:)) Добавлено через 5 мин. я в при...   7.12.2009 19:33
Екатерина7   Lapp, что-то я вообще не могу понять этой программ...   10.12.2009 20:31
Unconnected   Екатерина7, какой у тебя уровень программирования ...   10.12.2009 21:09
Екатерина7   извини, но хватит говорить про мой уровень програм...   11.12.2009 8:43
Lapp   заставляют задуматься,Ты задумывайся, никто не про...   11.12.2009 11:03
Екатерина7   ммм. да, это поняла.. такой вопрос: то, что выводи...   11.12.2009 12:22
Lapp   что выводится в результатах, Done:... квадрат с б...   11.12.2009 13:33
Екатерина7   а почему Done выводится одно и тоже бесконечное ко...   11.12.2009 15:31
Lapp   а почему Done выводится одно и тоже бесконечное ко...   11.12.2009 22:10
Екатерина7   результаты выполнения: a=2 b=2 ab=4 ...   12.12.2009 9:17
Lapp   результаты выполнения:Это неполный результат. 14 с...   12.12.2009 11:19
Екатерина7   нет, не в ручную.. все печатала.. хорошо, проверю.   12.12.2009 17:17
Екатерина7   а что делает function Overlap?   13.12.2009 10:19
Екатерина7   я задала n=6, все получается нормально, без вот эт...   13.12.2009 12:38
Lapp   я задала n=6, все получается нормально, без вот эт...   14.12.2009 1:54
Екатерина7   так там не должно быть этих скобок? или они должны...   14.12.2009 23:52
Lapp   ааааа.. эти скобочки не должны быть углом?Конечно,...   15.12.2009 0:20
Екатерина7   да, если n брать =8, добавляются скобочки и они уг...   15.12.2009 9:41
Unconnected   У меня при N=8 первая комбинация такая получается ...   15.12.2009 13:00
Екатерина7   все, получается. да Добавлено через 7 мин. идея...   15.12.2009 19:49
Lapp   У меня при N=8 первая комбинация такая получается ...   16.12.2009 0:51
Екатерина7   потому что сначала не получалось..( Добавлено чер...   16.12.2009 7:33
Lapp   потому что сначала не получалось..(Что не получало...   16.12.2009 10:03
Екатерина7   а для чего вот это? const r0: tRectangle=(a:1; ...   22.12.2009 21:56
Unconnected   Объявление переменных r0 и l0 типами tRectangle ...   22.12.2009 22:25
Екатерина7   заметила. а что такое NoOne? [b]Добавлено через ...   22.12.2009 22:52
Екатерина7   я так поняла, что function Overlap(r1: tRectangle;...   22.12.2009 23:07
Lapp   я так поняла, что function Overlap(r1: tRectangle;...   23.12.2009 5:58
Екатерина7   спасибо всем огромное, кто принимал участие в реше...   23.12.2009 16:01
Unconnected   Ну, насколько я понял, NoOne - булевая переменная,...   22.12.2009 23:04


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

 



- Текстовая версия 22.06.2025 22:12
Хостинг предоставлен компанией "Веб Сервис Центр" при поддержке компании "ДокЛаб"