包平方成长方形 [英] Pack squares into a rectangle

问题描述

我有一个长方形宽x高，而同样大小未知N个正方形。 我必须确定这些广场和行数和列数的最大尺寸完全适合（UPD。我的意思是不是要填满所有空间，但填充尽可能多的空间可能）成长方形。

我想，在数学上它看起来是这样的：

  X *尺寸＆LT; =宽度// x  - 列数
Y *的大小和LT =身高//Ÿ - 行数
X * Y＆LT; = N // N  - 数量的平方
大小 - ＆GT;最大//尺寸 - 平方大小
 

最终结果可能是这样的：

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

其中， 1 = 广场， 0 =空space`。

其实我看到了类似的问题，但其中predefined平方大小。另外，我写了一些笨拙的算法，但它的效果非常不理想。

编辑：我目前的算法：

我尝试了很多的变化，但我不能让它工作得很好适用于所有情况。其实，我可以通过所有可能的大小，但我不喜欢这种方式。

  //使事情变得更简单，我把宽度更大的尺寸
INT biggerSize = this.ClientSize.Width;
INT lowerSize = this.ClientSize.Height;
INT MAXSIZE = int.MinValue;
INT索引= 0;
INT索引2 = 0;

//找到最大合适的尺寸
的for（int i = _rects.Count; I＆GT; 0;我 - ）{
  INT尺寸= biggerSize / I;
  INT J =（int）的Math.Floor（（双）lowerSize /大小）;

  如果（I * J＆GT; = _boards.Count和放大器;＆放大器;大小＆GT; MAXSIZE）{
    MAXSIZE =大小;
    指数=（INT）我;
    索引2 =（INT）D];
  }
}

INT计数器= 0;

//地方所有的矩形
的for（int i = 0; I＆LT;指数;我++）{
  对于（INT J = 0; J＆LT;索引2; J ++）{
    如果（柜＆LT; _rects.Count）{
      _rects [计数器] .Size =新的大小（MAXSIZE，MAXSIZE）;
      _rects [计数器] .Location =新的点（I * MAXSIZE，J * MAXSIZE）;
    }

    反++;
  }
}
 

解决方案

您的问题是不相符的。首先，你的国家的问题，因为确定这些广场和行数和列数的最大尺寸，以符合完全成长方形。 （强调）。

但你得到样品的最终结果，使空。

因此​​，这是什么呢？

如果您需要的平方完全适合在没有空的空间的矩形，并超出了矩形的边界延伸的无广场，则最大平方的大小会等于长度的最大公约数和宽度的矩形的

请参阅 http://en.wikipedia.org/wiki/Greatest_common_divisor#A_geometric_view

I have a rectangle width x height, and N squares of same unknown size. I must determine the maximum size of these squares and number of rows and columns to fit perfectly (UPD. I mean not to fill all space, but fill as much space as possible) into the rectangle.

I guess, mathematically it looks like this:

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

Final result can look like this:

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

Where 1 = squares, 0 = empty space`.

Actually I saw similar problems, but with predefined size of squares. Also, I wrote some clumsy algorithm, but its results are very unsatisfactory..

Edit: My current algorithm:

I tried a lot of variations, but I cant make it work flawlessly for all cases. Actually, I can go through all possible sizes, but I do not like this approach.

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

解决方案

Your question is not consistent. First, you state the problem as "determine the maximum size of these squares and number of rows and columns to fit perfectly into the rectangle." (emphasis added).

But then you give a sample final result that allows empty space.

So which is it?

If you need the squares to fit perfectly in the rectangle with no empty space and no squares extending beyond the bounds of the rectangle, then the size of the maximal square would equal the greatest common divisor of the length and width of the rectangle.

See http://en.wikipedia.org/wiki/Greatest_common_divisor#A_geometric_view

这篇关于包平方成长方形的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！