作者ponwar87123 (干我屁事喔北七)
看板Grad-ProbAsk
標題[理工] matrix-multiplication遞迴列式
時間Tue Jan 21 22:07:32 2020
https://imgur.com/ecy1Mt3
這題該怎麼列遞迴式子？
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 101.9.172.153 (臺灣)
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1579615655.A.D43.html
1F：→ DLHZ: m[i,j]= min(m[i,k]+m[k+1,j]+p(i-1)pkpj), k=i~j-1, pi-1, 01/21 22:16
2F：→ DLHZ: pi個別為第i個矩陣的row數, column數 01/21 22:16
3F：→ DLHZ: 另外m[i,j]=0 if i=j 然後m[i,j]是第i個矩陣乘到第j個矩陣的 01/21 22:18
4F：→ DLHZ: 最小cost 01/21 22:18
5F：→ gash55025502: 照演算法的方式列的話 第二小題有辦法解嗎？ 01/21 22:27
6F：推 bochengchen: 想請問這是哪年的考題 01/21 22:29
7F：推 gash55025502: 我覺得第一小題答案應該是An=A1An-1+A2An-2+...+An- 01/21 22:33
8F：→ gash55025502: 1A1 01/21 22:33
9F：→ gash55025502: 第二小題應該是Catalan number調整一項或兩項？ 01/21 22:33
10F：推 Aa841018: 台科104數學 01/21 22:33
11F：→ gash55025502: 他是在算矩陣乘法有幾種相乘的方法 01/21 22:34
12F：→ cossetannie: 那應該就是算有幾種括號的括法吧 01/21 22:37
13F：推 Aa841018: 欸g大好像是對的，這題該不會和108台科一樣吧？https:// 01/21 22:38
14F：→ Aa841018: i.imgur.com/CSKoBhu.jpg 01/21 22:38
15F：→ DLHZ: 沒看以為是DP的東西== 那應該是Catalan number 01/21 22:39
我知道是catalan number
但遞迴式子沒想法＠＠
※ 編輯: ponwar87123 (101.9.172.153 臺灣), 01/22/2020 18:25:59
啊 查了一下108的答案 明白了
※ 編輯: ponwar87123 (101.9.172.153 臺灣), 01/22/2020 18:30:22
16F：→ DLHZ: (2n取n)/(n+1) 01/22 18:31
17F：→ DLHZ: 或是(2n取n) - (2n取(n+1)) 01/22 18:32
18F：推 mistel: k個矩陣的相異相乘數 n要代k-1 01/22 18:54
19F：→ mistel: 不過他應該是問遞迴 可能不能寫成簡式？ 01/22 18:54