[理工] [DS]-中央95資結

[NOtWorThy (分子小於64)]

如題 中央資結95考古題 第7題

參考答案是

A <- O

b <- M

for i=1 to n

   for j=1 to n

      for k=1 to n

        A[i, j]= B[i, j]+B[i, k]*B[k, j] //這邊感覺怪怪的 他不段被更新

                                         //若B[i, n]*B[n, j]=0不就錯了


for i = 1 to n

  for j = 1 to n

    if(i!=j and A[i, j]>=2)   //這邊>=2感覺是不是求錯了

                              //根據他這樣的algo不是只算到3-cycle嗎??

          return true

不知是否理解錯誤

或有其他想法

煩請高手賜教

謝謝!!

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 219.70.239.105
推 assassin88:不知道是不是matrix chain..如果是則沒錯
→ assassin88:上面的意思是要找出最小的k值使得矩陣相乘次數最少
→ taitin:應該是TRANSITIVE-CLOSURE的修改，只要做到第四次
→ taitin:剛好在第四次發現A[i,i]連通，表4cycle
→ taitin: A[i, j]= A[i, j]+B[i, k]*B[k, j]  修改成這樣應該就對了
→ NOtWorThy:tHX!!
→ taitin:對了請忽略3，4樓的話，太晚腦袋不清楚XD