Re: [問題] 長方形與正方形
看板Prob_Solve (計算數學 Problem Solving)作者idicivik ( 苦海釣叟)時間18年前 (2006/12/10 00:29)推噓0(0推 0噓 0→)留言0則, 0人參與討論串15/15 (看更多)
僅提供一些跟程式比較無關的想法
假設 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
討論串 (同標題文章)
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
