Algoritmos y Estructuras de Datos I

Facultad de Ciencias Exactas y Naturales

Universidad de Buenos Aires

Primer Cuatrimestre de 2000

Resolución del Parcial 17

Ejercicio 1

P º {M=M₀}

Q º {("i)(1≤i≤Filas(M) => MaxFilaHasta (M₀,M,i,Columnas(M₀)))}

MaxFilaHasta (M₀,M,f,c) º {("j)(1≤j≤c => ValorMax (M₀,M,f,j))}

IgualFila (M₀,M,f) º {("j)(1≤j≤Columnas(M) => M[i][j]=M₀[i][j])}

ValorMax (M₀,M,i,j) º {($k)(1≤k≤j Ù M₀[i][k]=M[i][j]) Ù

("k)(1≤k≤j => M₀[i][k]≤M[i][j])}

Pc º {f=1}

Qc º {f=Filas(M)+1 Ù ("i)(1≤i<f => MaxFilaHasta (M₀,M,i,Columnas(M₀)))}

I º {1≤f≤Filas(M)+1 Ù ("i)(1≤i<f => MaxFilaHasta (M₀,M,i,Columnas(M)) Ù

("i)(f≤i≤Filas(M) => IgualFila (M₀,M,i))}

B º {f≤Filas(M)}

FV = Filas(M)+1-f

Procedure Ej1 (in-out:M:Matriz)

var

f:integer:=1;

while (f≤Filas(M)) do

ModifFila (M,f);

f:=f+1;

od;

endprocedure

// PROCEDIMIENTO AUXILIAR ModifFila

P º {M=M₀ Ù f=F₀ Ù 1≤F₀≤Filas(M₀)}

Q º {MaxFilaHasta (M₀,M,f,Columnas(M)) Ù

("i)(1≤i≤Filas(M) Ù i¹f => IgualFila(M₀,M,i))}

Pc º {c=2}

Qc º {MaxFilaHasta (M₀,M,f,Columnas(M)) Ù

("i)(1≤i≤Filas(M) Ù i¹f => IgualFila(M₀,M,i)) Ù c=Columnas(M)+1}

I º {2≤c≤Columnas(M)+1 Ù MaxFilaHasta(M₀,M,f,c-1) Ù

("j)(c≤j≤Columnas(M) => M[f][j]=M₀[f][j]) Ù

("i)(1≤i≤Filas(M) Ù i¹f => IgualFila (M₀,M,i)) Ù f=F₀}

B º c≤Columnas(M)

FV = Columnas(M)+1-c

Procedure ModifFila (in-out:M:Matriz,in:f:integer)

var

c:integer:=2;

while (c≤Columnas(M)) do

if M[f][c-1]>M[f][c] then M[f][c]:=M[f][c-1];

else skip;

fi;

c:=c+1;

od;

endprocedure

Ejercicio 2

Especificación en Funcional

factTope:: [Llamada] -> Nat -> [Cuenta]

factTope xs t = eliminar_duplicados (factT xs xs t)

factT:: [Llamada] -> [Llamada] -> Nat -> [Cuenta]

factT [] ys t = []

factT (x:xs) ys t

| (sumaMontos (cuentaDe x) ys) > t = (cuentaDe x):(factT xs ys t)

| otherwise = factT xs ys t

cuentaDe:: Llamada -> Cuenta

cuentaDe llam = Cliente (Origen llam)

sumaMontos:: Cuenta -> [Llamada] -> Nat

sumaMontos c [] = 0

sumaMontos c (x:xs)

| cuentaDe x == c = (Duracion x)*(Precio (Lugar (Origen x)) (Lugar (Destino x)) +

sumaMontos c xs

| otherwise = sumaMontos c xs

eliminar_duplicados es la misma que la de la práctica (en lugar de ser [Int] es [Cuenta] y en lugar de Int es Cuenta y asumo que existe la igualdad entre cuentas)

PROGRAMA EN IMPERATIVO

P º {L=L₀ Ù t=T₀}

Q º {ret_value=f_factTope L₀ T₀}

Pc º P

Qc º {ret_value=f_factT L₀ L₀ T₀ Ù L=[]}

I º {ret_value=f_factT (f_take L₀ (f_long L₀ - f_long L)) L₀ T₀ Ù

L=f_drop L₀ (f_long L₀ - f_long L)

B º {f_long(L)>0}

Fv = f_long L

function Ej2 (L:lista de llamada,tope:integer):lista de Cuenta

while (Long(L)>0) do

if (SumaMontos(L,Cliente(Origen(Primero(L)))) > tope then

AgregarAtras(ret_value,Cliente(Origen(Primero(L))));

fi;

Cola(L);

od;

 ret_value:=elimina_duplicados(ret_value);

endfunction

// la funcion elimina_duplicados es la misma que la de la practica pero en lugar de usar [Int] usa [Cuenta]

// FUNCION AUXILIAR SumaMontos

P º {L=L₀ Ù c=C₀}

Q º {ret_value=f_sumaMontos C₀ L₀}

Pc º {ret_value=0}

Qc º Q

I º {ret_value=f_sumaMontos c (f_take L₀ (f_long L₀-f_long L)) Ù

L=f_drop L₀ (f_long L₀-f_long L)}

B º {f_long L>0}

Fv = long L

function SumaMontos (L:lista de integer,c:cuenta):integer

ret_value:=0;

while (Long(L)>0) do

if (Cliente (Primero(L))=c) then

ret_value:=ret_value+Duracion(Primero(L))*

Precio(Lugar(Origen(Primero(L))),Lugar(Destino(Primero(L))));

fi;

Cola(L);

od;

endfunction