java矩阵中的最小拆分数

Question

有一个矩形板，其中包含宽度x高度的方形瓷砖。通过从边缘水平或垂直拆分，板材可分为两个矩形件

例如，一张2x2图纸可以分为两张2x1，但不能分为两张，其中一张是1x1。这张纸可以根据我们的需要分很多次

我想创造至少一个完全由T瓷砖组成的作品。如何找到实现此目标所需的最小拆分操作数

例如，如果宽度=5，高度=4，T=8， 然后 最小拆分数=
第一次拆分将有2件：2x4，3x4。 2x4=8，等于T。因此，最小拆分数=1

我有蛮力解决方案，通过它我可以找到在一张纸上得到T瓷砖所需的最小分裂数，但我正在寻找一个优化的。有什么帮助或建议吗

Answer 1

设n和m为板的宽度和高度

1. 如果T>；n*m显然不可能实现理想的分割

2. 如果n或m除以T，那么我们可以很容易地进行一次分割。请注意，只有在一次拆分足够的情况下，T才可以被n或m整除。此外，还有一种特殊情况——当T=n*m时，我们不必进行任何拆分

3. 在其余情况下，如第2条所述。，我们必须至少分两次。看看如果T=a*b对于某些a<；=n和b<；=然后我们可以进行一次分割以获得一个尺寸为a x m的矩形，然后进行另一次分割以获得一个x b。因此，现在我们必须迭代所有可能的对（a，b），使T=a*b。如果其中有一对矩形a x b可以放入一个尺寸为n x m的电路板中，那么我们可以回答为两次分割。如果没有找到这样的对，会发生什么，即T是一个大素数，那么分裂是不可能的，如情况1所示

在某些情况下（即1.和2.）解决方案的复杂性是O（1），但在一般情况下是（3）当我们检查所有a*b=T的对（a，b），然后检查MIN（a，b）<；，这就是O（sqrt T）sqrt（T）-这是搜索某个数字的除数时也使用的常用技巧