Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > IT форум > Помощь студентам
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 06.11.2007, 00:38   #1
Carbon
JAVA BEAN
Участник клуба
 
Аватар для Carbon
 
Регистрация: 22.04.2007
Сообщений: 1,329
По умолчанию 5 прямоугольников

Народ. Здрасьте. У кого есть идеи решения следующей задачи:

5 прямоугольников заданы своими шириной и высотой. Определить, можно ли из них сложить 1 большой прямоугольник без отверстий, используя все 5 прямоугольников. Прямоугольники можно вращать.
Carbon вне форума Ответить с цитированием
Старый 06.11.2007, 01:41   #2
AND
 
Регистрация: 05.11.2007
Сообщений: 8
По умолчанию

Есть кое какие мыслишки... вообщем.
Раз нам известны все стороны, значит нам известна площадь получившегося прямоугольника. А дальше методом перебора находим сумму всех сторон от 1 до 5 в различных последовательностях, так как прямоугольников пять. В итоге сравниваем произведение переборов и если оно равно площади БОЛЬШОГО прямоугольника, то данный вариант возможен.
AND вне форума Ответить с цитированием
Старый 06.11.2007, 12:19   #3
Carbon
JAVA BEAN
Участник клуба
 
Аватар для Carbon
 
Регистрация: 22.04.2007
Сообщений: 1,329
По умолчанию

Стоп! Стоп! Стоп! Во-первых не одну сумму, а от 1 до 5 (по количеству возможных слоёв) и не всех сторон, а некоторых, т.к. в общем случае они не складываются в 1 ряд. Более того, суммы нужно находить по двум измерениям. И вообще, ну нашли мы суммы, но нужно как-то определить, что получившееся чудо архитектуры - это прямоугольник.
Carbon вне форума Ответить с цитированием
Старый 06.11.2007, 16:52   #4
AND
 
Регистрация: 05.11.2007
Сообщений: 8
По умолчанию

могут и в ряд накладываться, в том случае если они одинаковые... да, если я правильно понял выражения "два измерения", То суммы на мой взгляд нужно искать исходя из того, что у прямоугольника две разных стороны. НУ а если мы нашли суммы, то дальше мы вычитаем из получившихся сумм стороны прямоугольников и узнаём в какой последовательности они находятся( по сторонам должен быть 0 в итоге).
AND вне форума Ответить с цитированием
Старый 07.11.2007, 08:20   #5
SuperVisor
Павел Сергеевич
Форумчанин
 
Регистрация: 05.11.2006
Сообщений: 665
По умолчанию

Вы правильно мыслите... Но перемудрили немного. Задачка средней сложности.
1. Находим площадь всех прямоугольников.
2. Из полученной площади вычисляем возможные варианты БОЛЬШОГО прямоугольника, наращивая одну сторону (допутим площадь получилась 16: варианты 1х16, 2х8, 4х4)
3. Перебираем варианты полученных прямоугольников:
Если меньшая сторона одного из искомых прямоугольников больше меньшей стороны большего прямоугольника - вариант отпадает.
Нет - начинаем попытку построения фигур в большем прямоугольнике начиная с большего искомого прямоугольника.
Третий пункт очень объемен за счет перебора. Нужна будет помощь - чем смогу.
Познавая других, мы познаем себя.
С'est la vie...
SuperVisor вне форума Ответить с цитированием
Старый 07.11.2007, 13:02   #6
Carbon
JAVA BEAN
Участник клуба
 
Аватар для Carbon
 
Регистрация: 22.04.2007
Сообщений: 1,329
По умолчанию

В принципе, задача с рекурсией.

Цитата:
Нет - начинаем попытку построения фигур в большем прямоугольнике начиная с большего искомого прямоугольника.
А может, не пытаться впихнуть какой-то прямоугольник, а начинать с верхнего края большого прямоугольника подбирать туда прямоугольники, а затем вырезать часть и т.д.
Carbon вне форума Ответить с цитированием
Старый 07.11.2007, 20:15   #7
SuperVisor
Павел Сергеевич
Форумчанин
 
Регистрация: 05.11.2006
Сообщений: 665
По умолчанию

Цитата:
Сообщение от Carbon Посмотреть сообщение
А может, не пытаться впихнуть какой-то прямоугольник, а начинать с верхнего края большого прямоугольника подбирать туда прямоугольники, а затем вырезать часть и т.д.
Не поверишь - то что я предлагаю работает. Однажды я подобное уже решал, правда на паскале.
Познавая других, мы познаем себя.
С'est la vie...
SuperVisor вне форума Ответить с цитированием
Старый 07.11.2007, 22:16   #8
Carbon
JAVA BEAN
Участник клуба
 
Аватар для Carbon
 
Регистрация: 22.04.2007
Сообщений: 1,329
По умолчанию

А что значит "попытка построения фигур"?
Carbon вне форума Ответить с цитированием
Старый 08.11.2007, 07:44   #9
SuperVisor
Павел Сергеевич
Форумчанин
 
Регистрация: 05.11.2006
Сообщений: 665
По умолчанию

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

Да, кстати, размешение обязательно должно происходить от большего по площади прямоугольника к меньшему - это много упростит задачу.
Познавая других, мы познаем себя.
С'est la vie...

Последний раз редактировалось SuperVisor; 08.11.2007 в 07:46.
SuperVisor вне форума Ответить с цитированием
Старый 08.11.2007, 08:28   #10
puporev
Старожил
 
Регистрация: 13.10.2007
Сообщений: 2,740
По умолчанию

Как вариант мне кажется можно посмотреть следующий способ решения.
Если из пяти прямоугольников можно сложить большой прямоугольник, то это можно сделать пятью способами (количество вариантов разложения числа 5 на слагаемые): 1+1+1+1+1; 1+1+1+2; 1+1+3; 1+4; 1+2+2.
В первом случае нужно посмотреть есть ли у всех прямоугольников одинаковые стороны. Во втором - есть ли у 3х прямоугольников равные сторны, а у двух оставшихся сумма каких либо сторон равна выбранной стороне первых трех прямоугольников и т.д. Если бы задача была поставлена так, что даны пять конкретных прямоугольников и требуется определить можно ли из них составить прямоугольник, то я бы ее решал так. Хотя если решать в общем виде, то может я и неправ.
puporev вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Вывод прямоугольников на С. Ошибка зацикливания. KirTheCruel Помощь студентам 7 27.05.2008 21:19
Заполнение двумерного массива прямоугольников случайными изображениями Mischa Помощь студентам 1 11.03.2008 21:58