|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
|
Опции темы | Поиск в этой теме |
06.11.2007, 00:38 | #1 |
JAVA BEAN
Участник клуба
Регистрация: 22.04.2007
Сообщений: 1,329
|
5 прямоугольников
Народ. Здрасьте. У кого есть идеи решения следующей задачи:
5 прямоугольников заданы своими шириной и высотой. Определить, можно ли из них сложить 1 большой прямоугольник без отверстий, используя все 5 прямоугольников. Прямоугольники можно вращать. |
06.11.2007, 01:41 | #2 |
Регистрация: 05.11.2007
Сообщений: 8
|
Есть кое какие мыслишки... вообщем.
Раз нам известны все стороны, значит нам известна площадь получившегося прямоугольника. А дальше методом перебора находим сумму всех сторон от 1 до 5 в различных последовательностях, так как прямоугольников пять. В итоге сравниваем произведение переборов и если оно равно площади БОЛЬШОГО прямоугольника, то данный вариант возможен. |
06.11.2007, 12:19 | #3 |
JAVA BEAN
Участник клуба
Регистрация: 22.04.2007
Сообщений: 1,329
|
Стоп! Стоп! Стоп! Во-первых не одну сумму, а от 1 до 5 (по количеству возможных слоёв) и не всех сторон, а некоторых, т.к. в общем случае они не складываются в 1 ряд. Более того, суммы нужно находить по двум измерениям. И вообще, ну нашли мы суммы, но нужно как-то определить, что получившееся чудо архитектуры - это прямоугольник.
|
06.11.2007, 16:52 | #4 |
Регистрация: 05.11.2007
Сообщений: 8
|
могут и в ряд накладываться, в том случае если они одинаковые... да, если я правильно понял выражения "два измерения", То суммы на мой взгляд нужно искать исходя из того, что у прямоугольника две разных стороны. НУ а если мы нашли суммы, то дальше мы вычитаем из получившихся сумм стороны прямоугольников и узнаём в какой последовательности они находятся( по сторонам должен быть 0 в итоге).
|
07.11.2007, 08:20 | #5 |
Павел Сергеевич
Форумчанин
Регистрация: 05.11.2006
Сообщений: 665
|
Вы правильно мыслите... Но перемудрили немного. Задачка средней сложности.
1. Находим площадь всех прямоугольников. 2. Из полученной площади вычисляем возможные варианты БОЛЬШОГО прямоугольника, наращивая одну сторону (допутим площадь получилась 16: варианты 1х16, 2х8, 4х4) 3. Перебираем варианты полученных прямоугольников: Если меньшая сторона одного из искомых прямоугольников больше меньшей стороны большего прямоугольника - вариант отпадает. Нет - начинаем попытку построения фигур в большем прямоугольнике начиная с большего искомого прямоугольника. Третий пункт очень объемен за счет перебора. Нужна будет помощь - чем смогу.
Познавая других, мы познаем себя.
С'est la vie... |
07.11.2007, 13:02 | #6 | |
JAVA BEAN
Участник клуба
Регистрация: 22.04.2007
Сообщений: 1,329
|
В принципе, задача с рекурсией.
Цитата:
|
|
07.11.2007, 20:15 | #7 |
Павел Сергеевич
Форумчанин
Регистрация: 05.11.2006
Сообщений: 665
|
Не поверишь - то что я предлагаю работает. Однажды я подобное уже решал, правда на паскале.
Познавая других, мы познаем себя.
С'est la vie... |
07.11.2007, 22:16 | #8 |
JAVA BEAN
Участник клуба
Регистрация: 22.04.2007
Сообщений: 1,329
|
А что значит "попытка построения фигур"?
|
08.11.2007, 07:44 | #9 |
Павел Сергеевич
Форумчанин
Регистрация: 05.11.2006
Сообщений: 665
|
Т.е. размещаем больший из меньших прямоугольников сначала в одном положении и пытаемся воткнуть другой рядом с ним так, чтобы они закрыли (В лучшем случае) целый прямоугольник от общей площади (вычисленного прямоугольника), если не получается - переворачиваем первую фигуру, повторяем операцию, сравниваем количество незакрытой площади и возможность размещения в ней какойлибо фигуры...
Как вариант - использование двумерного массива для программной "визуализации" размещений. Нам массивы использовать было нельзя. =) Да, кстати, размешение обязательно должно происходить от большего по площади прямоугольника к меньшему - это много упростит задачу.
Познавая других, мы познаем себя.
С'est la vie... Последний раз редактировалось SuperVisor; 08.11.2007 в 07:46. |
08.11.2007, 08:28 | #10 |
Старожил
Регистрация: 13.10.2007
Сообщений: 2,740
|
Как вариант мне кажется можно посмотреть следующий способ решения.
Если из пяти прямоугольников можно сложить большой прямоугольник, то это можно сделать пятью способами (количество вариантов разложения числа 5 на слагаемые): 1+1+1+1+1; 1+1+1+2; 1+1+3; 1+4; 1+2+2. В первом случае нужно посмотреть есть ли у всех прямоугольников одинаковые стороны. Во втором - есть ли у 3х прямоугольников равные сторны, а у двух оставшихся сумма каких либо сторон равна выбранной стороне первых трех прямоугольников и т.д. Если бы задача была поставлена так, что даны пять конкретных прямоугольников и требуется определить можно ли из них составить прямоугольник, то я бы ее решал так. Хотя если решать в общем виде, то может я и неправ. |
|
Опции темы | Поиск в этой теме |
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Вывод прямоугольников на С. Ошибка зацикливания. | KirTheCruel | Помощь студентам | 7 | 27.05.2008 21:19 |
Заполнение двумерного массива прямоугольников случайными изображениями | Mischa | Помощь студентам | 1 | 11.03.2008 21:58 |