Размер квадратов Max для неизвестного числа в прямоугольнике

Концептуально:

• начать с 1 квадрата
• Для каждого дополнительного квадрата, если у вас нет комната в вашем сетке, сжать существующей коробки достаточно, чтобы сделать место для дополнительной строки или столбца.

псевдокод: дан прямоугольник M x N для заполнения K квадратами

// initial candidate grid within the rectangle
h=1
w=1
maxsquares=1
size=min(M,N) //size of the squares
while K > maxsquares
  if M/(h+1) >= N/(w+1)
    h=h+1
  else
    w=w+1
  endif
  maxsquares=h*w
  size=min(M/h,N/w)
done
print size

Вероятно, есть более быстрые способы перейти к ответу для очень большого K, но я не могу их придумать. Если вы знаете, что M и N являются целыми числами, могут быть еще более быстрые методы.

Это проблема упаковки. Оптимальные решения найти сложно. См., Например, Упаковка N квадратов в квадрат .

Вы можете вычислить (оптимистичную) верхнюю границу, разделив общую поверхность на количество квадратов: sqrt (ширина * высота / n) .

Не могли бы вы подробнее рассказать, как вы определяете заливку? Если я последую вашему описанию (большое «если»), то окажется, что многие из описываемых вами случаев на самом деле не заполняют прямоугольник. Например, вы говорите, что 2 квадрата в прямоугольнике 100 * 100 будут 50 * 50. Если я правильно понимаю вашу конфигурацию, они будут размещены на «диагонали» этого прямоугольника. Но тогда и в этом прямоугольнике будет два «промежутка» размером 50 * 50. Это не то, что я считаю «заполнением» прямоугольника. Вместо этого я бы сформулировал проблему как максимально возможный размер для 2 (квадратов равного размера), ограничивающая рамка которых будет 100 * 100 (при условии, что каждый квадрат должен контактировать хотя бы с одним другим квадратом?).

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

Кроме того, вы можете написать функциональный интерфейс для этого расчета? Вам нужно сделать это для n возможных квадратов с учетом размеров ограничивающей рамки?

x = max(rectHeight/numberOfSquares, rectangleLength/numberOfSquares)

if x <= retangleHeight && x <= rectangleLength then
  squareSideLength = x
else
  squareSideLength = min(rectangleHeight, rectangleLength)

Приведенные значения:

N - number of tiles
a, b - sides of the rectangle

сторона плитки может быть вычислена с помощью этой функции:

def maxSize(n: Int, a: Int, b: Int) = {
  var l = 0
  for (i <- 1 until a.min(b)) { // 
    val newL = (a.min(b) / i).min( (a.max(b) * i)/n )
    if (l < newL && ((a.min(b)/newL) * (a.max(b)/newL) >= n )  )
      l = newL
  }
  return l
}

Я предположил, что вы не собираетесь сделать плитки меньше 1x1, независимо от меры 1

сначала вы начинаете с размера 0:

l = 0

, затем вы выполняете итерацию от 1 до K столбцов плиток, где

K = min(a, b)

для каждой итерации вычисляет новую максимальную сторону тайл, использующий эту формулу

val newL = ( a.min(b) / i ).min( (a.max(b) * i)/n )

эта формула принимает меньшее из этих двух значений:

1. min(a, b)/i -- maximum length of a tile if there are i columns in the smaller side of the rectangle
2. (i * max(a, b))/n -- maximum length of a tile if there are i columns and n tiles in the bigger side of the rectangle

если кандидат newL больше, чем начальное значение l, и максимально возможное количество тайлов, которые могут быть помещены в квадрат без перекрытия, больше или равно количеству плиток n, тогда

l = newL

в конце верните l

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

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

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

Предположим, мы уже знаем, что 10 квадратов должны быть размещены в первом ряду, и это идеально соответствует ширине. Тогда длина стороны будет ширина / 10 . Таким образом, мы можем поместить м = высота / длина стороны квадратов в первый столбец. Эта формула может сказать, что мы можем разместить 2,33 квадрата в первом столбце. Невозможно разместить 0,33 квадрата, мы можем разместить только 2 квадрата. Реальная формула такова: м = пол (высота / длина стороны) .

Не очень быстрый (но НАМНОГО быстрее, чем попытка каждой комбинации) алгоритм состоит в том, чтобы попытаться сначала разместить 1 квадрат в первой строке / столбец, а затем посмотрим, сможем ли мы разместить достаточно квадратов в прямоугольнике. Если это не сработает, мы пробуем 2 квадрата в первой строке / столбце и т. Д., Пока не сможем уместить желаемое количество плиток.

Я думаю, что существует алгоритм O (1), если вам разрешено выполнять арифметические операции в O (1), но я пока не понял этого.

Вот версия этого алгоритма на Ruby. Этот алгоритм равен O (sqrt (# плиток)), если прямоугольник не очень тонкий.

def squareside(height, width, tiles)
  n = 0
  while true
    n += 1
    # case 1: the squares fill the height of the rectangle perfectly with n squares
    side = height/n
    m = (width/side).floor # the number of squares that fill the width
    # we're done if we can place enough squares this way
    return side if n*m >= tiles
    # case 2: the squares fill the width of the rectangle perfectly with n squares
    side = width/n
    m = (height/side).floor
    return side if n*m >= tiles
  end
end

Вы также можете использовать двоичный поиск для этого алгоритма. В этом случае это O (журнал (количество плиток)).

Разделите длинную сторону на количество плиток. Используйте более короткую сторону в качестве размера плитки. Presto! # плиток.

Rectagle = 200 x 10
Each tile is 10 x 10 (length of shorter side)
200/10 = 20 (number of tiles needed)

Следующая функция вычисляет плитку максимального размера для данной информации.

Если тот факт, что она написана на Python, затрудняет понимание, дайте мне знать в комментарии и Я попытаюсь сделать это на каком-нибудь другом языке.

import math
from __future__ import division

def max_tile_size(tile_count, rect_size):
    """
    Determine the maximum sized tile possible.

    Keyword arguments:
    tile_count -- Number of tiles to fit
    rect_size -- 2-tuple of rectangle size as (width, height)
    """

    # If the rectangle is taller than it is wide, reverse its dimensions
    if rect_size[0] < rect_size[1]:
        rect_size = rect_size[1], rect_size[0]

    # Rectangle aspect ratio
    rect_ar = rect_size[0] / rect_size[1]

    # tiles_max_height is the square root of tile_count, rounded up
    tiles_max_height = math.ceil(math.sqrt(tile_count))

    best_tile_size = 0

    # i in the range [1, tile_max_height], inclusive
    for i in range(1, tiles_max_height + 1):

        # tiles_used is the arrangement of tiles (width, height)
        tiles_used = math.ceil(tile_count / i), i

        # tiles_ar is the aspect ratio of this arrangement
        tiles_ar = tiles_used[0] / tiles_used[1]

        # Calculate the size of each tile
        # Tile pattern is flatter than rectangle
        if tile_ar > rect_ar:
            tile_size = rect_size[0] / tiles_used[0]
        # Tile pattern is skinnier than rectangle
        else:
            tile_size = rect_size[1] / tiles_used[1]

        # Check if this is the best answer so far
        if tile_size > best_tile_size:
            best_tile_size = tile_size

    return best_tile_size

print max_tile_size(4, (100, 100))

Алгоритм в общих чертах можно описать следующим образом

• Если прямоугольник выше, чем ширина, переверните его так, чтобы он шире, чем был выше.
• ] Вычислите s , квадратный корень из числа плиток с округлением в большую сторону. (В коде названо tile_max_height .)
• Цикл, где i переходит от 1 до с включительно:
  • Постройте сетку из квадратов, равную количеству плиток / i квадратов в ширину и i квадратов в высоту. (Округлите все вверх. Это «подкладывает» недостающие плитки, например, используя 2 плитки на 2 плитки, когда ваше общее количество плиток равно 3.)
  • Сделайте эту сетку как можно больше. (Рассчитайте это, используя соотношение сторон.) Определите размер одной плитки.
  • Используя этот размер, определите общую площадь, покрытую плитками.
  • Проверьте, является ли это лучшей общей площадью на данный момент; если это так, сохраните размер квадрата
• Возвратите этот размер квадрата

Это, вероятно, один из наиболее быстрых алгоритмов, перечисленных здесь, поскольку он вычисляет лучший размер квадрата за O (sqrt ( n )) для n плиток.

Обновление

При дальнейшем рассмотрении эта проблема имеет более простое решение, основанное на решении выше. Допустим, вам дано 30 плиток. Возможное расположение плиток легко вычислить:

• 30 x 1 (соотношение сторон 30,0000)
• 15 x 2 (соотношение сторон 7,5000)
• 10 x 3 (соотношение сторон 3,3333)
• 8 x 4 (соотношение сторон соотношение 2.0000)
• 6 x 5 (соотношение сторон 1.2000)
• 6 x 6 (соотношение сторон 1.0000)

Допустим, ваш прямоугольник имеет размер 100 x 60. Соотношение сторон вашего прямоугольника составляет 1,6667. Это от 1,2 до 2. Теперь вам нужно только рассчитать размеры плитки для компоновок 8 x 4 и 6 x 5.

Технически первый шаг по-прежнему занимает O (sqrt ( n ) ), поэтому этот обновленный метод не асимптотически быстрее, чем первая попытка.

Некоторые обновления из ветки комментариев

/*
Changes made:

tiles_used -> tiles_used_columns, tiles_used_rows
    (it was originally a 2-tuple in the form (colums, rows))
*/

/* Determine the maximum sized tile possible. */
private function wesleyGetTileSize() : Number {
    var tile_count : Number = slideCount.value;
    var b : Number = heightOfBox.value;
    var a : Number = widthOfBox.value;
    var ratio : Number;    

    // // If the rectangle is taller than it is wide, reverse its dimensions    

    if (a < b) {
        b = widthOfBox.value;
        a = heightOfBox.value;
    } 

    // Rectangle aspect ratio   
    ratio = a / b;    

    // tiles_max_height is the square root of tile_count, rounded up    
    var tiles_max_height : Number = Math.ceil(Math.sqrt(tile_count))    
    var tiles_used_columns : Number;
    var tiles_used_rows : Number;
    var tiles_ar : Number;
    var tile_size : Number;

    var best_tile_size : Number = 0;    

    // i in the range [1, tile_max_height], inclusive   
    for(var i: Number = 1; i <= tiles_max_height + 1; i++) {       
        // tiles_used is the arrangement of tiles (width, height)        
        tiles_used_columns = Math.ceil(tile_count / i);   
        tiles_used_rows = i;

        // tiles_ar is the aspect ratio of this arrangement        
        tiles_ar = tiles_used_columns / tiles_used_rows;        

        // Calculate the size of each tile        
        // Tile pattern is flatter than rectangle       
        if (tiles_ar > ratio){           
            tile_size = a / tiles_used[0]   ;
        }    
        // Tile pattern is skinnier than rectangle        
        else {            
            tile_size = b / tiles_used[1];
        }        
        // Check if this is the best answer so far        
        if (tile_size > best_tile_size){           
            best_tile_size = tile_size;
        }   
    }

    returnedSize.text = String(best_tile_size);
    return best_tile_size;
}

Вот решение O (1) без циклов.

Используя соотношение сторон (высота / ширина) прямоугольника, вы можете сделать первоначальное предположение о количестве плитки в направлениях x и y. Это дает верхнюю и нижнюю границы для общего количества плиток: от xy до (x + 1) (y + 1).

На основании этих границ есть три возможности:

1. Нижняя граница верна. Вычислите наибольший размер tileSize, который приведет к плиткам xy.
2. Верхняя граница верна. Вычислите наибольший размер tileSize, который приведет к (x + 1) (y + 1) плиткам
3. Правильный ответ находится где-то между верхней и нижней границами. Решите уравнение, чтобы определить правильные значения x и y, а затем вычислите наибольший размер tileSize, который приведет к правильному количеству плиток

int GetTileSize(int width, int height, int tileCount)
{
    // quick bailout for invalid input
    if (width*height < tileCount) { return 0; }

    // come up with an initial guess
    double aspect = (double)height/width;
    double xf = sqrtf(tileCount/aspect);
    double yf = xf*aspect;
    int x = max(1.0, floor(xf));
    int y = max(1.0, floor(yf));
    int x_size = floor((double)width/x);
    int y_size = floor((double)height/y);
    int tileSize = min(x_size, y_size);

    // test our guess:
    x = floor((double)width/tileSize);
    y = floor((double)height/tileSize);
    if (x*y < tileCount) // we guessed too high
    {
        if (((x+1)*y < tileCount) && (x*(y+1) < tileCount))
        {
            // case 2: the upper bound is correct
            //         compute the tileSize that will
            //         result in (x+1)*(y+1) tiles
            x_size = floor((double)width/(x+1));
            y_size = floor((double)height/(y+1));
            tileSize = min(x_size, y_size);
        }
        else
        {
            // case 3: solve an equation to determine
            //         the final x and y dimensions
            //         and then compute the tileSize
            //         that results in those dimensions
            int test_x = ceil((double)tileCount/y);
            int test_y = ceil((double)tileCount/x);
            x_size = min(floor((double)width/test_x), floor((double)height/y));
            y_size = min(floor((double)width/x), floor((double)height/test_y));
            tileSize = max(x_size, y_size);
        }
    }

    return tileSize;
}

I have tested this function for all integer widths, heights and tileCounts between 1 and 1000 using the following code:

for (width = 1 to 1000)
{
    for (height = 1 to 1000)
    {
        for (tileCount = 1 to 1000)
        {
            tileSize = GetTileSize(width, height, tileCount);

            // verify that increasing the tileSize by one
            // will result in too few tiles
            x = floor((double)width/(tileSize+1));
            y = floor((double)height/(tileSize+1));
            assert(x*y < tileCount);

            // verify that the computed tileSize actually
            // results in the correct tileCount
            if (tileSize > 0)
            {
                x = floor((double)width/tileSize);
                y = floor((double)height/tileSize);
                assert(x*y >= tileCount);
            }
        }
    }
}