Matrix chain multiplication: Difference between revisions
+VBA
(+VBA) |
|||
Line 1,032:
This solution is faster than the recursive one. The 1000 loops run now in 0.234 ms and 0.187 ms per loop on average.
=={{header|VBA}}==
{{trans|Fortran}}
<lang vb>Option Explicit
Option Base 1
Dim N As Long, U() As Long, V() As Long
Sub Optimize(A As Variant)
Dim I As Long, J As Long, K As Long, C As Long
N = UBound(A) - 1
ReDim U(N, N), V(N, N)
For I = 1 To N
U(I, 1) = -1
V(I, 1) = 0
Next I
For J = 2 To N
For I = 1 To N - J + 1
V(I, J) = &H7FFFFFFF
For K = 1 To J - 1
C = V(I, K) + V(I + K, J - K) + A(I) * A(I + K) * A(I + J)
If C < V(I, J) Then
U(I, J) = K
V(I, J) = C
End If
Next K
Next I
Next J
Debug.Print V(1, N);
Call Aux(1, N)
Debug.Print
Erase U, V
End Sub
Sub Aux(I As Long, J As Long)
Dim K As Long
K = U(I, J)
If K < 0 Then
Debug.Print CStr(I);
Else
Debug.Print "(";
Call Aux(I, K)
Debug.Print "*";
Call Aux(I + K, J - K)
Debug.Print ")";
End If
End Sub
Sub Test()
Call Optimize(Array(5, 6, 3, 1))
Call Optimize(Array(1, 5, 25, 30, 100, 70, 2, 1, 100, 250, 1, 1000, 2))
Call Optimize(Array(1000, 1, 500, 12, 1, 700, 2500, 3, 2, 5, 14, 10))
End Sub</lang>
'''Output'''
<pre>
48 (1*(2*3))
38120 ((((((((1*2)*3)*4)*5)*6)*7)*(8*(9*10)))*(11*12))
1773740 (1*((((((2*3)*4)*(((5*6)*7)*8))*9)*10)*11))
</pre>
=={{header|zkl}}==
| |||