matrices.pas

{ ppc386 -va -vh *.pas }
{ COMIENZO DE DESCRIPCION
  Multiplicar cuatro matrices de n\'umeros reales 
  $M_1 \times M_2 \times M_3 \times M_4$, donde $M_1$ tiene 
  10 filas y 20 columnas, $M_2$ es de 20 por 50, $M_3$ 
  es de 50 por 1 y $M_4$ es de 1 por 100. Asuma que la 
  multiplicaci\'on de una matriz de $p \times q$ por otra de
  $ q \times r $ requiere $ z = p q r $ operaciones escalares
  (que es el n\'umero de operaciones requerido por el
  algoritmo de multiplicaci\'on de matrices). Encuentre
  un orden casi-\'optimo en que se deben multiplicar las 
  matrices para minimizar el n\'umero total de operaciones 
  escalares. Como podria encontrarlo si hay una
  cantidad arbitraria de matrices de dimension arbitraria ?
  keywords: algoritmos
  FIN DE DESCRIPCION }
{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
{ $ Id: matrices.pas  2003/03/12 16:30 mstorti Exp jdelia $ }

program pmatriz ;

uses u_listpi, u_colapi ;

{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
procedure ORDEN_CASI_OPTIMO (L: listpi ; var C: colapi);
var
  p1, p2, p3  : posicion;
  q2, z       : posicion;
  e1, e2, e3  : tipo_elemento ;
  s, om, nro  : real ;
begin
  C.ANULA ;
  p1  := L.PRIMERO ;
  p2  := L.SIGUIENTE (p1);
  p3  := L.SIGUIENTE (p2);
  nro := 0 ;
  while ( p3 <> L.FIN ) do begin {revisa lista remanente}
    om := 1.0e6 ;
    z  := L.FIN ;
    while ( p3 <> z ) do begin {busca la menor opcion}
      e1 := L.RECUPERA (p1);
      e2 := L.RECUPERA (p2);
      e3 := L.RECUPERA (p3);
      s  := e1 * e2 * e3 ;
      writeln ('costo actual      ;  s  = ', s:6:0);
      if  (s < om) then  begin
        om :=  s ;
        q2 := p2 ;
      end ; {if}
      p1 := L.SIGUIENTE (p1);
      p2 := L.SIGUIENTE (p2);
      p3 := L.SIGUIENTE (p3);
    end ; {while}
    nro := nro + om ; {acumula numero de operaciones} 
    e2 := L.RECUPERA (q2);
    writeln ('costo menor       ;  om = ', om:6:0);
    writeln ('indice contraido  ;   q = ', e2:6);
    C.PONE (e2);
    L.SUPRIME (q2);
    p1 := L.PRIMERO ;
    p2 := L.SIGUIENTE (p1);
    p3 := L.SIGUIENTE (p2);
    L.IMPRIME ('lista de indices remanentes');
    readln ;
  end ; {while}
  C.IMPRIME ('');
  writeln ;
  writeln ('nro de operaciones; nro = ', nro:6:0);
  writeln ;
end;

{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
var
  L : listpi ;
  C : colapi ;
  p : posicion ;
begin
  L.ANULA ;
  p := L.PRIMERO ;
  L.INSERTA (100, p);
  L.INSERTA (  1, p);
  L.INSERTA ( 50, p);
  L.INSERTA ( 20, p);
  L.INSERTA ( 10, p);
  writeln ;
  L.IMPRIME ('lista de indices');
  ORDEN_CASI_OPTIMO (L, C);
end.
{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}