地板所需的最小瓷砖数量

Question

我开始学习如何在python中编程，我遇到了这个问题，我只能使用这些函数：

• 基本数学和逻辑运算符（.-，*，/，/，/，%，**，

我不是在寻找答案，只是想知道如何解决这个问题。

该问题要求确定覆盖矩形房间地板所需的具有相同方向的相同瓷砖的最小数量。超过地板面积的瓷砖多余部分将被丢弃，不能重复使用。编写一个名为min\u tiles的Python函数，该函数使用4个正整数，即room\u width、room\u length、tile\u width、tile\u length，并生成完全覆盖房间地板所需的最小瓷砖数。

以下是一些例子：

min_tiles（4,4,2,2）=

如果瓷砖是矩形的，则它们只能朝向一个方向，而不能同时朝向两个方向。因此，如果地板是3 x 4，瓷砖是1 x 3，那么在一个方向上需要6块瓷砖才能覆盖地板（丢弃多余的碎片），但在另一个方向上，只需要4块瓷砖才能覆盖地板。在这种情况下，您应该生成最小值，即4。因此，min\u瓷砖（3,4,1,3）=

提前感谢！

Answer 1

def min_tiles_horizontal(room_width,room_length,tile_width,tile_length):
  return math.ceil(room_width / float(tile_width)) * math.ceil(room_length / float(tile_length))

def min_tiles(room_width,room_length,tile_width,tile_length):
  return min(
      min_tiles_horizontal(room_width,room_length,tile_width,tile_length),        
      min_tiles_horizontal(room_width,room_length,tile_length,tile_width))

<代码>min\u tiles\u horizontal仅在平铺水平的情况下计算所需的平铺数量。在min\u tiles中，我们调用min\u tiles\u horizontal两次-一次用于获取水平平铺的数字，一次用于获取垂直平铺的数字（我们通过切换tile\u length和tile\u width作为参数来获取此值），然后返回这两个数字中的最小值。

float用于进行浮点除法，例如，对于3/float（2），我们将得到1.5（不使用float我们将进行整数除法，我们将得到1）<代码>数学。然后使用ceil将数字四舍五入到最接近的较大数字，例如数学。ceil（2.1）将为我们提供3个，因为当您需要2.1个平铺时，您必须使用3个。

Answer 2

您将能够使用动态规划解决方案来解决此问题，但如果您是一般编程新手，这将很困难。您可以假设首先放置一个与地板角对齐的平铺（具有两个可能的方向），放置此平铺后，将创建两个子问题，即较小的矩形。

您还知道，您可以使用带有l x w的一个图块生成n（l）x m（w）和n（w）x m（l）矩形。我认为完全适合边界的最大（按面积）这样的矩形将始终是解决方案的一部分。也许试着看看你是否能证明总是这样？