matrices.pas

{ ppc386 -va -vh *.pas }
{ COMIENZO DE DESCRIPCION

Escribir un procedimiento Pascal que, dada una lista de los indices de
una serie de matrices M1, M2, ..., Mn, calcula el orden optimo (o
cuasi-optimo) en el cual se deben realizar las multiplicaciones para
minimizar el numero de operaciones.  Asuma que la multiplicaci\'on de
una matriz de p x q por otra de q x r requiere z = p q r operaciones
escalares (que es el n\'umero de operaciones requerido por el
algoritmo de multiplicaci\'on de matrices). Si M1 es de p1 x q1, M2 es
de p2 x q2 .... y Mn es de pn x qn, entonces la lista L contiene los
indices L=(p1,p2,p3,...,pn,qn). Notar que los q1, q2, ..., q(n-1) no
son necesarios ya que debe ser q1=p2, q2=p3, ..., q(n-1)=pn. 

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.
{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}