Matrix chain multiplication: Difference between revisions
no edit summary
(Added Wren) |
No edit summary |
||
Line 27:
__TOC__
=={{header|Ada}}==
{{trans|C}}
This Ada example is implemented using a simple package and a main procedure. The package specification is:
<lang ada>
package Matrix_Chain is
type Vector is array (Natural range <>) of Integer;
procedure Matrix_Chain_Multiplication(Dims : Vector);
end Matrix_Chain;
</lang>
The implementation or body of the package is:
<lang ada>
With Ada.Text_IO; use Ada.Text_IO;
with Ada.Strings.Unbounded; use Ada.Strings.Unbounded;
package body Matrix_Chain is
type Result_Matrix is array(Natural range <>, Natural range <>) of Integer;
---------------------------------
-- Matrix_Chain_Multiplication --
---------------------------------
procedure Matrix_Chain_Multiplication (Dims : Vector) is
n : Natural := Dims'Length - 1;
S : Result_Matrix(0..n, 0..n);
m : Result_Matrix(0..n, 0..n) := (Others =>(Others => 0));
procedure Print(Item : Vector) is
begin
Put("Array Dimension = (");
for I in Item'Range loop
Put(Item(I)'Image);
if I < Item'Last then
Put(",");
else
Put(")");
end if;
end loop;
New_Line;
end Print;
procedure Chain_Order(Item : Vector) is
J : natural;
Cost : Natural;
Temp : Natural;
begin
for Len in 1..n - 1 loop
for I in 0..n - len - 1 loop
J := I + Len;
M(I, J) := Integer'Last;
for K in i..J - 1 loop
temp := item(I) * Item(K + 1) * Item(J + 1);
cost := m(i, K) + M(K + 1, J) + temp;
if cost < m(i,j) then
m(i, J) := cost;
s(i, j) := K;
end if;
end loop;
end loop;
end loop;
end Chain_Order;
function Optimal_Parens return String is
function Construct(S : Result_Matrix; I : Natural; J : Natural)
return Unbounded_String is
Us : Unbounded_String := Null_Unbounded_String;
Char_Order : Character;
begin
if I = J then
Char_Order := Character'Val( I + 65);
Append(Source => Us,
New_Item => Char_Order);
return Us;
else
Append(Source => Us,
New_Item => '(');
Append(Source => Us,
New_Item => Construct(s, I, S(I,J)));
Append(Source => Us,
New_Item => '*');
Append(Source => Us,
New_Item => Construct(s, s(i,j) + 1, j));
Append(Source => Us,
New_Item => ')');
return Us;
end if;
end Construct;
begin
return To_String(Construct(s, 0, N - 1));
end Optimal_Parens;
begin
Chain_Order(Dims);
Print(Dims);
Put_Line("Cost = " & Integer'Image(m(0, n - 1)));
Put_Line("Optimal Multiply = " & Optimal_Parens);
end Matrix_Chain_Multiplication;
end Matrix_Chain;
</lang>
The main procedure is:
<lang ada>
with Matrix_Chain; use Matrix_Chain;
with Ada.Text_IO; use Ada.Text_IO;
procedure Main is
V1 : Vector := (5, 6, 3, 1);
V2 : Vector := (1, 5, 25, 30, 100, 70, 2, 1, 100, 250, 1, 1000, 2);
V3 : Vector := (1000, 1, 500, 12, 1, 700, 2500, 3, 2, 5, 14, 10);
begin
Matrix_Chain_Multiplication(V1);
New_Line;
Matrix_Chain_Multiplication(V2);
New_Line;
Matrix_Chain_Multiplication(V3);
end Main;
</lang>
{{output}}
<pre>
Array Dimension = ( 5, 6, 3, 1)
Cost = 48
Optimal Multiply = (A*(B*C))
Array Dimension = ( 1, 5, 25, 30, 100, 70, 2, 1, 100, 250, 1, 1000, 2)
Cost = 38120
Optimal Multiply = ((((((((A*B)*C)*D)*E)*F)*G)*(H*(I*J)))*(K*L))
Array Dimension = ( 1000, 1, 500, 12, 1, 700, 2500, 3, 2, 5, 14, 10)
Cost = 1773740
Optimal Multiply = (A*((((((B*C)*D)*(((E*F)*G)*H))*I)*J)*K))
</pre>
=={{header|C}}==
| |||