仅提供一些跟程式比较无关的想法 假设 f(m, n) 为 边长为 m x n 的矩形 所得到的解(级 最少用f(m, n) 个正方形填满) 则我们有 0. 对於每个可以贴在矩形内部的正方形边长为 x 我们有 1 <= x <= min(m, n) 1. f(m, n) 是自然数, (by 原来的题目) 2. f(m, n) <= m * n (因为最起码可以用1 * 1的小正方形填满) 3. f(m, n) = f(n, m) 4. f(m, n) <= f(m/d, n/d) (Take d = (m, n) 这部份是因为可以以最少的作法放大边长 为原来的d 倍 又因为 f(m, n) 为最少 所以不可能会比其他作法做出来的个数 还大) 下面是比较是推导出来的 5. if m is not equal to n => f(m, n) > 1 (简单一点的说法就是不是边长相等的矩形 一定不会由一个正方形贴满) 这里是用反证法 Assume exists f(m, n) <= 1, and m != n By 1. => f(m, n) >= 1 so f(m, n) = 1 根据原来题目的说法 f(m, n) = 1 亦即 可以用一个正方形恰好贴满整个矩形 也就是说 m = 正方形边长 = n -><- 所以if m != n => f(m, n) > 1 6. f(1, n) = n by 0. 所以 1<= x <= min(1, n) = 1 所以 x = 1 亦即每个可以贴的正方形边长只可能是 1 而此时的个数为 n 所以 f(1, n) = n 目前只想到这样 欢迎继续加进去 (还有 我也很想证 4. 是等号 可是还没想出证明 至於为什麽导这麽一堆 是因为用程式作穷举时太容易漏掉一些case 没做) --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 140.112.50.171