Algoritmos y Estructuras de Datos I

Facultad de Ciencias Exactas y Naturales

Universidad de Buenos Aires

Primer Cuatrimestre de 2000

Resolución del Parcial 13

Ejercicio 1

NOTA: HAGO QUE DEVUELVA UNA LISTA EN LUGAR DE UN ARREGLO

1i)

P º {A=A₀ Ù tam=tam₀}

Q º Qc

Pc º {i=0 Ù ret_value=[]}

Qc º {i=dim(A₀) Ù ("j)((0≤j<dim(A₀)) => sacar_mayor(A₀,tam₀,j))}

B º {i<dim(A)}

I º {(0≤i≤dim(A)) Ù ("j)((0≤j<i) => sacar_mayor(A₀,tam₀,j))}

Fv = dim(A)-i

//el predicado sacar_mayor toma tam elementos contando desde la posicion pos (en //forma circular), y devuelve el mayor asignandolo a la posicion pos de ret_value

sacar_mayor(A,tam,pos) º

{("k)((pos≤k≤(tam+pos-1)) => A[k mod dim(A)]≤f_iesimo ret_value pos) Ù

 Ù ($p)((pos≤p≤(tam+pos-1) Ù A[p mod dim(A)]=f_iesimo ret_value pos)}

function Ciclar(A:arreglo de integer,tam):lista de integer

  var

    i:integer:=0;

  ret_value:=[];

  while (i<dim(A)) do

    AgregarAtras(ret_value,Sacar_max(A,tam,i));

    i:=i+1;

  od;

endfunction

//Funcion auxiliar Sacar_max

P º {pos=pos₀ Ù pos₀<dim(A) Ù A=A₀ Ù tam=tam₀}

Q º Qc

Pc º {i=pos₀ Ù ret_value=A₀[pos₀]}

Qc º {i=tam₀+pos₀-1 Ù ("j)((pos₀≤j≤tam₀+pos₀-1) => A[j mod dim(A)]≤ret_value) Ù

     Ù ($p)((pos0≤p≤(tam₀+pos₀-1)) Ù A[p mod dim(A)]=ret_value)}

B º {i<(tam+pos-1)}

I º {(pos₀≤i≤(tam₀+pos₀-1)) Ù ("j)((pos₀≤j≤i) => A[j mod dim(A)]≤ret_value) Ù

     Ù ($p)((pos₀≤p≤i) Ù A[p mod dim(A)]=ret_value)}

Fv = tam+pos-1-i

Sacar_max(A:arreglo de integer,tam:integer,pos:integer):integer

  var

    i:integer:=pos;

  ret_value:=A[i];

  while (i<(tam+pos-1)) do

    if A[(i+1) mod dim(A)]³ret_value then

      ret_value:=A[(i+1) mod dim(A)];

    else

      skip;

    fi;

    i:=i+1;

  od;

endfunction