|
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=A0 tam=tam0}
Q Qc
Pc {i=0 ret_value=[]}
Qc {i=dim(A0) ("j)((0≤j<dim(A0)) => sacar_mayor(A0,tam0,j))}
B {i<dim(A)}
I {(0≤i≤dim(A)) ("j)((0≤j<i) => sacar_mayor(A0,tam0,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=pos0 pos0<dim(A) A=A0 tam=tam0}
Q Qc
Pc {i=pos0 ret_value=A0[pos0]}
Qc {i=tam0+pos0-1 ("j)((pos0≤j≤tam0+pos0-1) => A[j mod dim(A)]≤ret_value)
($p)((pos0≤p≤(tam0+pos0-1)) A[p mod dim(A)]=ret_value)}
B {i<(tam+pos-1)}
I {(pos0≤i≤(tam0+pos0-1)) ("j)((pos0≤j≤i) => A[j mod dim(A)]≤ret_value)
($p)((pos0≤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
Aún no hay comentarios para este recurso.
Monografias, Exámenes, Universidades, Terciarios, Carreras, Cursos, Donde Estudiar, Que Estudiar y más: Desde 1999 brindamos a los estudiantes y docentes un lugar para publicar contenido educativo y nutrirse del conocimiento.
Contacto »