91 lines
2.7 KiB
Ada
91 lines
2.7 KiB
Ada
with Ada.Text_IO; use Ada.Text_IO;
|
|
with Ada.Strings.Unbounded; use Ada.Strings.Unbounded;
|
|
|
|
package body mat_chain is
|
|
type Result_Matrix is
|
|
array (Positive range <>, Positive range <>) of Integer;
|
|
|
|
--------------------------
|
|
-- Chain_Multiplication --
|
|
--------------------------
|
|
|
|
procedure Chain_Multiplication (Dims : Vector) is
|
|
n : Natural := Dims'Length - 1;
|
|
S : Result_Matrix (1 .. n, 1 .. n);
|
|
m : Result_Matrix (1 .. n, 1 .. n);
|
|
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 idx in 1 .. n loop
|
|
m (idx, idx) := 0;
|
|
end loop;
|
|
|
|
for Len in 2 .. n loop
|
|
for I in 1 .. n - Len + 1 loop
|
|
J := I + Len - 1;
|
|
m (I, J) := Integer'Last;
|
|
for K in I .. J - 1 loop
|
|
Temp := Item (I - 1) * Item (K) * Item (J);
|
|
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 + 64);
|
|
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, 1, n));
|
|
|
|
end Optimal_Parens;
|
|
|
|
begin
|
|
Chain_Order (Dims);
|
|
Print (Dims);
|
|
Put_Line ("Cost = " & Integer'Image (m (1, n)));
|
|
Put_Line ("Optimal Multiply = " & Optimal_Parens);
|
|
end Chain_Multiplication;
|
|
|
|
end mat_chain;
|