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