Задачка такая вспомнилась... Про квадраты :)

Вспомнил вот задачку, в свое время решал в муках. Может она сводится к какой-либо стандартной задаче, а я и не в курсе? А то, то, что я в конце концов написал, было дико тормознутым

Параметры: m,n,k

Рассмотрим прямоугольник который состоит из n*m клеток. Этот прямоугольник надо весь закрыть квадратами таким образом, чтобы выполнялись следующие условия:

- Длины сторон всех квадратов натуральные числа;
- Стороны квадратов проходят точно по краям клеток из которых состоит прямоугольник;
- Квадраты не перекрывают друг друга;
- В результате все клетки прямоугольника должны быть закрыты квадратами;
- Среди используемых квадратов хотя бы один должен быть с длиной стороны равной k;

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

Например, если n=5, m=3, k=2 то решение = 4.

Сообщение отредактировано: Kotyarich - 28.03.02, 13:26

Хорошая задачка Только простая.
По хорошему стоит еще в начале поставить проверку на то, что m>=n, и если это не так то менять их местами. Но вобщем я это по ходу постарался обеспечить. Единственно, чтобы в самом начале денные правильно поставили. Не компилял, но вроде должно работать.

<br>//dok - надо ли на данном этапе вписывать квадрат k или нет<br>int split (int n, int m, int k, int dok)<br>{<br>     cout<<"Processing "<<m<<" x "<<n<<" square\n";<br>     if ( (m-n<k) && (dok == 1) )<br>     {<br>           cout<<"Cut "<<k<<" x "<<k<<" square \n";<br>           return ( 1 + split(k, n-k, k, 0) + split(n, m-k, k, 0) );<br>     }<br>     else<br>     {<br>           cout<<"Cut "<<n<<" x "<<n<<" square \n";<br>           if (n==m) return 1;<br>           return ( 1 + split(n, m-n, k, dok) );<br>     }<br>}<br>

Сообщение отредактировано: murph - 29.03.02, 11:56

Если я правильно понял твою идею, то ты ошибся. Это первое что пришло и мне в голову - берем наибольший квадрат по наименьшей стороне прямоугольника, потом делим стандартным образом прямоугольник на квадраты, попутно как-то засовывая квадрат К. Проблема в том, что не обязательно при конфигурации с наименьшим количеством квадратов длина стороны хотя бы одного из них будет равна наименьшей длине сторон прямоугольника. Мешает квадрат К, который необязательно будет совпадать с квадратом полученным в результате работы алгоритма разбиения на квадраты, а только в этом случае мы получим оптимальную конфигурацию (с наименьшим количеством квадратов) по твоему алгоритму. Вот еще примеры, которые твоя прога не воспроизведет скорее всего (если я правильно понял идею ):
m = 17 n = 17 k = 3                         Answer: 12
m = 23 n = 23 k = 2                         Answer: 13
m = 19 n = 19 k = 6                         Answer: 13
m = 13 n = 13 k = 4                       Answer: 11
m = 25 n = 25 k = 1                       Answer: 14
Есть картинки, с ними понятнее, только похоже тут их не выложить...

Приведи еще десяток разнородных результатов для тестирования. А то у тебя все квадраты.

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

Кстати, tatar - это ты?

Сообщение отредактировано: murph - 29.03.02, 16:37

Цитата

Кстати, tatar - это ты?

Я знал что ты это спросишь Хороший сайт у Быстрицкого...


Примеров больше нет. Я сейчас обнаружил, что потерял ту прогу Картинки можно посмотреть хере:

http://www.gradetools.com/oop/papildus.htm

там не по-русски написано, но картики те самые.

От подхода отказываться не стоит. В конце концов у меня вышло то же самое, только в трех измерениях так сказать Мой подход следующий:
0: int TEMP = MAX_INTEGER; int X;
1: Берем квадрат К ставим в верхний левый угол прямоугольника
2: Разбиваем остаток прямоугольника на квадраты с помощью аналога твоего сплита.
3: Считаем квадраты и запоминаем в X
4: IF Х < TEMP THEN TEMP = X
5: IF K в правом нижнем углу - говорим TEMP и умираем ELSE сдвигаем К на клеточку влево(или на клеточку вниз и в начало строки, если он дошел до конца строчки) и прыгаем на 1

Как видишь тупой брут-форс. Кроме того, кто-то мне сказал что при каких-то там условиях оно ошибается. Может от зависти. Работу я сдвл короче, но осадок остался
Все это тормозило СТРАШНО. Почему и возник вопрос, может кто сталкивался или идейку подкинет как можно было бы оптимизировать.