Разделить квадрат на маленькие квадраты

Question

У меня большой квадрат. И я хотел бы разделить этот квадрат на маленькие квадраты. Мне нужны все возможные комбинации. Я знаю, что существует бесконечное число комбинаций, но у меня есть одно ограничение. Я установил размер для наименьшего квадрата.

Я могу реализовать это, используя грубую силу. Но это слишком долго.

Есть ли предпочтительный алгоритм для этой задачи?

Спасибо!

Answer 1

Ну, у этой проблемы есть решение, только если мы сделали 2 предположения (в противном случае есть бесконечные комбинации)

1) самый маленький квадрат имеет фиксированный размер
2) также установлен способ вырезания большого квадрата, как если бы вы поместили квадрат в сетку, линии которой разделены размером маленького квадрата.

Есть и третье предположение, которое немного облегчит проблему

3) Большой квадрат имеет сторону в K раз большую, чем маленький квадрат. Где K - целое число.

Если оба предположения верны, мы можем продолжить:

Найдите количество N (N beign integer) наименьших квадратов: квадраты с размером N * small-size

 if ((big-size % N*small-size)==0)
    Number += (big-size / N*small-size)^2
 else
    Number += ((big-size / N*small-size)^2) * (big-size % N*small-size)

* (большой размер% N small-size) в условии else есть, потому что, если bigsquare не делится на N, при «сетке» большого квадрата с gid-width N останется «дробная часть». Таким образом, мы можем начать деление снова (повторная сетка), но со смещением 1, 2 или N маленьких шагов. Количество шагов (большой размер% N маленький размер).

Опять же, эти шаги верны, только если были приняты 3 допущения.

Answer 2

Моя математика немного размыта, но если у вас есть квадрат (n ^ 2), то у вас есть длина одной стороны (n).

Начиная с n вы можете рассчитать все факторы для этого числа и использовать их в качестве сторон для меньших квадратов ...

* 1006 Е.Г. *

n^2 = 44100
n = 210

Factors of n = x=2,x=3,x=5,x=7, x= ... and so on.

Таким образом, вы меньше квадратов для каждого фактора

x=2 : x^2 = 4 : 44100 / 4 = 11025 small squares
x=3 : x^2 = 9 : 44100 / 9 = 4900 small squares
x=5 : x^2 = 25 : 44100 / 25 = 1764 small squares
x=7 : x^2 = 49 : 44100 / 49 = 900 small squares

и т. Д.

Answer 3

Нет «бесконечных» комбинаций. На самом деле, число может быть большим, но ограниченным. Более того, если вам нужны строгие квадраты (ширина = высота, а не просто прямоугольники), их еще меньше, поскольку вы должны разделить исходный квадрат (со стороны L) на одинаковые целые числа с обеих сторон, иначе вы получите прямоугольники также. Если вы работаете с целыми числами, я бы порекомендовал просто разделить L на 2, 3, ... M (L / M = минимальная длина внутреннего квадрата).