Taille maximale du carré pour un nombre inconnu à l'intérieur du rectangle

Sur le plan conceptuel:

• commencer avec 1 carré
• Pour chaque carré, si vous n'avez pas
  de la place dans votre boîte de grille, jusqu'à présent, de réduire les
  la boîte existante juste assez pour faire
  la salle de ligne ou de colonne.

pseudo: compte tenu de M x N rectangle à remplir avec K carrés

//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

Il y a probablement plus rapide des moyens de saut à la réponse à la très grande K, mais je ne peux pas penser à eux. Si vous savez que M et N sont des nombres entiers, il y a peut être encore des méthodes plus rapides.

Ici est un O(1) solution sans boucles.

En utilisant le rapport d'aspect (hauteur/largeur) du rectangle, vous pouvez venir avec un premier deviner le nombre de tuiles dans les directions x et y. Cela donne une limite supérieure et limite inférieure pour le nombre total de carreaux: entre xy et x+1)(y+1).

Sur la base de ces limites, il y a trois possibilités:

1. La limite inférieure est correct. Calculer le plus grand taillecarreau qui entraînera xy tuiles.
2. La limite supérieure est correct. Calculer le plus grand taillecarreau qui en résultera (x+1)(y+1) carreaux
3. La bonne réponse se situe quelque part entre les limites supérieure et inférieure. Résoudre une équation pour déterminer les valeurs de x et y, puis calculer le plus grand taillecarreau qui entraînera le nombre correct de tuiles

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;
}

J'ai testé cette fonction, pour tout entier largeurs, hauteurs et tileCounts entre 1 et 1000 en utilisant le code suivant:

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);
            }
        }
    }
}

La fonction suivante calcule le maximum de la taille de la tuile de l'information donnée.

Si le fait qu'il est écrit en Python, il est difficile pour vous de comprendre, laissez-moi savoir dans un commentaire et je vais essayer de le faire dans une autre langue.

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))

L'algorithme peut vaguement être décrite comme suit

• Si le rectangle est plus haute que large, de le retourner de sorte qu'il est plus large que haute.
• Calculer sla racine carrée du nombre de tuiles, arrondi. (Nommé tiles_max_height dans le code).
• Boucle où je va de 1 à s compris:
  • Construire une grille de carrés qui est le nombre de carreaux de / je carrés de large et je carrés de haut. (Aller tout en haut. Cette "pads" les tuiles manquantes, telles que l'utilisation de 2 carreaux par 2 tuiles lors de votre nombre total de carreaux de est 3.)
  • Faire cette grille aussi grand que possible. (La calculer à l'aide de rapports d'aspect.) Déterminer la taille d'une tuile.
  • À l'aide de cette taille, de déterminer la superficie totale couverte par les tuiles.
  • Vérifier si c'est le meilleur total de la zone jusqu'à présent; si elle est, de stocker la taille du carré
• Retour que la taille du carré

C'est probablement l'un des algorithmes plus rapides énumérés ici, car il calcule le meilleur carré de la taille en O(sqrt(n)) pour n tuiles.

---

Mise à jour

Nouvel examen de la question, ce problème a une solution plus simple basé sur la solution ci-dessus. Dites que vous êtes compte tenu de 30 tuiles. Votre possible tuile arrangements sont faciles à calculer:

• 30 x 1 (rapport d'aspect 30.0000)
• 15 x 2 (rapport d'aspect 7.5000)
• 10 x 3 (rapport d'aspect 3.3333)
• 8 x 4 (rapport d'aspect 2.0000)
• 6 x 5 (ratio d'aspect de 1,2000)
• 6 x 6 (rapport d'aspect 1.0000)

Dire que votre rectangle est de 100 x 60. Votre rectangle de rapport d'aspect est 1.6667. C'est entre 1,2 et 2. Maintenant, vous avez seulement besoin de calculer la tuile dimensions de 8 x 4 et 6 x 5 arrangements.

Le premier pas toujours techniquement prend O(sqrt(n)), donc cette mise à jour de la méthode n'est pas asymptotiquement plus rapide que la première tentative.

---

Quelques mises à jour à partir des commentaires fil

/*
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;
}

Donné des valeurs:

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

côté d'un carreau peut être calculée à l'aide de cette fonction:

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
}

j'ai supposé que vous n'allez pas faire des carreaux plus petits que 1x1, quelle que soit la mesure de 1 est

d'abord, vous commencez à partir de la taille 0:

l = 0

ensuite, vous parcourez de 1 à K colonnes de tuiles où

K = min(a, b)

pour chaque itération calculer la nouvelle valeur maximale côté d'un carreau à l'aide de cette formule

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

cette formule prend la plus petite de ces deux valeurs:

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

si le candidat newL est supérieure à la valeur initiale l et un maximum de tuiles qui peuvent être mis en place sans la superposition est plus grand ou égal que le nombre de carreaux de n puis

l = newL

sur la fin retour l

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

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