Количество умножений чисел, при умножении матриц Опции

[samec]

Даны три матрицы A(m1,n1); B(m2,n2); C(m3,n3). Как мне вычислить количество умножений чисел, которое потребуется для умножения матриц, например, следующим образом (A*B)*C ??

[samec]

Почти такой же пример (только не рекурсивный вариант, в книге сказано, что рекурсивный вариант алгоритма экспоненциально зависит от количества матриц, что не лучше полного перебора...) я нашёл в книге Кормена: Алгоритмы. Построение и анализ.
Вот так я его реализовал на паскале:

program matr;
uses crt;
const KOL_M=50;
type
 matr_typ=array[1..KOL_M,1..KOL_M] of Longint;

var
 p:array[0..KOL_M] of integer;
 kol:integer;
 m,s:matr_typ;

procedure vvod;
var
 i:integer;
begin
 write('Vvedite kol-vo matric: ');
 readln(kol);
 writeln('Vvod razmernostey matric');
 writeln('Vvedite razmernost 1-oy matrici: ');
 write('Vvedite kol-vo strok: ');
 readln(p[0]);
 write('Vvedite kol-vo stolbcov: ');
 readln(p[1]);
 for i:=2 to kol do
  begin
   write('Vvedite kol-vo stolbcov ',i,'-oy matrici: ');
   readln(p[i]);
  end;
end;

procedure Minim;
var
 n,i,j,l,k:integer;
 q:Longint;
begin
 n:=kol;
 for i:=1 to n do
  m[i,i]:=0;
 for l:=2 to n do
  for i:=1 to n-l+1 do
   begin
    j:=i+l-1;
    m[i,j]:=2147483647;
    for k:=i to j-1 do
     begin
      q:=m[i,k]+m[k+1,j]+p[i-1]*p[k]*p[j];
      if (q<m[i,j]) then
       begin
        m[i,j]:=q;
        s[i,j]:=k;
       end;
     end;
   end;
 writeln('M');
 for i:=1 to kol do
  begin
   for j:=1 to kol do
    write(m[i,j]:10,' ');
   writeln;
  end;
 writeln('S');
 for i:=1 to kol do
  begin
   for j:=1 to kol do
    write(s[i,j]:3,' ');
   writeln;
  end;
end;

begin
 clrscr;
 vvod;
 Minim;
 readkey;
end.

В матрице m в элементе [1..n], где n - количество матриц, хранится минимальное количество умножений. В матрице s, в элементе s[i,j] - записано место последнего умножения при оптимальной расстановке скобок.
Также в этой книге есть процедура, реализующая произведение матриц с оптимальной расстановкой скобок, вот её псевдокод:

Код

Matrix-Chain-Multiply(A,s,i,j);

1 if j>i
2  then X<-Matrix-Chain-Multiply(A,s,i,s[i,j])
3       Y<-Matrix-Chain-Multiply(A,s,s[i,j]+1,j)
4       return Matrix-Multiply(X,Y)
5 else return Ai

Думаю, что для расстановки скобок переделать нужно именно эту процедуру...но вот как? что то у меня не получается ... помогите, пожалуйста....

Сообщение отредактировано: samec - 2.07.2007 13:07