作者crazykk (JK)
看板Grad-ProbAsk
標題Re: [理工] [資結] 99交大資聯
時間Mon Mar 15 20:57:10 2010
※ 引述《eric19870117 (艾瑞克)》之銘言：
: 99交大資聯第15題
: Given 5 matrices with dimensions,12x5,5x10,10x2,2x5,5x4,what is the minimum
: number of scalar multications to mutiply these 5 matrices?
: 這一題我算了好幾遍都是490次 ˊˋ
: 沒有選項可以選
: 不知道是哪裡算錯了
: 以下是我的計算過程
: 1 2 3 4 5
: ┬─────────
: 1│0 600 220 340 490
: │
: 2│ 0 100 150 250
: │
: 3│ 0 100 120
: │
: 4│ 0 40
: │
: 5│ 0
: 強者我同學說答案是356
: 可是我怎麼算都算不出356
: 哭哭
以下是我的計算過程及表格
1 2 3 4 5
___________________________
0 600 220 340 356 1
0 100 150 180 2
0 100 120 3
0 40 4
0 5
m[1,3]= k=1,m[1,1]+m[2,3]+12*5*2=220 v
k=2,m[1,2]+m[3,3]+12*10*2
m[2,4]= k=2,m[2,2]+m[3,4]+5*10*5
k=3,m[2,3]+m[4,4]+5*2*10=150 v
m[3,5]= k=3,m[3,3]+m[4,5]+10*2*4=120 v
k=4,m[3,4]+m[5,5]+10*5*4
m[1,4]= k=1,m[1,1]+m[2,4]+12*5*5=450
k=2,m[1,2]+m[3,4]+12*10*5=1300
k=3,m[1,3]+m[4,4]+12*2*5=340 v
m[2,5]= k=2,m[2,2]+m[3,5]+5*10*4=320
k=3,m[2,3]+m[4,5]+5*2*4=180 v
k=4,m[2,4]+m[5,5]+5*5*4=350
m[1,5]= k=1,m[1,1]+m[2,5]+12*5*4=420
k=2,m[1,2]+m[3,5]+12*10*4=1200
k=3,m[1,3]+m[4,5]+12*2*4=356 v
k=4,m[1,4]+m[5,5]+12*5*4=580
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 60.244.36.191
推 gsrr:算這個好麻煩! 03/15 21:03
→ stevenwin:DP的題目都是這樣，一粗心就掰了= = 03/15 21:04
推 wassili:感謝...好像OBST阿= =..一堆符號看到眼花 03/15 21:10
推 wassili:可以在請問一下那矩陣括號該怎麼取才是最快的算法嗎XD 03/15 21:14
推 stevenwin:只知道查root的表格 03/15 21:16
推 ashon:括號就是K值 03/15 21:16
→ crazykk:當矩陣數目少，用暴力法比較快 03/15 21:17
→ crazykk:若矩陣數目較多，通常用Dynamic Programming去解 03/15 21:20
→ eric19870117:3Q~~~~~~~~~~~~~~~~~~ 03/15 21:49
→ Lautreamont:這題是苦工題 但是題型固定 03/15 22:04
推 abcde1499:台大看到考這個超開心 因為至少有一會的了.... 03/15 22:35
推 eric19870117:我台大那題算對 考交大的時候竟然忘了 哈哈 03/15 22:56
→ keepoo:我跟樓上相反@@ 奇怪的是我明明沒再複習 03/15 23:00
推 stevenwin:我台大算錯，交大卻算對了 03/15 23:37
推 sa074463:同樓上= =" 03/15 23:56
→ MarcusWill:我也是台大對交大忘 03/16 00:24
推 sodas2002:這題可以用肉眼判斷阿 選擇題~ 03/16 03:44
→ sodas2002:大的先包一包 留小的就好 03/16 03:44
→ killerjoe:台大忘~交大對= = 03/18 22:12