INFOMAN брой 5

{
                             УМНОЖЕНИЕ НА МАТРИЦИ
                             --------------------

     Имаме N матрици, размерите на които са дадени в масива S. Те трябва да
 се умножат една с друга. Редът,по който матриците се умножават не влияе на
 крайния резултат, но влияе съществено на броя необходими операции.За да ум-
 ножим една матрица с размер a*k с друга матрица с размер k*b  са ни необхо-
 дими a*k*b операции. Ако имаме да умножим N матрици, можем да поставим ско-
 би, за да определим реда на умножение.  Задачата е да се намери такова пос-
 тавяне на скобите, при което да са необходими минимален брой операции.
   Прилага се динамично оптимиране за да се намери оптималния ред на умноже-
 ние на матриците по формулите:
   M(x,x) = 0  за  x = 1...N
   M(i,j) = Min(  M(i,k) + M(k+1,j) + S(i-1)*S(k)*S(j)  )  за k = i...j-1
 където:
   M(i,j) е минималният брой операции, необходими за умножаване на матриците
          с номера от i до j  1 <= i < j <= N
   S(x-1) и S(x) са съответно дължината и ширината на x-тата матрица
          като 1 <= x <= N
  Минималният брой операции за умножение на матриците (търсената стойност) е
 M(1,N). За да можем след като намерим стойностите на матрицата M, да възста-
 новим точния ред на умножение на матриците, можем когато намерим стойността
 на k, за която M(i,j) е минимално, да я запазваме някъде. Можем да използва-
 ме полето M(j,i) на матрицата,защото винаги i<=j и това поле не се използва
 за други цели. След това като възстановяваме точния ред на изпълнение на ум-
 ноженията, ще използваме стойността k=M(j,i),за да сложим в скоби израза от
 от поз. i до поз. k и израза от поз. k+1 до позиция j, защото тази стойност
 k означава, че първо се умножават матриците с номера от i до k, после се ум-
 ножават матриците с номера от k+1 до j  и след това се умножават получените
 две матрици.
   За да се постигне квадратна сложност на алгоритъма,ако M(i,j) веднъж е из-
 числено, то се запомня в таблица и при следваща необходимост от него, се из-
 ползва стойността от тази таблица (използва се "memory function"). И понеже
 матрицата M е с размери N*N, то сложността на алгоритъма е O(N*N*N), защото
 трябва да се изчислят най-много N*N елемента и за всеки от тях се изчерпват
 по N варианта, за да се намери оптималният.
  Трябва да отбележим, че всички възможни начини за поставяне на скобите при
 умножение на N матрици е N-тото число на Каталана. Формулата е:
                  (N+1)*(N+2)*...*(2N-2)
         Kat(N) = ----------------------
                      1*2*...*(N-1)
  Ето как с прилагане на динамично оптимиране с полиномиална сложност намира-
 ме най-добрия от експоненциален брой варианти, без да ги изчерпваме.
}


{$M 65520,0,655360} {Нужен е голям стек за намирането на скобите}

CONST MaxMartics  = 100;
      EndLess     = 65535;
      EndLessByte = 255;

VAR MinMat: array[1..MaxMartics,1..MaxMartics] of word;
    { MinMat(i,j) (i<j) показва мин.брой операции за умножаване на матр. от }
    { i до j, а MinMat(j,i) (j>i) показва позицията, в която те се разделят }
    { на две групи - [от i до MinMat(j,i)] и [от MinMat(j,i)+1 до j]        }
    Size: array[0..MaxMartics] of word;

Function MinMatrix(i,j:byte): word; {Връща минималния брой операции}
Var Min,ValueK: word;   {за умножаване матриците с номера от i до j}
    K: byte;
Begin
  if i=j then MinMatrix:=0 {MinMatrics[i,i]=0 винаги}
  else {Ако търсената стойност в вече изчислена, тя се взема от таблицата}
    if MinMat[i,j]<>EndLess then
      MinMatrix:=MinMat[i,j]
  else {Намираме място k за разделяне на две, така че да получим минимален}
    begin {брой операции за умножаване матр. от i до k с матр. от k+1 до j}
      Min:=EndLess;
      for k:= i to j-1 do
        begin
          ValueK:= MinMatrix(i,k) + MinMatrix(k+1,j) +
                  Size[i-1]*Size[k]*Size[j];
          if ValueK < Min then
            begin Min:=ValueK; MinMat[j,i]:=k; end;
        end;
      MinMat[i,j]:=Min; MinMatrix:=Min;
    end;
End;

Function GetSkobiOrder(L,R:byte): string;
Begin {Рекурсията е хубаво нещо!}
  if L=R then GetSkobiOrder:= chr( L + ord('A')-1 )
  else GetSkobiOrder:= '('+GetSkobiOrder(L,MinMat[R,L])+'*'
                          +GetSkobiOrder(MinMat[R,L]+1,R)+')';
End;


VAR N: byte;

BEGIN
  N:=4;
  Size[0]:=13; Size[1]:=5; Size[2]:=89; Size[3]:=3; Size[4]:=34;

  FillChar(MinMat,SizeOf(MinMat),EndLessByte);
  WriteLn('Min = ',MinMatrix(1,N),'.  Rez = ',GetSkobiOrder(1,N));
END.