在广场的最小数量的剪切矩形 [英] Cut rectangle in minimum number of squares

问题描述

我试图解决以下问题：

的M * N A长方形的纸片将被削减成正方形，以便：

A rectangular paper sheet of M*N is to be cut down into squares such that:

  
1. 纸张沿着一条线平行于纸张的侧边之一切断。
  
2. 纸被切割，从而使得生成的尺寸总是整数。
  

该过程停止时，纸张不能进一步削减。

The process stops when the paper can't be cut any further.

什么是纸片的最低数量削减，使得所有的方块？

What is the minimum number of paper pieces cut such that all are squares?

限制：1＆LT; = N＆LT; = 100和1＆LT; = M＆LT; = 100

Limits: 1 <= N <= 100 and 1 <= M <= 100.

例：设N = 1和M = 2，则回答是2为正方形的最小数目可切断为2（纸被水平切割沿短边在中间）

Example: Let N=1 and M=2, then answer is 2 as the minimum number of squares that can be cut is 2 (the paper is cut horizontally along the smaller side in the middle).

我的code：

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++;

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

But I am not getting what's wrong with this approach as it's giving me a wrong answer.

推荐答案

我会写这是一个动态的（递归）的程序。

I'd write this as a dynamic (recursive) program.

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

Write a function which tries to split the rectangle at some position. Call the function recursively for both parts. Try all possible splits and take the one with the minimum result.

基本情况是，当双方都相等，即输入已经是一个正方形，在此情况下，结果是1

The base case would be when both sides are equal, i.e. the input is already a square, in which case the result is 1.

function min_squares(m, n):

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

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

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

    return min { min_hor, min_ver }

要提高性能，你可以的缓存的递归结果：

To improve performance, you can cache the recursive results:

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 horizontally:
    min_hor := min { min_squares(m, i) + min_squares(m, n-i)  |  i ∈ [1, n/2] }

    // minimum number of squares if you split vertically:
    min_ver := 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缓存[100] [100] 因为自从你输入大小的缓存数据结构是有限的。把它作为一个静态的局部变量，因此它会自动用零初始化。然后除$ P $角0为不缓存（因为它不能成为任何输入的结果）。

In a concrete C++ implementation, you could use int cache[100][100] for the cache data structure since your input size is limited. Put it as a static local variable, so it will automatically be initialized with zeroes. Then interpret 0 as "not cached" (as it can't be the result of any inputs).

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

这篇关于在广场的最小数量的剪切矩形的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！