|
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 »