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