secuencia.pas

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

  Ejercicio tomado en el Examen Final del 26/7/01:
  escribir un procedure SECUENCIA (L: lista; var L1: lista);
  el cual busca la secuencia ordenada m\'as larga dentro de
  la lista L dada.
  Ejemplo: si L=(5, 5, 4, 5, 4, 3, 5, 5, 6, 6), entonces
  la secuencia ordenada m\'as larga es L1=(3, 5, 5, 6, 6).

FIN DE DESCRIPCION }

{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
{$ Id: secuencia.pas 2002/04/05 18:00 jdelia  Exp jdelia   $}

program p_secuencia ;

uses u_listpi;

type
   lista = listpi ;

{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
procedure SECUENCIA (L: lista; var L1: lista);
var
  L2	       : lista;
  p, q	       : posicion;
  n1, n2, v, w : integer;
begin
{ En todo momento `L1' contiene la secuencia ordenada mas
  larga encontrada hasta ese momento. Su longitud es `n1'.
  Inicialmente la ponemos a 0 }
  L1.ANULA;
  n1 := 0;
  p  := L.PRIMERO;
  while (p <> L.FIN) do begin
{   Guardamos en `L2' la secuencia ordenada mas larga
    empezando en la posicion `p'. Su longitud sera `n2'.
    Inicialmente ponemos el elemento en `p'}
    L2.ANULA;
    n2 := 1;
    v := L.RECUPERA (p);
    L2.INSERTA (v, L2.FIN);
    p:= L.SIGUIENTE (p);
    while (p <> L.FIN) do begin
      { "v", "w" son dos elementos siguientes }
      w := L.RECUPERA (p);
      { Corta cuando encuentra un elemento menor }
      if (w < v) then break;
      v := w;
      L2.INSERTA (w, L2.FIN);
      n2 := n2 + 1;
      p := L.SIGUIENTE (p);
    end; {while}
  { Si la longitud de la secuencia encontrada en "p" es
    mayor que la mayor encontrada hasta el momento,
    reemplaza L1 por el contenido de L2 }
    if (n2 > n1) then begin
      n1 := n2;
      L1.ANULA;
      q := L2.PRIMERO;
      while (q <> L2.FIN) do begin
        L1.INSERTA (L2.RECUPERA (q), L1.FIN);
        q := L2.SIGUIENTE (q);
      end; {while}
    end ; {if}
    L2.ANULA; { Seamos prolijos !! }
  end; {while}
end; 

{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
var
  j, n	        : integer;
  r1, r2, alpha : real;
  L, L1	        : lista;
begin 
  L.ANULA;
  write ('Ingrese n y alpha : ');
  read  (n, alpha);
  writeln ;
{ genera lista con numeros aleatorios. `0 <= alpha < 1 '
  actua como un `filtro pasabajos', cuanto alpha mas
  cerca de uno, mas suave es la lista y por lo tanto mas
  probabilidad de encontrar secuencias largas. Cuanto mas
  cerca de cero mas probabilidad de encontrar secuencias
  cortas }
  r1 := 0.5 ;
  for j := 1 to n do begin
    r2 := (1 - alpha) * random + alpha * r1;
    L.INSERTA (trunc (n*r2), L.FIN);
    r1 := r2;
  end; {j}
  L.IMPRIME ('Lista generada:');
{ Busca secuencia ordenada mas larga. }

  SECUENCIA (L, L1);
  L1.IMPRIME ('Secuencia ordenada mas larga:');   
end.
{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}