切出最小正方形的矩形

一尘不染

切出最小正方形的矩形

algorithm

我正在尝试解决以下问题：

M * N的矩形纸应切成正方形，以便：

沿着平行于纸张侧面之一的线切割纸张。

裁切纸张以使最终尺寸始终为整数。

当无法进一步裁切纸张时，该过程停止。

切成正方形的最小切纸数量是多少？

限制：1 <= N <= 100和1 <= M <= 100。

示例：令N = 1且M = 2，则答案是2，因为可以裁切的最小正方形数是2（沿着中间的较小侧水平裁切纸张）。

我的代码：

cin >> n >> m;

int N = min(n,m);
int M = max(n,m);
int ans = 0;

while (N != M) {
    ans++;
    int x = M - N;
    int y = N;
    M = max(x, y);
    N = min(x, y);
}

if (N == M && M != 0)
   ans++;

但是我没有得到这种方法的问题，因为它给了我一个错误的答案。

阅读 230

2020-07-28

共1个答案

一尘不染

我将其编写为动态（递归）程序。

编写一个试图在某个位置分割矩形的函数。递归调用两个部分的函数。尝试所有可能的分割，并以最小的结果进行分割。

基本情况是当两边相等时，即输入已经是一个正方形，在这种情况下，结果为1。

function min_squares(m, n):

    // base case:
    if m == n: return 1

    // minimum number of squares if you split vertically:
    min_ver := min { min_squares(m, i) + min_squares(m, n-i)  |  i ∈ [1, n/2] }

    // minimum number of squares if you split horizontally:
    min_hor := min { min_squares(i, n) + min_squares(m-i, n)  |  i ∈ [1, m/2] }

    return min { min_hor, min_ver }

为了提高性能，您可以缓存递归结果：

function min_squares(m, n):

    // base case:
    if m == n: return 1

    // check if we already cached this
    if cache contains (m, n):
        return cache(m, n)

    // minimum number of squares if you split vertically:
    min_ver := min { min_squares(m, i) + min_squares(m, n-i)  |  i ∈ [1, n/2] }

    // minimum number of squares if you split horizontally:
    min_hor := min { min_squares(i, n) + min_squares(m-i, n)  |  i ∈ [1, m/2] }

    // put in cache and return
    result := min { min_hor, min_ver }
    cache(m, n) := result
    return result

在具体的C ++实现中，int cache[100][100]由于输入大小受到限制，因此可以用于缓存数据结构。将其作为静态局部变量放置，因此它将自动用零初始化。然后将0解释为“未缓存”（因为它不可能是任何输入的结果）。

可能的C ++实现：http :
//ideone.com/HbiFOH

2020-07-28