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

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

看板Prob_Solve (計算數學 Problem Solving)作者yoco315 (眠月)時間18年前 (2006/11/18 13:52)推噓10(10推 0噓 1→)

留言11則, 6人參與討論串13/15 (看更多)

※ 引述《march20 ()》之銘言： : 先來大膽假設一件事: : 在所有最佳解中, 至少有一個是符合這個 pattern : ┌───┬───┐ : │ │ │ : │ A │ B │ : │ │ │ : ├───┴───┤ : │ │ : │ C │ : │ │ : └───────┘ 我寫了一個暴力法搜索所有解的程式 18 * 19 的最佳解為 order = 7 ┌──────┬────┐ │11 │8 │ │ │ │ │ │ │ │ │ │ │ ├─┬──┤ │ │3 │5 │ ├────┬─┴─┤ │ │7 │7 │ │ │ │ ├──┤ │ │ │5 │ │ │ │ │ └────┴───┴──┘ (只是結構圖,比例沒有完全正確,比例正確的話圖要畫很大) 上面的結構寫成一個數列的話，是 11 8 3 5 7 7 5 數列解讀方法是先從左到右，然後從上到下，搜索第一個空格然後放入大小為 n 的方塊 (想一下應該就看的懂 @@") order 7 有四種組合 1. 11 8 3 5 7 7 5 2. 8 11 5 3 7 7 5 3. 7 7 5 5 11 3 8 4. 5 7 7 5 3 11 8 不過這四個其實同構全部不符合上面的 pattern 我程式用的暴力演算法式 for if ( 還沒填滿 ) 搜索下一個可以放置方塊的位置(先左到右,而上到下) 訂出這個方塊最大可能的大小(不超出邊界,也不重疊別的方塊) else 印出來然後 back_trace (把前一個方塊的大小-1,如果已經是1，那就拿掉這個方塊) 這樣就可以找出所有最低 order 的解答.. 順便附上 1~20 的 min-order table | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 ---+---------------------------------------------------------------- 1 | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 2 | 2 1 3 2 4 3 5 4 6 5 7 6 8 7 9 8 10 9 11 10 3 | 3 3 1 4 4 2 5 5 3 6 6 4 7 7 5 8 8 6 9 9 4 | 4 2 4 1 5 3 5 2 6 4 6 3 7 5 7 4 8 6 8 5 5 | 5 4 4 5 1 5 5 5 6 2 6 6 6 7 3 7 7 7 8 4 6 | 6 3 2 3 5 1 5 4 3 4 6 2 6 5 4 5 7 3 7 6 7 | 7 5 5 5 5 5 1 7 6 6 6 6 6 2 8 7 7 7 7 7 8 | 8 4 5 2 5 4 7 1 7 5 6 3 6 5 8 2 8 6 7 4 9 | 9 6 3 6 6 3 6 7 1 6 7 4 7 7 4 7 8 2 7 8 10 | 10 5 6 4 2 4 6 5 6 1 6 5 7 5 3 5 7 6 7 2 11 | 11 7 6 6 6 6 6 6 7 6 1 7 6 7 7 7 7 7 7 8 12 | 12 6 4 3 6 2 6 3 4 5 7 1 7 5 5 4 7 3 7 4 13 | 13 8 7 7 6 6 6 6 7 7 6 7 1 7 8 8 8 7 7 7 14 | 14 7 7 5 7 5 2 5 7 5 7 5 7 1 7 7 7 6 7 6 15 | 15 9 5 7 3 4 8 8 4 3 7 5 8 7 1 7 8 5 7 4 16 | 16 8 8 4 7 5 7 2 7 5 7 4 8 7 7 1 8 7 7 5 17 | 17 10 8 8 7 7 7 8 8 7 7 7 8 7 8 8 1 8 9 7 18 | 18 9 6 6 7 3 7 6 2 6 7 3 7 6 5 7 8 1 7 6 19 | 19 11 9 8 8 7 7 7 7 7 7 7 7 7 7 7 9 7 1 9 20 | 20 10 9 5 4 6 7 4 8 2 8 4 7 6 4 5 7 6 9 1 -- To iterate is human, to recurse is divine. 遞迴只應天上有, 凡人該當用迴圈. 　 L. Peter Deutsch -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.114.78.32 ※ 編輯: yoco315 來自: 140.114.78.32 (11/18 15:03)