[理工] matrix-multiplication遞迴列式

看板Grad-ProbAsk作者 (干我屁事喔北七)時間6年前 (2020/01/21 22:07), 6年前編輯推噓5(5推 0噓 14→)
留言19則, 6人參與, 6年前最新討論串1/1
https://imgur.com/ecy1Mt3
這題該怎麼列遞迴式子？ -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 101.9.172.153 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1579615655.A.D43.html
→
01/21 22:16, 6年前 , 1F
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, 1F
→
01/21 22:16, 6年前 , 2F
pi個別為第i個矩陣的row數, column數
01/21 22:16, 2F
→
01/21 22:18, 6年前 , 3F
另外m[i,j]=0 if i=j 然後m[i,j]是第i個矩陣乘到第j個矩陣的
01/21 22:18, 3F
→
01/21 22:18, 6年前 , 4F
最小cost
01/21 22:18, 4F
→
01/21 22:27, 6年前 , 5F
照演算法的方式列的話 第二小題有辦法解嗎？
01/21 22:27, 5F
推
01/21 22:29, 6年前 , 6F
想請問這是哪年的考題
01/21 22:29, 6F
推
01/21 22:33, 6年前 , 7F
我覺得第一小題答案應該是An=A1An-1+A2An-2+...+An-
01/21 22:33, 7F
→
01/21 22:33, 6年前 , 8F
1A1
01/21 22:33, 8F
→
01/21 22:33, 6年前 , 9F
第二小題應該是Catalan number調整一項或兩項？
01/21 22:33, 9F
推
01/21 22:33, 6年前 , 10F
台科104數學
01/21 22:33, 10F
→
01/21 22:34, 6年前 , 11F
他是在算矩陣乘法有幾種相乘的方法
01/21 22:34, 11F
→
01/21 22:37, 6年前 , 12F
那應該就是算有幾種括號的括法吧
01/21 22:37, 12F
推
01/21 22:38, 6年前 , 13F
欸g大好像是對的，這題該不會和108台科一樣吧？https://
01/21 22:38, 13F
→
01/21 22:38, 6年前 , 14F
i.imgur.com/CSKoBhu.jpg
01/21 22:38, 14F
→
01/21 22:39, 6年前 , 15F
沒看以為是DP的東西== 那應該是Catalan number
01/21 22:39, 15F
我知道是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
→
01/22 18:31, 6年前 , 16F
(2n取n)/(n+1)
01/22 18:31, 16F
→
01/22 18:32, 6年前 , 17F
或是(2n取n) - (2n取(n+1))
01/22 18:32, 17F
推
01/22 18:54, 6年前 , 18F
k個矩陣的相異相乘數 n要代k-1
01/22 18:54, 18F
→
01/22 18:54, 6年前 , 19F
不過他應該是問遞迴 可能不能寫成簡式？
01/22 18:54, 19F
‣ 更多 ponwar87123 的文章
文章代碼(AID): #1U9mMdr3 (Grad-ProbAsk)