5

假设我有一个 7x7 的正方形。我可以用其他正方形填充正方形（即尺寸为 1x1,2x2 .....6x6 的正方形）。我怎样才能用尽可能小的正方形填充正方形。请帮助我.

4

3 回答 3

1

考虑一个尺寸为 的正方形s x s。切出一个较小的正方形尺寸m x m将产生一个正方形m x m、一个正方形n x n和两个尺寸的矩形m x n，其中m + n = s。

当s是偶数时，正方形可以被划分为m = n，在这种情况下，矩形也将是正方形，结果为 4。

但是，当s为奇数时，必须选择 和 的值，以使生成的矩形可以用尽可能少的正方形填充m。n似乎没有一种立即显而易见的方法来找出最佳配置，所以我建议提出一种算法来找出可用于填充矩形大小的最小正方形数量m x n（这是一个稍微更简单的问题，我相信它可以用递归算法来解决）。所需的正方形总数将等于2 x ([number of squares in m x n rectangle] + 1)。您可以使用循环来检查 m 和 之间的所有1大小s/2。

希望这能让你开始。

于 2013-03-28T19:21:10.580 回答
0

首先检查n是否为偶数。如果 n 是偶数，那么答案是 4，因为没有办法将 3 个正方形或 2 个正方形组合在一起形成另一个正方形，从而解决所有可能情况的一半

在您继续之前：这种方法是不完整的，这可能是错误的方法

我只是打算抛出一个开箱即用的想法，只是因为我觉得这可能会有所帮助，并希望能推进这个问题。我觉得这可能与哥德巴赫的弱猜想有关。该算法可能太长而无法计算更大的值，而且我不确定正在发生多少优化。

现在我的想法是尝试枚举所有 AND都是素数的三元组（它们 >= 2）(n1,n2,n3)AND ANDn1 + n2 + n3 = nn1, n2, n3n >= 7n1 <= n2 <= n3

现在让我从字面上描述我的算法：

我的算法

现在我的想法是找到所有可能的三元组(n1,n2,n3)，使其符合上述定义。下一组n_s = n1 + n2。IFn_s > n3遵循上面的描述，否则翻转n_s和n3

现在问题是剩下的白色矩形（应该彼此一致）。

让我们n4 x n3表示矩形，其中：

n4 = n - 2 * n3 \\if following the depicted example

枚举所有可能的三元组(n41, n42, n43)（将 n 视为 n = n4，因此 n3 >= 7）和(n31, n32, n33)（将 n 视为 n = n3，因此 n3 >= 7）。接下来找到n_s3 == n_s4它们可能是最大的值。
例如：

让我们假设x3 = 17和x4 = 13

  Enumeration of x3 = 17:
  2 + 2 + 13
  3 + 3 + 11
  5 + 5 + 7
  
  Enumeration of x_s3:
  4 = 2 + 2
  6 = 3 + 3
  10 = 5 + 5
  12 = 5 + 7
  14 = 3 + 11
  15 = 2 + 13
  
  Enumeration of x4 = 13:
  2 + 2 + 7
  3 + 5 + 5
  
  Enumeration of x_s4:
  4 = 2 + 2
  8 = 3 + 5
  9 = 2 + 7
  10 = 5 + 5

由于10是 13 和 17 之间共享的最大值，因此您在（两个矩形）中放置了一个 10 x 10 的正方形，现在您有一个非平行四边形，它变得越来越难以填充，但可能（我觉得）朝向正确的方向。

所有反馈表示赞赏。

于 2013-04-02T21:46:41.867 回答
0

考虑一个尺寸为 sx 的正方形。因式分解s为素数。然后解决每个素数的问题sp。答案与 forsp x sp相同s x s。最小的素数可能会给出最低的结果。我没有证据证明这一点，但我已经手动检查了 17 x 17。这是 Otaias 的偶数概念的概括，s导致答案为 4。

放置算法：

您需要从 n = (s+1)/2（向下舍入）循环到 n = s-1。

将 nxn 方块放在角落里。

设 m = s - n。将 mxm 方块放在相邻的角落并继续放置，直到它们（几乎）到达 nxn 方块的末端。

剩余的空间将是 mxm（如果你幸运的话），或者最多 2m-1 x 2m-1，缺少一个角块。

用类似的算法填充剩余空间。首先在缺少的角块对面的角落放置一个 n2 x n2 正方形。

手工工作我得到了以下结果：

s  minimum number of squares:
2   4
3   6
5   8
7   9
11  10
13  11
17  12
于 2013-04-02T16:55:06.237 回答