Rosetta Code

Matrix chain multiplication: Difference between revisions

Page Discussion

Matrix chain multiplication (view source)

Revision as of 15:00, 23 December 2020

248 bytes added ,  3 years ago
no edit summary
No edit summary
No edit summary
Line 29:
 
=={{header|Ada}}==
This example implements the pseudocode in the reference Wiki page. The pseudocode states that the index values for the array to multiply begin at 0 while the cost and order matrices employ index values beginning at 1. Ada supports this pseudocode directly because Ada allows the programmer to define the index range for any array type.
{{trans|C}}
This Ada example is implemented using a simple package and a main procedure. The package specification is:
<lang ada>
package Matrix_Chainmat_chain is
type Vector is array (Natural range <>) of Integer;
procedure Matrix_Chain_MultiplicationChain_Multiplication (Dims : Vector);
end Matrix_Chainmat_chain;
</lang>
The implementation or body of the package is:
<lang ada>
Withwith Ada.Text_IO; use Ada.Text_IO;
with Ada.Strings.Unbounded; use Ada.Strings.Unbounded;
 
package body Matrix_Chainmat_chain is
S :type Result_Matrix(0..n, 0..n);is▼
type Result_Matrix is array (NaturalPositive range <>, NaturalPositive range <>) of Integer;▼
 
---------------------------------▼
▲ type Result_Matrix is array(Natural range <>, Natural range <>) of Integer;
-- Chain_Multiplication --
---------------------------------▼
 
procedure Chain_Multiplication (Dims : Vector) is
▲ ---------------------------------
n : Natural := Dims'Length - 1;▼
-- Matrix_Chain_Multiplication --
m S : Result_Matrix (01 .. n, 01 .. n) := (Others =>(Others => 0));▼
▲ ---------------------------------
m : Result_Matrix (1 .. n, 1 .. n);
 
procedure Matrix_Chain_MultiplicationPrint (DimsItem : 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;
Line 68:
end Print;
 
procedure Chain_Order (Item : Vector) is
J : naturalNatural;
Cost : Natural;
Temp : Natural;
 
begin
for Lenidx in 1 .. n - 1 loop
form I(idx, inidx) := 0..n - len - 1 loop;
end J := I + Lenloop;
 
M(I, J) := Integer'Last;▼
for KLen in i2 ..J - 1n loop
for I in 1 .. n temp- := item(I) * Item(KLen + 1) * Item(J + 1);loop
J cost := m(i, K)I + M(KLen +- 1, J) + temp;
m if cost < m(iI,j J) then:= Integer'Last;
for K in I .. J m(i, J)- :=1 cost;loop
Temp := Item s(i,I j- 1) :=* Item (K) * Item (J);
Cost := m (I, New_ItemK) =>+ Construct(s,m s(i,j)K + 1, j)J) + Temp;▼
if Cost < m New_Item(I, =>J) ')');then▼
▲ M m (I, J) := Integer'LastCost;
S New_Item(I, J) :=> Char_Order)K;▼
end if;
end loop;
Line 91 ⟶ 95:
 
function Optimal_Parens return String is
function Construct(S : Result_Matrix; I : Natural; J : Natural)
(S : Result_Matrix; I : Natural; J : return Unbounded_String isNatural)
Us :return Unbounded_String := Null_Unbounded_String;
is
Us : Unbounded_String := Null_Unbounded_String;
Char_Order : Character;
begin
if I = J then
Char_Order := Character'Val( (I + 6564);
Append (Source => Us, New_Item => Char_Order);
▲ 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 => '*');
New_Item => Construct(s, I, S(I,J)));Append
Append (Source => Us, New_Item => UsConstruct (S, S (I, J) + 1, 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 (sS, 01, N - 1n));
 
end Optimal_Parens;
 
begin
Chain_Order (Dims);
Print (Dims);
Put_Line ("Cost = " & Integer'Image (m (01, n - 1)));
Put_Line ("Optimal Multiply = " & Optimal_Parens);
end Chain_Multiplication;
 
end Matrix_Chain_Multiplication;
 
end Matrix_Chainmat_chain;
</lang>
The main procedure is:
<lang ada>
with Matrix_ChainMat_Chain; use Matrix_ChainMat_Chain;
with Ada.Text_IO; use Ada.Text_IO;
 
procedure Mainchain_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_MultiplicationChain_Multiplication(V1);
New_Line;
Matrix_Chain_MultiplicationChain_Multiplication(V2);
New_Line;
Matrix_Chain_MultiplicationChain_Multiplication(V3);
end Mainchain_main;
</lang>
{{output}}
AdaDaddy
82

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/280474"