Задача о находжении минимального количества квадратов

Дан прямоугольник с целочисельными длинами сторон. Задача состоит в находжении минимального количества квадратов на которые можно разрезать данный прямоугольник.
Есть способ всегда "откусывать" квадрат наибольшей возможной площади, но он не дает минимальности.
Для примера 5х6 этот способ даст один квадрат со стороной 5 и 4-ре со сторнами 1.
Минимальное количество на самом деле: 2 по 3, и 3 по 2.
http://i.pixs.ru/storage/7/6/5... 799765.png

0

Дан прямоугольник с целочисельными длинами сторон. Задача состоит в находжении минимального количества квадратов на которые можно разрезать данный прямоугольник.
Есть способ всегда "откусывать" квадрат наибольшей возможной площади, но он не дает минимальности.
Для примера 5х6 этот способ даст один квадрат со стороной 5 и 4-ре со сторнами 1.
Минимальное количество на самом деле: 2 по 3, и 3 по 2.
http://i.pixs.ru/storage/7/6/5... 799765.png

	Комментарий модератора
	Правила, 4.12. Картинки и любые другие файлы загружайте на форум, во избежание их удаления или потери на сторонних ресурсах.

0

откуда такая задача?

Добавлено через 19 минут
у меня появился такой вариант: дан квадрат прямоугольник nxm. n*m = k. вот у нас есть k (клеток, в примере на рисунке 30), что делаем - перебираем все варианты квадратов сверху вниз, начиная с корень из k, пытаясь заполнить пространство такими же квадратами, например: k = 30. 5 < sqrt(k) < 6. тогда начинаем с 5: 5*5 = 25. вычитаем из 30. получаем 5. и рекурсивно пытаемся заполнить квадратами эти 5: 2 * 2 + 1 * 1 = 5, но каким-то образом надо сделать проверку, что этот вариант нас не устраивает, тогда надо уменьшить "максимальный" квадрат, то есть 2x2 -> 1x1, и заполняем этот прямоугольник из 5.
Получили разложение 30 = 5x5 + 1x1 + 1x1 + 1x1 + 1x1 +1x1. Далее уменьшаем максимальный квадрат 5x5 -> 4x4, делаем то же самое: 30 = 4x4 + 14, 14 = 3x3 + 5.
Каким образом проверять, влезет ли - может, передавать длины и ширину прямоугльника. например:
30 = 5x5 + 5, тогда передаем для анализа прямоугольник со сторонами 5, 1. понятно, что 2x2 туда не влезет.
таким образом мы получим набор вариантов, и выберем с минимальным значением. как задачу выполнить без перебора, пока не знаю, может ни как.
вот как-то сумбурно написал, но вроде имею можно уловить.

0

Перебором конечно можно. Тогда фактически задача сведется к представлению числа (площади прямоугольника S=MxN) в виде суммы чисел (правда только тех что сами являются квадратами натуральных чисел, но тогда количество возможных вариантов растет слишком быстро с ростом S.

Если НСД(M,N)=1, то вообще кошмар. Задача о разбиении числа. (http://ru.wikipedia.org/wiki/%... 0%BB%D0%B0)

Может наоборот начинать из наихудшего варианта и использовать диаграмму Юнга, но как.

________________________________________ ________________
а задача, можно сказать неоткуда)

0

Хорошая задача. Видел оценки в книге Яглома Как "разрезать квадрат?", стр 87 и далее.

0

Сообщение от azbest Для примера 5х6 этот способ даст один квадрат со стороной 5 и 4-ре со сторнами 1.

Всё равно 5 квадратов получается ведь???? Не понял.... Дайте другой какой нить пример

0

Сообщение от PoMa_HaB Всё равно 5 квадратов получается ведь????

Извините там не 4, а 5-ть квадратов 1х1 и того в сумме 6.

0

вот картинка с разрезами

0

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

0

Предлагаю алгоритм разбиения целочисленного прямоугольника со сторонами a и b на минимальное число квадратов, основанный на полном переборе.

1) Пусть a<b. Если a=b, то достаточно одного квадрата. Рассмотрим все возможные разбиения числа ab в сумму квадратов
где - положительные числа, не превосходящие a,
не обязательно различные.
2) Для каждого такого разбиения числа ab проверяем можно ли выложить прямоугольник со сторонами a, b из квадратов со сторонами . Проверку делаем тоже полным перебором:
a) Каждый квадрат последовательно пытаемся уложить на прямоугольник.
b) Положение квадрата полностью определяется положением, скажем, левой верхней вершины. Эта вершина помещается в узел целочисленной сетки на прямоугольнике.
c) Если квадраты замощают прямоугольник, то найдено разбиение прямоугольника.
d) Переходим к следующему разбиению числа ab.
e) На каждом шаге число квадратов сравниваем с минимальным среди уже рассмотренных разбиений.

0

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

0

Сообщение от school_bot да и вообще, метод откусывания дает неплохое приближение. его кол-во участвующих квадратов можно использовать для откидывания вариантов при переборе.

Следуя Яглому, обозначим k(m,n) - минимальное число квадратов, замощающих прямоугольник mn.
Так вот известно, что k(32,33)<10. Метод откусывания однако дает лишь k(32,33)<34.

Предлагаю, такое сокращение перебора. Разбиваем одно из чисел так, чтобы свести дело к двум прямоугольникам меньших размеров.
Решить задачу для каждого из них и получить оценки.
Скажем для случая 32*33 имеем 33=16+17. Получаем два прямоугольника 16*32 и 17*32.
Очевидно, что k(16,32)=2 и можно аналогично продолжить для k(17,32).

Это как видно известная задача. Следил и здесь за обсуждением,
но сегодня появились комментарии, которых еще вчера не было видно. Кто понимает в чем дело?

0

Сообщение от kabenyuk Кто понимает в чем дело?

объединили одни и те же топики из разных разделов

0