refina.pas

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

  (a) Escriba un procedimiento
  REFINA (delta: real; var L:lista) tal que dada una lista
  de reales clasificados de menor a mayor $L$, REFINA
  inserta elementos entre los de $L$, de modo tal que la
  diferencia m\'axima entre elementos de la lista final
  sea menor o igual que delta;

  (b) Escriba un procedimiento
  DESREFINA (delta: real; var L:lista) tal que dada una
  lista de reales clasificados de menor a mayor
  L, REFINA suprime elementos entre los de $L$, de modo tal que
  la diferencia minima entre elementos de la lista final
  sea mayor o igual que delta.

  FIN DE DESCRIPCION }

{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
{ 1. Escriba un procedure REFINA (delta: real; var L:lista);
  tal que dada una lista de reales clasificados de menor a
  mayor L, REFINA inserta elementos entre los de L de modo
  tal que la diferencia maxima entre elementos de la lista
  final sea menor o igual que delta.

  Sea la lista L= [ a_1, a_2,..., a_n], entonces si
  a_[j+1] - a_j > delta debe insertar a_j + delta,
  a_j + 2 * delta, etc... hasta que el ultimo elemento
  insertado este a una distancia menor que delta de
  a_[j+1]. Por ejemplo, si
  L = [1.3, 1.4, 2.0, 2.33, 3.4] y delta = 0.25 entonces
  REFINA debe retornar
  L = [1.3, 1.4, 1.65, 1.9, 2. 2.25 2.33, 2.58, 2.83, 3.08,
  3.33, 3.4]

  2. Escriba un procedure DESREFINA (delta: real; var L:lista);
  tal que dada una lista de reales clasificados de menor a
  mayor L, REFINA suprime elementos entre los de L de modo
  tal que la diferencia minima entre elementos de la lista
  final sea mayor o igual que delta.

  Sea la lista L= [a_1, a_2,..., a_n], entonces si
  a_[j+1] - a_j < delta debe suprimir a_[j+1].
  Si a_[j+2] - a_j < delta tambien se suprime hasta
  encontrar algun a_[j+p] tal que a_[j+p] - a_j >= delta
  o se encuentre el fin de la lista. El procedimiento
  continua con el siguiente elemento, si existe.

  Por ejemplo, si L = [ 1.3, 1.4, 1.65, 1.9, 2. 2.33,
  2.58, 2.83, 3.08, 3.35, 3.4] y delta = 1 entonces
  REFINA debe retornar L = [ 1.3, 2.33, 3.35 ]

  Nota: la versiones aqui implementadas de REFINA y
        DESREFINA no son reciprocas, esto es, al refinar y
        desrefinar sucesivamente no se obtiene, en general,
        la misma lista inicial.
}
{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
{ $ Id: refina.pas 2002/04/05 17:35 jdelia  Exp jdelia    $ } 
program refina_p ;
uses u_listpr ;
type
lista = listpr ;

{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
procedure REFINA (delta: real; var L: lista);
var
  p,  q      : posicion;
  rp, rq, dr :  real;
begin 
  p := L.PRIMERO;
  while true do begin
    q := L.SIGUIENTE (p);
    if (q = L.FIN) then break;
    rp := L.RECUPERA (p);
    rq := L.RECUPERA (q);
    dr := rq - rp ;
    if (dr > delta) then L.INSERTA (rp + delta, q);
    p := L.SIGUIENTE (p);
  end; {while}
end;

{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
procedure DESREFINA (delta: real; var L: lista);
var
  p, q	     : posicion;
  rp, rq, dr : real;
begin 
  p := L.PRIMERO;
  while ( p <> L.FIN ) do begin
    rp := L.RECUPERA (p);
    while (true) do begin
      q := L.SIGUIENTE (p);
      if (q = L.FIN ) then break;
      rq := L.RECUPERA (q);
      dr := rq - rp ;
      if (dr) > delta then break;
      L.SUPRIME (q);
    end ; {while}
    p := L.SIGUIENTE (p);
  end; {while}
end;

{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}      
var 
  L        : lista;
  r, delta : real;
  n, k     : integer;
begin
 {Prueba poniendo un numero de reales generados al azar}
  delta := 0.5;
  n := 10 ;
  L.ANULA ;
  for k := 1 to n do begin
    r := (k + 0.9 * random) * delta;
    L.INSERTA (r, L.FIN);
  end;
  L.IMPRIME ('antes de refinar: ');

  REFINA (delta, L);
  L.IMPRIME ('despues de refinar a delta = ');

  REFINA (0.3*delta, L);
  L.IMPRIME ('despues de refinar a 0.3*delta = ');

  DESREFINA (delta,L);
  L.IMPRIME ('despues de desrefinar: ');
end.
{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}