Matrix chain multiplication: Difference between revisions
Content added Content deleted
(Added C#) |
(+MATLAB) |
||
Line 330: | Line 330: | ||
Cost : 1773740 |
Cost : 1773740 |
||
</pre> |
</pre> |
||
== {{lang|MATLAB}} == |
|||
<lang matlab>function [r,s] = optim(a) |
|||
n = length(a)-1; |
|||
u = zeros(n,n); |
|||
v = ones(n,n)*inf; |
|||
u(:,1) = -1; |
|||
v(:,1) = 0; |
|||
for j = 2:n |
|||
for i = 1:n-j+1 |
|||
for k = 1:j-1 |
|||
c = v(i,k)+v(i+k,j-k)+a(i)*a(i+k)*a(i+j); |
|||
if c<v(i,j) |
|||
u(i,j) = k; |
|||
v(i,j) = c; |
|||
end |
|||
end |
|||
end |
|||
end |
|||
r = v(1,n); |
|||
s = aux(u,1,n); |
|||
end |
|||
function s = aux(u,i,j) |
|||
k = u(i,j); |
|||
if k<0 |
|||
s = sprintf("%d",i); |
|||
else |
|||
s = sprintf("(%s*%s)",aux(u,i,k),aux(u,i+k,j-k)); |
|||
end |
|||
end</lang> |
|||
'''Output''' |
|||
<lang matlab>[r,s]=optim([1,5,25,30,100,70,2,1,100,250,1,1000,2]) |
|||
r = |
|||
38120 |
|||
s = |
|||
"((((((((1*2)*3)*4)*5)*6)*7)*(8*(9*10)))*(11*12))" |
|||
[r,s]=optim([1000,1,500,12,1,700,2500,3,2,5,14,10]) |
|||
r = |
|||
1773740 |
|||
s = |
|||
"(1*((((((2*3)*4)*(((5*6)*7)*8))*9)*10)*11))"</lang> |
|||
== {{header|Python}} == |
== {{header|Python}} == |