作者NOtWorThy (分子小於64)
看板Grad-ProbAsk
标题[理工] [DS]-中央95资结
时间Tue Feb 9 23:22:15 2010
如题 中央资结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
1F：推 assassin88:不知道是不是matrix chain..如果是则没错 02/09 23:34
2F：→ assassin88:上面的意思是要找出最小的k值使得矩阵相乘次数最少 02/09 23:34
3F：→ taitin:应该是TRANSITIVE-CLOSURE的修改，只要做到第四次 02/10 00:56
4F：→ taitin:刚好在第四次发现A[i,i]连通，表4cycle 02/10 00:58
5F：→ taitin: A[i, j]= A[i, j]+B[i, k]*B[k, j] 修改成这样应该就对了 02/10 01:07
6F：→ NOtWorThy:tHX!! 02/10 08:49
7F：→ taitin:对了请忽略3，4楼的话，太晚脑袋不清楚XD 02/10 10:49