拆分方成小方块 [英] Split square into small squares

问题描述

我有大广场。我想这个广场分割成小方块。我需要的所有可能的组合。我知道，有组合的无穷计数，但我有一个限制。我有固定尺寸最小的广场上。

I have big square. And I would like to split this square into small squares. I need all possible combinations. I know that there are infinity count of combinations but I have one limitation. I have fixed size for smallest square.

我可以用蛮力实现它。但实在是太长了。

I can implement it using brute force. But it is too long.

时的任何preferable算法完成这个任务？

Is any preferable algorithm for this task?

谢谢！

推荐答案

那么这个问题只有解决办法，如果我们做了2假设（否则有英辉组合）

Well this problem only have solution if we made 2 assumptions (otherwise there is infine combinations)

1）的smalest正方形具有固定大小
2）的方式来减少大广场也是固定的，因为如果你把方成线的小正方形的大小分离的网格。

1) the smalest square has a fixed size
2) the way to cut the big square is also fixed, as if you put the square into a grid which lines are separated by the size of the small square.

还有一个第三个假设，将使问题更容易一点

There is also an third assumption that would make the problem a bit easier

3）大广场上有比小广场边的K-倍。其中K是一个整数。

3) The big square has side K-times bigger than the small square. With K being an integer.

如果这两个假设是真的，我们可以继续：

If both assumptions are true we can proceed:

找到N（beign整数）最小的平方数：方格大小为N *小尺寸

Find the number of N (N beign integer) smallest squares: squares with size N*small-size

 if ((big-size % N*small-size)==0)
    Number += (big-size / N*small-size)^2
 else
    Number += ((big-size / N*small-size)^2) * (big-size % N*small-size)

中的*（大尺寸％N *小尺寸），在其他条件是有becouse如果bigsquare不是除以N，当griding与GID宽度N的大广场，我们将有一个小数部分走了。这样我们可以开始重新分割（griding再次），但为1，2或N小步骤的偏移。步骤的数量（大尺寸％N *小尺寸）。

The * (big-size % N*small-size) in the else condition is there becouse if the bigsquare isn't divided by N, when "griding" the big square with gid-width of N, we will have an "fraction part" left. This way we can start dividing again (griding again) but with an offset of 1, 2 or N small steps. The amount of steps is (big-size % N*small-size).

此外，这些步骤只能容纳如此，如果3个假设进行了。

Again, these steps only hold true if the 3 assumptions were took.

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