作者yoco315 (眠月)
站內Prob_Solve
標題Re: [問題] 長方形與正方形
時間Sat Nov 18 14:17:30 2006
※ 引述《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)
1F：推 ledia:我跟你方法差不多 先找出某 order 可能的配置再去拼 11/18 17:21
2F：→ ledia:不過看起來你做得完整多了 XD 然後我看不出什麼規律 :( 11/18 17:22
3F：推 willieliao:DP? nice XD 11/18 21:27
4F：推 yoco315:沒有DP,我想不出來怎麼DP,所以是暴力+cut 11/19 01:25
5F：推 march20:拜服 m(_ _)m (比我光說不練強太多啦XD) 11/19 05:59
6F：推 march20:會不會是螺紋分佈呢@@? 中間一個方型, 週邊是四塊矩型? 11/19 06:00
7F：推 colawei:拜求此解之 Time Complexity & Space Complexity m(_ _)m 11/20 10:41
8F：推 march20:我想是 exponential 吧 11/21 12:12
9F：推 march20:(time complexity) 11/21 12:12
10F：推 ablboy:推! 但是請教 min-order table 要如何使用? 不甚了解! 11/22 21:02
11F：推 yoco315:那沒有使用阿.. 只是印出來好看而已.. 每個都是暴力跑出來 11/24 17:13