Я имею ширину x ширины прямоугольника и N квадратов того же неизвестного размера. Я должен определить максимальный размер этих квадратов и количество строк и столбцов, чтобы они идеально соответствовали (UPD. Я имею в виду не заполнять все пространство, а заполнять как можно больше места) в прямоугольник.
Я думаю, математически это выглядит так:
x * size <= width //x - number of columns y * size <= height //y - number of rows x * y max //size - size of squares Конечный результат может выглядеть следующим образом:
1 1 1 1 1 1 1 1 1 1 0 0
Где 1 = squares , 0 = пустое пространство`.
На самом деле я видел подобные проблемы, но с предопределенным размером квадратов. Кроме того, я написал несколько неуклюжий алгоритм, но его результаты очень неудовлетворительны ..
Изменить: Мой текущий алгоритм:
Я пробовал много вариантов, но я не могу заставить его работать безупречно для всех случаев. На самом деле, я могу пройти все возможные размеры, но мне не нравится этот подход.
// to make things more simple I put width as bigger size int biggerSize = this.ClientSize.Width; int lowerSize = this.ClientSize.Height; int maxSize = int.MinValue; int index = 0; int index2 = 0; // find max suitable size for (int i = _rects.Count; i > 0; i--) { int size = biggerSize / i; int j = (int)Math.Floor((double)lowerSize / size); if (i * j >= _boards.Count && size > maxSize) { maxSize = size; index = (int)i; index2 = (int)j; } } int counter = 0; // place all rectangles for (int i = 0; i < index; i++) { for (int j = 0; j < index2; j++) { if (counter < _rects.Count) { _rects[counter].Size = new Size(maxSize, maxSize); _rects[counter].Location = new Point(i * maxSize, j * maxSize); } counter++; } }
Ваш вопрос несовместим. Во-первых, вы указываете проблему как «определить максимальный размер этих квадратов и количество строк и столбцов, чтобы они идеально вписывались в прямоугольник». (выделено курсивом).
Но тогда вы даете образец конечного результата, который позволяет пустое пространство.
Так что это?
Если вам нужны квадраты, чтобы они идеально располагались в прямоугольнике без пустого пространства и квадратов, выходящих за пределы прямоугольника, размер максимального квадрата был бы равен наибольшему общему делителю длины и ширины прямоугольника.
См. http://en.wikipedia.org/wiki/Greatest_common_divisor#A_geometric_view
Эта проблема возникла недавно в проекте, над которым я работал. Вот решение, которое было определено:
int numItems; // the number of squares we need to pack in. double rectWidth; // the width of the space into which we want to pack our squares. double rectHeight; // the height of the space into which we want to pack our squares. double tableRatio = rectWidth / rectHeight; double columns = sqrt(numItems * tableRatio); double rows = columns / tableRatio; columns = ceil(columns); // the number of columns of squares we will have rows = ceil(rows); // the number of rows of squares we will have double squareSize = rectWidth / columns; // the size of each square.