Placez les carrés dans un rectangle

J’ai un rectangle de largeur x hauteur et N carrés de même taille inconnue. Je dois déterminer la taille maximale de ces carrés et le nombre de lignes et de colonnes pour s’adapter parfaitement (UPD. Je ne veux pas dire de remplir tout l’espace, mais de remplir autant d’espace que possible) dans le rectangle.

Mathématiquement, ça ressemble à ça:

x * size <= width //x - number of columns y * size <= height //y - number of rows x * y  max //size - size of squares 

Le résultat final peut ressembler à ceci:

 1 1 1 1 1 1 1 1 1 1 0 0 

1 = squares , 0 = espace vide`.

En fait, j’ai vu des problèmes similaires, mais avec une taille prédéfinie de carrés. J’ai aussi écrit un algorithme maladroit, mais ses résultats sont très insatisfaisants.

Edit: Mon algorithme actuel:

J’ai essayé beaucoup de variations, mais je ne peux pas le faire fonctionner parfaitement dans tous les cas. En fait, je peux passer par toutes les tailles possibles, mais je n’aime pas cette approche.

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

Votre question n’est pas cohérente. En premier lieu, vous dites que le problème “détermine la taille maximale de ces carrés et le nombre de lignes et de colonnes pour s’adapter parfaitement au rectangle”. (emphase ajoutée).

Mais ensuite, vous donnez un exemple de résultat final qui laisse de l’espace vide.

Alors c’est quoi?

Si vous avez besoin que les carrés s’intègrent parfaitement dans le rectangle sans espace vide ni prolongement au-delà des limites du rectangle, la taille du carré maximal correspond au plus grand diviseur commun de la longueur et de la largeur du rectangle.

Voir http://en.wikipedia.org/wiki/Greatest_common_divisor#A_geomesortingc_view

Ce problème est apparu récemment dans un projet sur lequel je travaillais. Voici la solution qui a été déterminée:

 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.