Ruby实现的矩阵连乘算法
动态规划解决矩阵连乘问题，随机产生矩阵序列，输出形如((A1(A2A3))(A4A5))的结果。
代码：
#encoding:utf-8
=begin
author:xujin,4100213
date:Oct28,2012
MatrixChain
tofindanoptimumorderbyusingMatrixChainalgorithm
exampleoutput:
Thegivenarrayis:[30,35,15,5,10,20,25]
Theoptimumorderis:((A1(A2A3))((A4A5)A6))
Thetotalnumberofmultiplicationsis:15125
Therandomarrayis：[5,8,8,2,5,9]
Theoptimumorderis:((A1(A2A3))(A4A5))
Thetotalnumberofmultiplicationsis:388
=end
INFINTIY=1/0.0
p=[30,35,15,5,10,20,25]
m,s=Array.new(p.size){Array.new(p.size)},Array.new(p.size){Array.new(p.size)}
defmatrix_chain_order(p,m,s)
n=p.size-1
(1..n).each{|i|m[i][i]=0}
forrin(2..n)do
foriin(1..n-r+1)do
j=r+i-1
m[i][j]=INFINTIY
forkin(i...j)do
q=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j]
m[i][j],s[i][j]=q,kif(q<m[i][j])
end
end
end
end
defprint_optimal_parens(s,i,j)
if(i==j)then
print"A"+i.to_s
else
print"("
print_optimal_parens(s,i,s[i][j])
print_optimal_parens(s,s[i][j]+1,j)
print")"
end
end
defprocess(p,m,s)
matrix_chain_order(p,m,s)
print"Theoptimumorderis:"
print_optimal_parens(s,1,p.size-1)
printf("\nThetotalnumberofmultiplicationsis:%d\n\n",m[1][p.size-1])
end
puts"Thegivenarrayis:"+p.to_s
process(p,m,s)
#producearandomarray
p=Array.new
x=rand(10)
(0..x).each{|index|p[index]=rand(10)+1}
puts"Therandomarrayis："+p.to_s
m,s=Array.new(p.size){Array.new(p.size)},Array.new(p.size){Array.new(p.size)}
process(p,m,s)
热门推荐
10 八一幼儿祝福语大全简短
11 公司乔迁食堂祝福语简短
12 婚礼结束聚餐祝福语简短
13 儿媳买车妈妈祝福语简短
14 毕业送礼老师祝福语简短
15 同事辞职正常祝福语简短
16 恭贺新婚文案祝福语简短
17 金店立秋祝福语简短英文
18 婆婆高寿祝福语大全简短