Q 06　在长方形中取正方形

IQ　80
目标时间：20 分钟

想必大家都折过千纸鹤吧？1 张长方形的纸是没法折出千纸鹤的，所以要以长方形纸的短边为基准剪出 1 个正方形。接下来，对剪裁后剩下的纸一直重复该操作，直到最后剩下的纸为正方形。

以 1 张的长方形纸为例，剪掉 1 个的正方形后，剩下 1 张的长方形纸。再用剩下的纸剪 1 个的正方形，剩下的是 1 张的长方形纸。继续用剩下的纸剪 1 个的正方形，剩下的是 1 张的长方形纸，于是最后得到 2 张的正方形纸。这样，1 张长方形纸就分成了 5 张正方形纸（图 1.9）。

问题

有 1 个长方形，其长边的长度不超过 1000，且正好可以分成 20 个正方形。这样的长方形的“长和宽的组合”一共有多少种？长方形的长和宽在互换的情况下算是同一种组合。

以长边的长度不超过 8 且正好可以分成 5 个正方形的长方形为例，除图 1.9 所示的的长方形外，还有图 1.10 展示的 7 种长方形，加起来一共有 8 种组合。

思路

知道长方形中短边的长度，就知道了正方形的边长，“长方形中长边的长度”减去“剪下来的正方形的边长”，得到的就是新的长方形中其中一边的长度。这时，剪下的正方形未必只有 1 个。

另外，在思考时要抛弃“长和宽”的思考方式，将关注点放在“长边和短边”上，然后重复执行相同的处理。

重复取正方形，直到最后剩下的正方形。这个递归处理可以用代码清单 06.01 和代码清单 06.02 实现。用长边除以短边，得到的商就是正方形的个数，余数是新长方形的短边的长度。

代码清单 06.01（q06_1.rb）

W, N = 1000, 20

def cut(w, h)
  return 1 if w == h
  w, h = h, w if w > h
  q, r = h.divmod(w)
  result = q
  result += cut(w, r) if r > 0
  result
end

cnt = 0
1.upto(W) do |i| # 短边
  i.upto(W) do |j| # 长边
    cnt += 1 if cut(i, j) == N
  end
end
puts cnt

代码清单 06.02（q06_1.js）

W = 1000;
N = 20;

function cut(w, h){
  if (w == h) return 1;
  if (w > h){
    var temp = w; w = h; h = temp;
  }
  var r = h % w;

  var result = Math.floor(h / w);
  if (r > 0) result += cut(w, r);
  return result;
}

var cnt = 0;
for (var i = 1; i <= W; i++){   // 短边
  for (var j = i; j <=W; j++){  // 长边
    if (cut(i, j) == N) cnt++;
  }
}
console.log(cnt);

代码清单 06.03（q06_2.rb）

W, N = 1000, 20

def cut(w, h, n)
  return (n == 0) if w == h
  w, h = h, w if w > h
  q, r = h.divmod(w)
  if (n - q < 0) || (r == 0)
    return (n - q == 0)
  else
    return cut(w, r, n - q)
  end
end

cnt = 0
1.upto(W) do |i| # 短边
  i.upto(W) do |j| # 长边
    cnt += 1 if cut(i, j, N)
  end
end
puts cnt

代码清单 06.04（q06_2.js）

W = 1000;
N = 20;

function cut(w, h, n){
  if (w == h) return (n == 0);
  if (w > h){
    var temp = w; w = h; h = temp;
  }
  var r = h % w;

  var q = Math.floor(h / w);
  if ((n - q < 0) || (r == 0))
    return (n - q == 0);
  else
    return cut(w, r, n - q);
}

var cnt = 0;
for (var i = 1; i <= W; i++){    // 短边
  for (var j = i; j <= W; j++){  // 长边
    if (cut(i, j, N)) cnt++;
  }
}
console.log(cnt);

关键点

在需要剪取很多正方形时，代码的处理时间不会有明显变化，但是在需要剪取少量正方形时，使用后面介绍的那个方法可以使处理速度变快。

答案　26 882 种