Algoritmos y Estructuras de Datos I

Facultad de Ciencias Exactas y Naturales

Universidad de Buenos Aires

Primer Cuatrimestre de 2000

Resolución del Parcial 18

Ejercicio 1

1-a) Es un procedimiento porque cambia a uno de los parámetros de Entrada. Si fuera función en la postcondición tendría que figurar ret_value.

1-b) Si, la postcondición no aclara qué valor tiene cada B[j] (con 0≤j<dim(B)) al finalizar el programa

1-c) A se modifica.Vale 0 en las posiciones en las cuales A₀ era distinto a B₀ y el valor opuesto a cada A₀ en las posiciones en las cuales A₀ era igual a B₀

1-d)

Pc � {i=0} � P

Qc � {i=dim(A) � ("j)(0≤j<dim(A₀) => Propiedad (A,A₀,j,B₀)) � B=B₀}

B � {i<dim(A)}

I � {0≤i≤dim(A) � ("j)(0≤j<i => Propiedad (A,A₀,j,B₀)) � B=B₀ �

("j)(i≤j<dim(A) => A[j]=A₀[j])}

FV = dim(A) - i

1-e)

procedure ej1(in-out:A:Arreglo de integer,in:B:arreglo)

var

i:integer:=0;

while (i<dim(A)) do

if (A[i]=B[i]) then A[i]:=-B[i];

else A[i]:=0;

fi;

i:=i+1;

od;

endprocedure

1-f) Estaria mal porque podria pasar lo siguiente:

a)     dim(A)<dim(B)

En la forma en la cual yo elegí implementar el ciclo, haría lo mismo que si B fuera igual a la dimension de A (o sea, no tomando en cuenta los B[i] con dim(B)>i�dim(A)). En este caso no hace falta cambiar nada (pero hay que ver si sigue haciendo lo que se quiere)

b)     dim(A)>dim(B)

Esta mal porque a partir de un cierto momento (cuando i�dim(A)) estoy comparando elementos de A con elementos de B que no existen...

O sea que en este caso habria que cambiar la precondición y postcondicion (y por supuesto el programa) para que tenga en cuenta este problema (por ejemplo

Q � {("j)(0≤j<(f_min dim(A₀) dim(B₀)) => Propiedad(A,A₀,j,B₀))} )

1-g)

P � {A=A₀ � B=B₀ � Dim(A)=Dim(B) � (0≤j<dim(A₀) => A₀[j]�0 � B₀[j]�0)}

Q � {ret_value=f_contarceros (f_ej1 A₀ B₀)}

Pc � {i=0 � ("j)(0≤j<dim(A₀) => Propiedad(A,A₀,j,B₀)) � ret_value=0}

Qc � {i=dim(A) � ret_value=f_contarceros (f_take (f_ej1 A₀ B₀) i) � B=B₀ �

("j)(0≤j<dim(A₀) => Propiedad(A,A₀,j,B₀))}

B � {i<dim(A)}

I � {0≤i≤dim(A) � ret_value=f_contarceros (f_take A i) � B=B₀ �

("j)(0≤j<dim(A₀) => Propiedad(A,A₀,j,B₀))}

FV = dim(A)-i

ej1:: [Int] -> [Int] -> [Int]

ej1 [] [] = []

ej1 (x:xs) (y:ys) | x==y = (-y):(ej1 xs ys)

| otherwise = 0:(ej1 xs ys)

contarceros:: [Int] -> Int

contarceros [] = 0

contarceros (x:xs) | x==0 = 1+contarceros xs

| otherwise = contarceros xs

function No_coinciden(A:Arreglo de Integer,B:Arreglo de Integer):integer

var

i:integer:=0;

ej1(A,B);

while (i<dim(A)) do

if (A[i]=0] then ret_value:=ret_value+1;

else skip;

i:=i+1;

od;

endfunction

Ejercicio 2

I � ⌐B � {f_long L≤0 � 0≤i≤f_long L₀ � 0≤f_long L≤f_long L₀ �

ret_value=f_suma (f_take L₀ i) � L=f_drop L₀ (f_long L₀-f_long L)}

I � ⌐B � {f_long L=0 � L=[] � 0≤i≤f_long L₀ � ret_value=f_suma (f_take L₀ i)

El invariante está mal porque no se deduce de I � ⌐B la postcondición del ciclo (lo único que se deduce es que L=[], o sea f_long L=0, pero no se deduce que i=f_long L₀

Ejercicio 3

P � {L=L₀ � n=N₀ � N₀>0}

Q � {ret_value=f_promn L₀ N₀}

Pc � {i=0 � ret_value=[]}

Qc � {i=f_div_entera (f_long L₀) N₀ � ret_value=f_take (f_promn L₀ N₀) i

� L=L₀ � n=N₀}

B � {i<f_div_entera (f_long L) n}

I � {0≤i≤f_div_entera (f_long L) n � L=L₀ � n=N₀ �

ret_value=f_take (f_promn L₀ N₀) i}

FV = f_div_entera (f_long L) n - i

-- NOTA: Habria que usar Float y el div ser la division con decimales...

promn:: [Int] -> Int -> [Int]

promn [] _ = []

promn xs n | longitud xs < n = []

| otherwise = (prom_aux (take n xs) n):(promn (drop n xs) n)

prom_aux:: [Int] -> Int -> Int

prom_aux xs n = div (suma xs) n

suma:: [Int] -> Int

suma [] = 0

suma (x:xs) = x+suma xs

function PromN(L:lista de integer,n:integer):lista de integer

var

i:integer:=0;

ret_value:=[];

while (i<Division_Entera(Long(L),n) do

AgregarAtras(ret_value,CalcProm(L,n,i));

i:=i+1;

od;

endfunction

//FUNCION AUXILIAR CalcProm

P � {L=L₀ � n=N₀ � ind=ind₀ � f_long L�ind₀*N₀}

Q � {ret_value=f_suma (f_take (f_drop L₀ ind₀*N₀) N₀)/2}

Pc � {i=0 � ret_value=0}

Qc � {i=n � ret_value=f_suma (f_take (f_drop L₀ ind₀*N₀) i)}

I � {0≤i≤n � ret_value=f_suma (f_take (f_drop L₀ ind₀*N₀) i)}

B � {i<n}

Fv = n-i

function CalcProm(L:lista de integer,n:integer,ind:integer):integer

var

i:integer:=0;

ret_value:=0;

while (i<n) do

ret_value:=ret_value+Iesimo(L,ind*n+i);

i:=i+1;

od;

ret_value:=ret_value/n;

endfunction