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)