PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

Re: [問題] 長方形與正方形

看板Prob_Solve (計算數學 Problem Solving)作者 (眠月)時間18年前 (2006/11/16 04:12), 編輯推噓1(1推 0噓 0→)
留言1則, 1人參與, 最新討論串8/15 (看更多)
※ 引述《march20 ()》之銘言： : 先來大膽假設一件事: : 在所有最佳解中, 至少有一個是符合這個 pattern : ┌───┬───┐ : │ │ │ : │ A │ B │ : │ │ │ : ├───┴───┤ : │ │ : │ C │ : │ │ : └───────┘ : 其中 A 為正方型, B 和 C 為矩型 (可能為正方型, 也可能為長或寬為 0 的退化矩型) 以 7*7 來說，最佳解是 ┌──┬─┬─┐ │3 │2 │2 │ │ ├┬┼─┤ ├──┴┼┤2 │ │4 ├┴─┤ │ │3 │ │ │ │ └───┴──┘ order=9，沒有更好的解了 @"@ 所以不是所有的 optimal solution 都具有上面的形式.. 不過我從這篇 paper 看到一種形式 Tiling a rectangle with the fewest squares http://arxiv.org/pdf/math.CO/9411215 a ┌──┐ │ b│ c │ └───┐ │ │ │ │d │ │ │ │ └──────┘ 也許可以嘗試以 dynamic programming 建立 (a,b,c,d) 的表格來求解.. 不過這個也一樣要證明每個這種形式的最佳解，都必須含有這種形式的子集 我從這個網頁 http://www.stetson.edu/%7Eefriedma/mathmagic/1298.html 上面看到的最佳解 目前看到的都符合這個規則 (修一下文: 剛剛再去看了一下,發現反例了XD) 至於證明的話 在上面那篇 paper 第六節有提到 根據 abcd 的大小，可以分成六種類型 我粗看了一下，他應該是沒有證明 只是提出這種分解的 bound 所以我也不知道這是不是對的..... (是錯的 囧) -- To iterate is human, to recurse is divine. 遞迴只應天上有, 凡人該當用迴圈. 　 L. Peter Deutsch -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 61.31.171.248 ※ 編輯: yoco315 來自: 61.31.171.248 (11/16 05:01)
推
11/16 06:59, , 1F
遇到這種要做 case 分類, 然後一一擊破的, 最讓人頭大 囧
11/16 06:59, 1F
‣ 更多 yoco315 的文章
文章代碼(AID): #15MtIh-x (Prob_Solve)
討論串 (同標題文章)
本文引述了以下文章的的內容：
以下文章回應了本文：
完整討論串 (本文為第 8 之 15 篇)：
排序： 最舊先 | 最新先 | 留言數
在新視窗開啟完整討論串 (共15篇)
Prob_Solve 近期熱門文章
更多 近期熱門文章 >>
PTT數位生活區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 yoco315 的文章
文章代碼(AID): #15MtIh-x (Prob_Solve)