particiona.pas

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

Ejercicio tomado en el Ex\'amen Final del 05/07/01:

1) Usando las operaciones de Lista, escribir un procedimiento
   PARTICIONA (var L: lista; a: integer) el cual, dada una
   lista de enteros L reemplace aquellos que son mayores que
   `a' por una sucesi\'on de elementos menores o iguales que
   `a' manteniendo la suma total constante. Se propone el
   siguiente algoritmo: recorrer la lista y, cada vez que se
   encuentra un elemento `x>a' suprimirlo y reemplazarlo por
   `a' tantas veces como entren en `x' y finalmente el resto,
   por ejemplo, si `x=7' y `a=2', entonces se debe reemplazar
   ese 7 por la secuencia `2,2,2,1'. En la lista final NO deben
   quedar elementos mayores que `a'.  Por ejemplo, si
   L=[2,5,2,6,4,1,9,6,3,2], entonces PARTICIONA (L,4) debe
   retornar L=[2,4,1,2,4,2,4,1,4,4,1,4,2,3,2];

2) Usando las operaciones de Lista, escribir un procedimiento
   REJUNTA (var L: lista; a: integer) que, dada una lista de
   enteros L, agrupe elementos de tal manera que en L queden
   solo elementos mayores o iguales que `a'. El algoritmo
   recorre la lista y, cuando encuentra un elemento menor,
   empieza a agrupar el elemento con los siguientes hasta
   llegar a `a' o hasta que se acabe la lista.  Por ejemplo,
   si L=[3,4,2,4,1,4,4,3,2,2,4,1,4,1,4,4,1,4,4,2], entonces
   REJUNTA (L,10) da L=[13,12,13,10,10]. En la lista final
   NO deben quedar elementos menores que `a' salvo,
   eventualmente, el \'ultimo.
   keywords: lista

FIN DE DESCRIPCION }
{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
{ $ Id: particiona.pas  2002/04/05 16:10 mstorti Exp jdelia $}
 
program pruinver;

uses u_listpi;

const
  nmax = 10 ;

type
  lista = listpi ;

{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
procedure PARTICIONA(var L : lista; a:integer);
var
  p : posicion;
  x : tipo_elemento;
begin
  p := L.PRIMERO;
  while (p <> L.FIN) do begin
    x := L.RECUPERA (p);
    if (x > a) then begin
       L.SUPRIME (p);
       while (x >= a) do begin
	 L.INSERTA (a,p);
	 x := x - a;
	 p := L.SIGUIENTE (p);
       end ; {while}
       if (x > 0) then L.INSERTA (x,p);
    end; {if}
    p := L.SIGUIENTE (p);
  end; {while}
end;

{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
procedure REJUNTA (var L: lista; a: integer);
var
  p : posicion;
  x : tipo_elemento;
begin
  p := L.PRIMERO;
  while ( p <> L.FIN ) do begin
    x := L.RECUPERA (p);
    if (x < a) then begin
      L.SUPRIME (p);
      while (p <> L.FIN) and (x < a) do begin
	x := x + L.RECUPERA (p);
        L.SUPRIME (p);
      end ; {while}
      L.INSERTA (x ,p);
    end ; {if}
    p := L.SIGUIENTE (p);
  end; {while}
end;

{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
var
  L : lista;
  j : integer;
begin
   randomize ;
   L.ANULA;
   for j := 1 to nmax do 
      L.INSERTA (trunc (random (nmax) ), L.PRIMERO );
   L.IMPRIME ('Lista original:');	

   PARTICIONA (L,4);
   L.IMPRIME ('Lista despues de particionar:');	

   REJUNTA (L,10);
   L.IMPRIME ('Lista despues de rejuntar:');	
   
end.
{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}