[請益] matrix-chain multiplication和Catalan numbers
看板Prob_Solve (計算數學 Problem Solving)作者mqazz1 (無法顯示)時間14年前 (2010/05/29 23:01)推噓1(1推 0噓 2→)留言3則, 2人參與討論串1/1
我在讀Cormen的演算法(二版)
有一個地方不是很了解(在書上的333頁)
=====================================
解決 n 個矩陣的乘法
所有的括號是 P(n)
P(n) = 1 if n = 1
sum(k=1 to n-1) P(k)P(n-k) if n >= 2
如果是 4 個矩陣相乘
P(4)帶入這個遞迴式的結果是5
=> 四個矩陣有5種方法相乘
(A1(A2(A3A4)))
(A1((A2A3)A4))
((A1A2)(A3A4))
((A1(A2A3))A4)
(((A1A2)A3)A4)
然後Catalan number的公式 (2n)! / (n+1)!n!
這邊用n=4帶入會得到14
n=3會得到5
所以是要求n個矩陣相乘，在Catalan number要代n-1，在P(n)要代n嗎?
謝謝
=====================================
這是Catalan number 維基百科的介紹
http://zh.wikipedia.org/zh-tw/Catalan_number
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.228.30.220
→
05/30 00:02, , 1F
05/30 00:02, 1F
推
05/30 21:23, , 2F
05/30 21:23, 2F
→
05/30 21:23, , 3F
05/30 21:23, 3F
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
-1
12