1

我一直在练习一些编程竞赛问题（为了好玩和为即将到来的比赛练习），我一直坚持这个问题：http ://dwite.ca/questions/power_tiles.html

我不确定我应该从哪里开始=/。我应该如何解决这个问题才能解决它？

4

4 回答 4

1

我会通过递归来处理它。

编写一个接收两个整数值作为输入的函数。一个值是长度，另一个是宽度。您可以放入的最大正方形将基于最短的边。其尺寸计算如下：

2^RoundDown(Log(ShortSide,Base:2))

这将为您提供您的第一个正方形并将矩形划分为 3 个或 1 个其他矩形，或者如果它是边长为 2^n 的正方形，则什么都没有。

通过简单的减法很容易得到剩余矩形的尺寸。计算尺寸后，再次（在其内部）为每个具有其尺寸的新矩形调用该函数。

当计算的两边的差异为零时，该函数应该终止，即它是正方形，边长为 2^n。

有点像这样：

Global int Counter
DivideRectangle(int Width, int Length)
    int BigSquare = 2^RoundDown(Log(Width,Base:2))
    if NOT(Width - BigSqaure = 0 AND Height- BigSqaure = 0)
        DivideRectangle(width - BigSquare, Height - BigSquare)
        DivideRectangle(width - BigSquare, BigSquare)
        DivideRectangle(BigSquare, Height - BigSquare)

    Counter += 1

仅此而已；整个操作后返回的计数器是填充矩形的正方形数。显然代码有缺陷，需要改进，但这只是应该发生的事情的概述。

于 2013-08-16T19:57:41.770 回答
1

对我来说看起来像是一个动态编程问题

  • 令F(w,h)为将w x h矩形平铺的最小正方形数。

  • 求 F 的递归公式：

    • 如果 w = 0 或 h = 0 则 F(w, h) = 0

    • 否则，F(w,h) =

      For each allowable size a=i^2 <= min(w,h), try to place the a by a square (A)
 in the top left corner.
One of the following possibilities will describe the
 optimal solution:
 +---+--+    +---+--+
 | A | C|    | A |  |
 +---+--+    +---+  |
 |  B   |    |B  |C |
 +------+    +---+--+
 So, choose the best of
   (1 + F(h-a, w) + F(h-a, w-a)) or
   (1 + F(h-a, a) + F(w-a, h))

在餐巾纸上进行大 O 分析，这似乎是一种O(side^2 * sqrt(side))-ish 算法。如果这太多了，您可以：

  • 尝试利用问题中的对称性（例如 F(w,h) = F(h, w)）
  • 再次检查分析以确保它太慢并且您需要另一种算法（也许您不需要计算所有 (w,h) 对？）
  • 找出问题的某些属性，以实现更简单、更少详尽的策略。（例如，尽可能选择最大的正方形是一种简单的贪婪策略……但它在所有情况下都有效吗？）
于 2011-04-03T04:40:47.643 回答
0

什么“1、2、4、8等”记得你？

看图，你会选择什么样的填充顺序（以尺寸计）？

于 2011-04-03T04:03:18.927 回答
0

我会首先用手找出答案说半打左右......然后模拟你如何在程序中解决问题......然后在你有一个有效的“蛮力”答案之后尝试更多地解决问题优雅地。

我会先尝试放置尽可能多的最大尺寸的瓷砖，然后用适合的下一个最大尺寸填充您可以填充的位置。然后变小……直到填满。

您可以使用数组或数组在空间上跟踪填充的空间......但是我怀疑有一种更简单的方法可以通过一些简单的计算来做到这一点......比如取尺寸并取两者中较小的一个并利用 log基地2或类似的东西......

我确信有一个很好的简洁递归解决方案..基于两个的幂..然后你可以将它解开为一个非递归解决方案......

于 2011-04-03T04:05:24.667 回答