Algoritmos y Estructuras de Datos I

Facultad de Ciencias Exactas y Naturales

Universidad de Buenos Aires

Primer Cuatrimestre de 2000

Resolución de la Práctica 4

Ejercicio 1

1.1.i)

a) P � {n=N₀ � m=M₀}

1.1.ii)

b) Q � {ret_value = M₀*N₀}

1.1.iii)

b)Pc � {ret_value = 0 � i = 0 � n=N₀ � m=M₀}

B � {i < f_abs n }

I � {ret_value = m*i � 0 � i � (f_abs n) � n=N₀ � m=M₀}

Fv = (f_abs n) - i

Qc � {ret_value = (f_abs n) * m � n=N₀ � m=M₀}

1.1.iv)

Precondición y postcondición para la función abs:

P � {n=N₀}

Q � {ret_value = f_abs N₀}

1.2.i) a) P � {n=N₀ }

1.2.ii) c) Q � { (ret_value = f_primo(N₀) ) }

Ejercicio 2

2i)

function Potencia (n:integer,m:integer):integer

var

i:integer:=0;

ret_value:=1; // no hace falta declarar a retvalue porque se declara

// automáticamente con el tipo declarado en la función

while (i<m) do

i:=i+1;

ret_value:=retvalue*n;

od;

endfunction

2ii)

function Factorial (n:integer):integer

var

i:integer:=0;

ret_value:=1;

while (i<n) do

i:=i+1;

ret_value:=ret_value*i;

od;

endfunction

2iii) (2do cuat. 99)

function Fibonacci (n:integer):integer

var

i:integer:=1;

j:integer:=0;

�ret_value:=1;

�if ((n==0) || (n==1)) then

ret_value:=n;

else

while (i<n) do

ret_value:=ret_value+j;

j:=ret_value-j;

i:=i+1;

od;

fi;

enfunction

2iii) Está mal la especificación

Ejercicio 3

a-vii) P�{i=I₀ � n=N₀ � I₀>0 � (f_par(I₀)� N₀�0)}

a-ix) Q�{ret_value=f_raizEnesima I₀ N₀}

b-i) P�{TRUE}

b-iv) Q�{ret_value=101}

Ejercicio 4

4-i) No concuerda.

La guarda no coincide con lo que se encuentra adentro del while.

4-ii)

Código que respeta los estados: (hay un error en el I?)

function Hay_algun_cuadrado2 (n:integer, m:integer):bool

var

i:integer:=n;

ret_value:=false;

while (i<=m) do

ret_value=(cuadrado?(i) ú ret_value);

i:=i+1;

od;

Estados que respetan el código:

P �{ n = N₀ � m = M₀ }

Pc � { i=m � ret_value�false � ((N₀>=M₀) => (n=N₀ � m=M₀ )) �

((N₀<M₀) => (n=M₀ � m=N₀)}

//I � { (ret_value � ($k)((n <= k < i - 1) � es_cuadrado(k))) � (n <= i <= m + 1)

� n = N₀ � m = M₀ � N₀ <= M₀ }

B � ( i>n )

//Fv = m - i

//Qc � Q �{ ret_value � ($k)(( N₀ <= k <= M₀) � es_cuadrado?(k)) }

EL CODIGO NUNCA ENTRA AL CICLO

Ejercicio 5

5-a-i) No, pues el invariante está mal. No puede ser que antes de entrar al ciclo

ret_value ya dé la suma.

5-a-ii) No, por la misma razón que i

5-a-iii) No, porque en el invariante aparece ret_value=ret_value+i lo cual no tiene

sentido

5-a-iv) SI

5-b)

function SumMenMul (n:integer, m:integer)

ret_value:=0;

while (n>0) do

if (es_mult(n,m) then

ret_value:=ret_value+n;

else

skip;

fi;

n:=n-1;

od;

endfunction

5-c)SI

Ejercicio 6

6-i)

P � {n=N₀ � m=M₀ � M₀>0 � N₀�0}

Q � {ret_value=f_resto N₀ M₀}

Pc � {ret_value=N₀}

Qc � Q

B � {ret_value�m}

I � {(f_resto ret_value m = f_resto N₀ M₀) � (0≤ret_value≤n)}

Fv = (f_resto N₀ M₀) - ret_value

//resto:: Nat -> Nat -> Nat

//resto n d | (d==0) = error "No se puede dividir por 0"

// | (n==0) = 0

// | (n<d) = n

// | (n==d) = 0

// | otherwise = resto (n-d) d

function Resto (n:integer,m:integer):integer

ret_value:=n;

while (ret_value�m) do

ret_value:=ret_value-m;

od;

endfunction

6-ii)

P � {n=N₀ � m=M₀ � M₀>0 � N₀�0}

Q � {ret_value = f_division N₀ M₀}

Pc � {ret_value=0}

Qc � Q

B � {n�m}

I � {(f_resto n m = f_resto N₀ M₀) � (ret_value*m + n = N₀) � (0≤n≤N₀)}

Fv = n - (f_resto N₀ M₀)

//division:: Nat -> Nat -> Nat

//division n d = division2 n d 0

//division2:: Nat -> Nat -> Nat -> Nat

//division2 n 0 v = error "No sea bruto, no se puede dividir por cero."

//division2 0 d v = 0

//division2 n d v |(n<d) = v

// |(n==d) = v+1

// | otherwise = division2 (n-d) d (v+1)

function División_entera (n:integer,m:integer):integer

ret_value:=0;

while (n�m) do

n:=n-m;

ret_value:=ret_value+1;

od;

endfunction

6-iii)

P � {n=N₀ � m=M₀ � ⌐(N₀=0 � M₀=0) � (N₀�0) � (M₀�0)}

Q � {ret_value = f_mcd N₀ M₀}

Pc � P

Qc � {n=f_mcd N₀ M₀ � m=n}

B � {n�m}

I � {f_mcd(N₀,M₀)=f_mcd(n,m) � (f_mcd(N₀,M₀)≤n≤N₀) � (f_mcd(N₀,M₀)≤m≤M₀)}

FV = (n+m) - 2*(f_mcd N₀ M₀)

//mcd:: Nat -> Nat -> Nat

//mcd 0 m = m

//mcd n 0 = n

//mcd n m = mcd m (resto n m)

function MCD (n:integer,m:integer):integer

while (n�m) do

if (n>m) then

n:=n-m;

else

m:=m-n;

od;

ret_value:=n;

endfunction

Ejercicio 7

7-i)

P � {n=N₀ � m=M₀ � N₀�M₀ � N₀>0 � M₀�0}

Q � {ret_value=f_comb N₀ M₀}

//comb:: Nat -> Nat -> Nat

//comb n m | (n<m) = error "No sea animal, ese combinatorio no existe."

// | otherwise = division (factorial n) ((factorial (n-m)*(factorial m))

//factorial:: Nat -> Nat

//factorial 0 = 1

//factorial (n+1) = (factorial n)*(n+1)

Num_combinatorio(n:integer,m:integer):integer

ret_value:=División_entera(Factorial(n),Producto(Factorial(n-m),Factorial(m)));

endfunction

7-ii)

P � {n=N₀ � m=M₀}

Q � {ret_value=f_divisor N₀ M₀}

//divisor:: Int -> Int -> Bool

//divisor n m | (m `mod` n == 0) = True

// | otherwise = False

Divisor(n:integer,m:integer):bool

if (Resto(m,n)==0) then

ret_value:=True;

else

ret_value:=False;

fi;

endfunction

7-iii)

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

Q � {ret_value=($j)(0≤j≤N₀ � j*j=N₀)}

Pc � {i=0 � ret_value=False}

Qc � {i=N₀+1 � ret_value=($j)(0≤j≤N₀ � j*j=N₀)}

B � {i≤n}

I � {0≤i≤n+1 � ret_value=($j)(0≤j<i � j*j=N₀)}

Fv = N₀-(i-1)

Cuadrado_perfecto(n:integer):bool

�var

i:integer:=0;

ret_value:=False;

while (i≤n) do

if (i*i)=n) then

ret_value:=True;

else

skip;

fi;

i:=i+1;

od;

endfunction

7-iv)

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

Q � {ret_value=f_sumadiv N₀}

Pc � {ret_value=1 � i=1}

Qc � {(ret_value=f_sumadiv n) � (i=n)}

I � {(ret_value=f_sumadiv i) � (1<=i<=n)}

Fv � n-i

//suma_divisores:: Int -> Int

//suma_divisores n = sumdiv2 n 1 0

//sumdiv2:: Int -> Int -> Int -> Int

//sumdiv2 0 cont sumdiv = error "Cero tiene infinitos divisores."

//sumdiv2 n cont sumdiv | n < cont = sumdiv

// | divisor cont n = sumdiv2 n (cont+1) (cont+sumdiv)

// | otherwise = sumdiv2 n (cont+1) sumdiv

Suma_divisores(n:integer):integer

var

i:integer:=1;

ret_value:=1;

while (i<n) do

i:=i+1;

if (Divisor(i,n)) then

ret_value:=ret_value+i;

else

skip;

fi;

od;

endfunction

7-v)

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

Q � {ret_value=f_primo2 N₀}

//primo2:: Nat -> Bool

//primo2 0 = False

//primo2 n | (suma_divisores n)==(n+1) = True

// | otherwise = False

function Primo(n:integer):bool

if (Suma_divisores(n)=n+1) then

ret_value:=True

else

ret_value:=False;

fi;

endfunction

7-vi)

P � {n=N₀}

Q � {ret_value=f_sig_primo N₀}

Pc � {n=N₀+1}

Qc � {n=f_sig_primo N₀}

B � {⌐(Primo(n)}

I � {(f_sig_primo N₀ = f_sig_primo (n-1)) � (N₀<n<=f_sig_primo N₀)}

Fv = f_sig_primo N₀ - n

//sig_primo:: Int -> Int

//sig_primo n | primo (n+1) = n+1

// | otherwise = sig_primo (n+1)

function Siguiente_primo(n:integer):integer

n:=n+1;

while (not (Primo(n))) do

n:=n+1;

od;

ret_value:=n;

endfunction

7-vii)

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

Q � {ret_value=f_cant_prim N₀}

Pc � {i=1 � ret_value=0}

Qc � {i=N₀+1 � ret_value=f_cant_prim N₀}

I � {(ret_value=f_cant_prim (i-1)) � (1<=i<=N₀+1)}

Fv = N₀+1-i

//cant_prim:: Int -> Int

//cant_prim max = contprim max 1 0

//contprim:: Int -> Int -> Int -> Int

//contprim max con acu | max < con = acu

// | primo con = contprim max (con+1) (acu+1)

// | otherwise = contprim max (con+1) acu

Cantidad_de_primos(n:integer):integer

var

i:integer:=1;

ret_value:=0;

while (i<=n) do

if (Primo(i)) then

ret_value:=ret_value+1;

else

skip;

fi;

i:=i+1;

od;

endfunction

Ejercicio 8

8-a)

P � { a=A₀ }

Q � {ret_value=f_normaDos A₀^Dim(A₀)}

8-b)

P � {l=L₀ � n=N₀ � N₀<Long(L₀)}

Q � {(f_mismosElementos L₀ ret_value) � ("i)(0�i�Long(L₀) �

(i < N₀ � ( f_iesimo ret_value i ) < ( f_iesimo L₀ N₀ )) ú

(i � N₀ � ( f_iesimo ret_value i) � (f_iesimoL₀ N₀))}

Ejercicio 9

9-a-i) Da True cuando el parametro es un número primo.

9-a-ii) Devuelve el siguiente primo al numero pasado como parámetro.

9-a-iii) Devuelve True cuando todos los elementos del arreglo son pares.

9-a-iv)Dado una arreglo y un n, devuelve la posicion en la cual esta ese n en el arreglo, y si el n no está en el arreglo, devuelve -1.

9-b-i-1) Cuando le paso 0,1 o -1 antes me daba False y ahora da True.

9-b-i-2) Es lo mismo

9-b-ii-1) Si N₀ es primo, antes me daba el siguiente primo, ahora me podría dar el mismo N₀ o cualquier otro primo anterior.

9-b-ii-2) Podria devolver cualquier primo.

9-b-iii) Es lo mismo.

9-b-iv) Podria devolver -1 aunque el parametro pertenezca al arreglo.

Ejercicio 10

10-i)

P � {L=L₀ � elem=elem₀}

Q � {ret_value=f_agregar_atrás L elem}

// agregar_atras::[Int] -> Int -> [Int]

// agregar_atras xs elem = reverso (elem:(reverso xs))

function AgregarAtras(L:lista de integer,elem:integer):lista de integer

� ret_value:=Reverse(Agregar(Reverse(L),elem));

endfunction

// Funcion auxiliar Reverse

P � {L=L₀}

Q � {ret_value=f_reverso L₀}

Pc � {ret_value=[]}

Qc � {L=[] � ret_value=f_reverso L₀} � P

B � {long(L)>0}

I � {f_concatenar (f_reverso ret_value) L =s= L₀}

Fv = long(L)

//reverso:: [a] -> [a]

//reverso [] = []

//reverso (x:xs) = concatenar (reverso xs) [x]

//concatenar:: [a] -> [a] -> [a]

//concatenar [] xs = xs

//concatenar (x:xs) ys = x:concatenar xs ys

function Reverse(L:lista de integer):lista de integer

ret_value:=[];

while (long(L)>0) do

Agregar(ret_value,Primero(L)):

Cola(L);

od;

endfunction

10-ii)

P � {L=L₀ � iesimo=iesimo₀}

Q � {ret_value=f_i_esimo L₀ iesimo₀}

Pc � {i=0} � P

Qc � {i=iesimo � L=f_drop L₀ i}

B � {(i�iesimo)}

I � {L=f_drop L₀ i � (0<=i<=iesimo)}

Fv = iesimo - i

//i_esimo:: [Int] -> Int -> Int

//i_esimo (x:xs) 0 = x

//i_esimo (x:xs) n = i_esimo xs (n-1)

// take n toma los n primeros elementos de la lista

// drop n saca los n primeros elementos de la lista

function I-esimo(L:lista de integer,iesimo:integer):integer

var

i:integer:=0;

while (i�iesimo) do

Cola(L);

i:=i+1;

od;

ret_value:=Primero(L);

endfunction

10-iii)

P � {L=L₀ � pos=pos₀ � elem=elem₀}

Q � {ret_value=f_asignar L₀ pos₀ elem₀}

Pc1 � {ret_value=[] � lorig=f_long L₀ � pos₀<f_long L₀} � P

Qc1 � {ret_value=f_take L₀ pos₀ � L=f_drop L₀ pos₀ � pos=pos₀ � elem=elem₀}

Pc2 � {ret_value=(f_take L₀ pos₀ ++ [elem₀]) � L=f_drop L₀ (pos₀+1) � pos=pos₀ � elem=elem₀}

Qc2 � {ret_value=(f_take L₀ pos₀ ++ [elem₀] ++ f_drop L₀ (pos₀+1)) � L=[] � pos=pos₀ � elem=elem₀}

B1 � {(lorig-(f_long L))<pos}

I1 � {ret_value=f_take L₀ ((f_long L₀)-(f_long L)) �

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

Fv1 = pos₀-(lorig-(f_longitud L))

B2 � {(f_long L)>0}

I2 � {ret_value=f_take L₀ pos₀ ++ [elem₀] ++

++ f_drop (f_take ((f_long L₀)-(f_long L))) (pos₀+1) �

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

Fv2 = f_long L

//asignar::[Int] -> Int -> Int -> [Int]

//asignar xs pos elem = asignar_aux xs pos elem 0

//asignar_aux::[Int] -> Int -> Int -> Int -> [Int]

//asignar_aux [] _ _ _ = []

//asignar_aux (x:xs) pos elem i

// | (i==pos) = elem:(asignar_aux xs pos elem (i+1))

// | otherwise = x:(asignar_aux xs pos elem (i+1))

function Asignar (L:lista de integer,pos:integer,elem:integer):lista de integer

const

lorig:integer:=long(L);

ret_value:=[];

if (pos>=long(L)) then

ret_value:=L;

else

while ((lorig-long(L))<pos) do

AgregarAtras (ret_value,Primero(L));

Cola(L);

od;

AgregarAtras(ret_value,elem);

Cola(L);

while (long(L)>0) do

AgregarAtras (ret_value,Primero(L));

Cola(L);

od;

fi;

endfunction

10-iv-a)

// Comienzo=SacarUltimo

P � {L=L₀}

Q � {ret_value=f_comienzo L₀}

//comienzo:: [Int] -> [Int]

//comienzo xs = reverse (cola (reverso xs))

function Comienzo(L:lista de integer):lista de integer

ret_value:=Reverse(Cola(Reverse (L));

endfunction

10-iv-b)

P � {L=L₀ � (f_long L₀)>0}

Q � {ret_value=f_ultimo L₀}

//ultimo:: [Int] -> Int

//ultimo [] = error "La lista no puede ser vacia"

//ultimo [x] = x

//ultimo (x:xs) = ultimo xs

function Ultimo(L:lista de integer):integer

ret_value:=Primero(Reverse(L));

endfunction

10-v)

P � {A=A₀}

Q � {ret_value=f_reverso A₀^dim(A)}

Pc � {i=0}

Qc � {i=dim(A) � ret_value=f_reverso A₀^dim(A)} � P

B � {i<dim(A)}

I � {ret_value^i=f_reverso (f_drop (A₀^dim(A)) (dim(A)-i)) � (0≤i≤dim(A))} � P

Fv = dim(A)-i

function Reverse(A:arreglo de integer):arreglo de integer

var

i:integer:=0;

while (i<dim(A)) do

ret_value[i]:=A[dim(A)-i-1];

i:=i+1;

od;

endfunction

10-vi)

P � {A=A₀}

Q � {ret_value=f_capicua A₀^dim(A)}

function Capicua(A:Arreglo de integer):Bool

if (A==Reverse(A)) then

ret_value:=True;

else

ret_value:=False;

fi;

endfunction

Ejercicio 11

11-i) VERSION 1 (NO HACER)

P � {L=L₀}

Q � {ret_value=f_limpiar_duplicados L₀}

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

Qc � {ret_value=f_limpiar_duplicados L₀ � L=[] �

� i=(f_long L₀)-(f_contar_repetidos L₀)}

B � {(f_long L)>0}

I � {ret_value=f_take (f_limpiar_duplicados L₀) i � L=f_sacar_elmtos_hasta L₀ i �

� (0≤i≤((f_long L₀)-(f_contar_repetidos L₀)) �

((f_long L)=0 => i=(f_long L₀)-(f_contar_repetidos L₀)}

Si la lista es vacía, quiere decir que saqué todos sus elementos (si había 4 diferentes, i=4), por lo tanto si hago "f_take (f_limpiar_duplicados L₀) i" estoy tomando todos los elementos de f_limpiar_duplicados L₀ (o sea que i es la longitud de la lista original menos los repetidos (i=(f_longitud L₀)-(f_contar_repetidos L₀))

Fv = f_long L

//contar_repetidos:: [Int] -> Int

//contar_repetidos [] = 0

//contar_repetidos (x:xs)

// | pertenece x xs = cuent_rep x xs + contar_repetidos (sacar_elemento x xs)

// | otherwise = contar_repetidos xs

//cuent_rep:: Int -> [Int] -> Int

//cuent_rep _ [] = 0

//cuent_rep n (x:xs) | (n==x) = 1+cuent_rep n xs

// | otherwise = cuent_rep n xs

//pertenece:: Int -> [Int] -> Bool

//pertenece _ [] = False

//pertenece a (x:xs) | (a==x) = True

// | otherwise = pertenece a xs

//sacar_prim_elem:: [Int] -> [Int]

//sacar_prim_elem [] = []

//sacar_prim_elem (x:xs) = sacar_elemento x xs

-- saca todas las apariciones del primer elemento en la lista

//sacar_elmtos_hasta:: [Int] -> Int -> [Int]

//sacar_elmtos_hasta xs n

// | (n==0) = xs

// | otherwise = sacar_prim_elem (sacar_elmtos_hasta xs (n-1))

-- va sacando todas las apariciones de los primeros elementos

function Limpiar_duplicados(L:lista de integer):lista de integer

var

i:integer:=0;

ret_value:=[];

while (long(L)>0) do

AsignarAtras(ret_value,Primero(L));

L:=Sacar_elemento(Primero(L),L);

i:=i+1;

od;

endfunction

//Función auxiliar Sacar_elemento

P � {L=L₀ � elem=elem₀}

Q � {ret_value=f_sacar_elemento elem₀ L₀}

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

Qc � {ret_value=f_sacar_elemento elem₀ L₀ � i=f_long L₀ � L=[]}

B � {i<f_long L}

I � {ret_value=f_sacar_elemento elem₀ (f_take L₀ i) � L=f_drop L₀ i �

� (0≤i≤f_long L₀)}

Fv = long(L₀)-i

function Sacar_elemento(elem:integer,L:lista de integer):lista de integer

var

i:integer:=0;

while (i<long(L)) do

if (Primero(L)==elem) then

skip;

else

AsignarAtras(ret_value,Primero(L));

fi;

Cola(L);

od;

endfunction

11-i) VERSION 2

P � {L=L₀}

Q � {ret_value=f_limpiar_duplicados L₀}

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

B � {i<(f_long L)}

I � {0<=i<=(f_long L₀) � ret_value=f_limp_dup_hta L₀ i � L=L₀}

Qc � {i=(f_long L₀) � ret_value=f_limp_dup_hta L₀ (f_long L₀)}

FV = (f_long L)-i

// limp_dup_hta:: [Int] -> Int -> [Int]

// limp_dup_hta [] _ = []

// limp_dup_hta (x:xs) n

// | (n==0) = []

// | otherwise = x:(limp_dup_hta (sacar_elemento x xs) (n-1))

function limpiar_duplicados(L:lista de integer):Lista de integer

var

i:integer:=0;

ret_value:=[];

while (i<Long(L)) do

if (Pertenece (Iesimo(L,i),ret_value)) then skip;

else

Agregar_Atrás(ret_value,Iesimo(L,i));

fi;

i:=i+1;

od;

endfunction

//Función auxiliar Pertenece

P � {L=L₀ � elem=elem₀}

Q � {ret_value=f_pertenece elem₀ L₀}

Pc � {i=0 � ret_value=False} � P

B � {i<(f_long L)}

I � {0<=i<=(f_long L) � ret_value=f_pertenece elem₀ (f_take L₀ i) � L=L₀}

Qc � {i=(f_long L) � ret_value=f_pertenece elem₀ (f_take L₀ (f_long L₀))}

function Pertenece (elem:integer,L:lista de integer):Bool

var

i:integer:=0;

ret_value:=False;

while (i<Long(L)) do

if (Iesimo(L,i)==elem) then ret_value:=True;

else skip;

i:=i+1;

od;

endfunction

11-ii)

P � {L=L₀}

Q � {ret_value=f_apariciones L₀}

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

B � {i<(f_long L)}

I � {0<=i<=(f_long L) � ret_value=f_alternar_hta L₀ i}

Qc � {i=(f_long L) � ret_value=f_alternar_hta L₀ (f_long L)}

FV = (f_long L)-i

// apariciones_hta::[Int] -> Int -> [Int]

// apariciones_hta [] _ = []

// apariciones_hta xs n = alternar (limp_dup_hta xs n) (take n (apa_elem xs))

function apariciones (L:lista de integer):Lista de integer

var

i:integer:=0;

ret_value:=[];

while (i<Long(L)) do

if Pertenece_pospar((Iesimo(L,i)),ret_value) then skip;

else

AgregarAtras(ret_value,(Iesimo(L,i)));

AgregarAtras(ret_value,Cant_apar((Iesimo(L,i)),L);

fi;

i:=i+1;

od;

endfunction

//Funciona auxiliar Pertenece_pospar

P � {L=L₀ � elem=elem₀}

Q � {ret_value=f_pertenece_pospar elem₀ L₀}

Pc � {i=0 � ret_value=False} � P

B � {i<long(L)}

I � {0<=i<=(f_long L) � ret_value=f_pertenece_pospar elem₀ (f_take L₀ i) � L=L₀}

Qc � {i=(f_long L) � ret_value=f_pertenece_pospar elem₀ (f_take L₀ (long(L₀))

// pertenece_pospar:: Int -> [Int] -> Bool

// pertenece_pospar _ [] = False

// pertenece_pospar a [x] = (a==x)

// pertenece_pospar a (x:y:xs) = (a==x) || pertenece_pospar a xs

function Pertenece_pospar (elem:integer,L:lista de integer):Bool

var

i:integer:=0;

ret_value:=False;

while (i<Long(L)) do

if ((Iesimo(L,i)==elem)&&(Par(i))) then ret_value:=True;

else skip;

i:=i+1;

od;

endfunction

// Funcion auxiliar Cant_apar

P � {L=L₀ � elem=elem₀}

Q � {ret_value=f_cantidad_apariciones L₀ elem₀}

Pc � {i=0 � ret_value=0} � P

B � {i<(f_long L₀)}

I � {0<=i<=(f_long L₀) � ret_value=f_cantidad_apariciones (f_take L₀ i) elem₀}

Qc � {i=(f_long L₀) � ret_value=f_cantidad_apariciones (f_take L₀ (f_long L₀)) elem₀}

function Cant_apar (L:lista de integer,elem:integer):integer

var

i:integer:=0;

ret_value:=0;

while (i<Long(L)) do

if ((Iesimo(L,i))==elem) then ret_value:=ret_value+1;

else skip;

i:=i+1;

od;

endfunction

11-iii)

P � {A=A₀}

Q � {ret_value=f_elev_cuad A₀^dim(A)}

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

B � {i<dim(A)}

I � {0<=i<=dim(A) � ret_value=f_elev_cuad A₀^i � A=A₀}

Qc � {i=dim(A) � ret_value=f_elev_cuad A₀^dim(A) � A=A₀}

FV = dim(A)-i

// elev_cuad::[Int] -> [Int]

// elev_cuad [] = []

// elev_cuad (x:xs) = (x*x):(elev_cuad xs)

function Elevar_al_cuadrado (A:arreglo de integer):lista de integer

var

i:integer:=0;

ret_value:=[];

while (i<dim(A)) do

AgregarAtras(ret_value,(A[i]^2));

i:=i+1;

od;

endfunction

11-iv) VERSION 1

P � {A=A₀}

Q � {ret_value=f_ordenar_dec A₀^dim(A₀)}

Pc � {L=A₀^dim(A₀) � i=0 � L=L₀ � ret_value=[]}

Qc � {i=dim(A) � ret_value=f_take (f_ordenar_dec L₀) i � A=A₀ � L=[]}

B � {i<dim(A)}

I � {0≤i≤dim(A) � A=A₀ � L=(f_sacar_mayores_hta L₀ i)

� ret_value=f_take (f_ordenar L) i}

FV = Dim(A) - i

function Ordenar (A:arreglo de integer):Lista de integer

var

i:integer:=0;

L:Lista de integer;

ret_value:=[];

L:=Array2List(A);

while (i<Dim(A)) do

ret_value:=AgregarAtras(ret_value,Mayor(L));

L:=Sacar_uno(L,Mayor(L));

i:=i+1;

od;

endfunction

//FUNCION AUXILIAR Array2List

P � {A=A₀}

Q � {ret_value=A₀^dim(A₀)}

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

Qc � {i=dim(A₀) � ret_value=A₀^dim(A₀)}

B � {i<dim(A)}

I � {0≤i≤dim(A₀) � A=A₀ � ret_value=A₀^i}

FV = dim(A)-i

function Array2List (A:Arreglo de integer):Lista de integer

var

i:integer:=0;

ret_value=[];

while (i<dim(A)) do

AgregarAtras(ret_value,A[i]);

i:=i+1;

od;

endfunction

//FUNCION AUXILIAR Mayor

P � {L=L₀ � f_long L₀>0}

Q � {ret_value=f_mayor L₀}

Pc � {i=1 � ret_value=f_head L₀}

Qc � {i=f_long L₀ � ret_value=f_mayor (f_take L₀ i) � L=L₀}

B � {i<f_long L}

I � {1≤i≤f_long L₀ � ret_value=f_mayor (f_take L₀ i) � L=L₀}

FV = f_long L - i

function Mayor (L:lista de integer):integer

var

i:integer:=1;

ret_value:=primero(L);

while (i<Long L) do

if (Iesimo(L,i)>ret_value)

then ret_value:=Iesimo(L,i);

else skip;

fi;

i:=i+1;

od;

endfunction

//FUNCION AUXILIAR SACAR_UNO

P � {elem=elem₀ � L=L₀ � f_pertenece elem₀ L₀}

Q � {ret_value=f_sacar_uno elem₀ L₀}

Pc � {i=0 � saque?=False � ret_value=[]} � P

Qc � {i=f_long L₀ � saque?=True � ret_value=f_take (f_sacar_uno elem₀ L₀) (i-1)}

B � {i<f_long L}

I � {0≤i≤f_long L � L=L₀ � elem=elem₀ �

((saque?=True � ret_value=f_take (f_sacar_uno elem₀ L₀) (i-1)) ú

(saque?=False � ret_value=f_take (f_sacar_uno elem₀ L₀) i))}

FV = f_long L - i

function Sacar_uno (elem:integer,L:lista de integer):Lista de integer

var

i:integer:=0;

saque?:Bool:=False;

ret_value:=[];

while (i<Long(L)) do

if ( (elem=Iesimo(L,i)) && saque?=False )

then

saque?:=True;

i:=i+1;

else

AgregarAtras(ret_value,Iesimo(L,i));

i:=i+1;

fi;

od;

endfunction

11-iv) VERSION 2 (INCOMPLETA)

P � {A=A₀}

Q � {ret_value=f_ordenar_dec A₀^dim(A₀)}

Pc � {i=0} � P

Qc � {i=dim(A₀) � A^dim(A₀)=f_ordenar_dec A₀^dim(A₀)}

B � {i<dim(A)}

I � {0≤i≤dim(A) �

f_drop A^dim(A) (dim(A)-i)=f_ordenar_dec (f_drop A₀^dim(A₀) (dim(A₀)-i)}

FV = dim(A)-i

function ordenar (A:Arreglo de integer):Lista de integer

var

i:integer:=0;

while (i<dim(A)) do

Poner_mayor_al_final(A,i+1);

i:=i+1;

od;

ret_value:=Array2List(A);

endfunction

//Procedimiento auxiliar Poner_mayor_al_final

P � {A=A₀ � i=i₀}

Q � {f_drop A^dim(A) (dim(A)- i₀)=f_drop (f_ordenar A₀^dim(A)) (dim(A)- i₀)}

Pc � {j=1}

Qc � {j=dim(A)} � Q

B � {j<dim(A)}

I � {1≤j≤dim(A) �

Ejercicio 12

12-i-a) VERSION 1

P � {L=L₀ � M=M₀ � (f_long M₀)>=(f_long L₀)}

Q � {ret_value=f_prefijo L₀ M₀}

Pc � {i=0 � ret_value=False} � P

B � {i<(f_long L) � (f_iesimo L i)=(f_iesimo M i)}

I � {0<=i<=(f_long L) � f_prefijo (f_take L i) (f_take M i) � L=L₀ � M=M₀}

Qc � {(i=(f_long L) �

f_prefijo (f_take L (f_long L)) (f_take M (f_long L))) ú

(i<(f_longitud L) �

⌐(f_prefijo (f_take L (f_long L)) (f_take M (f_long L))))}

FV = (f_long L)-i

function Prefijo (L:lista de char,M:lista de char):Bool

var

i:integer:=0;

ret_value:=False;

while ( (i<long(L)) && (Iesimo(L,i)=Iesimo(M,i)) ) do

i:=i+1;

od;

endfunction

12-1-a) VERSION 2

P � {L=L₀ � M=M₀}

Q � {ret_value=f_prefijo L₀ M₀}

Pc � {i=0 � ret_value=True � f_long L₀≤f_long M₀}

B � {i<f_long L}

I � {ret_value=("j)(0≤j<i => f_iesimo L j = f_iesimo M j)}

Qc � {i=f_long L � ret_value=("j)(0≤j<i => f_iesimo L j = f_iesimo M j)}

FV = f_long L - i

function Prefijo (L:lista de integer,M:lista de integer

var

i:integer:=0;

if (Long(L)>Long(M)) then ret_value:=False;

else

ret_value:=True;

while (i<Long(L)) do

ret_value:=ret_value and Iesimo(L,i)=Iesimo(M,i);

i:=i+1;

od;

fi;

endfunction

12-i-b)

P � {L=L₀ � M=M₀ � (f_long M₀)>=(f_long L₀)}

Q � {ret_value=f_sufijo L₀ M₀}

function Sufijo (L:lista de char,M:lista de char):Bool

ret_value:=Prefijo (Reverse(L),Reverse(M));

endfunction

12-ii-b)

P � {L=L₀ � M=M₀}

Q � {ret_value=f_subcadena L₀ M₀}

Pc � {ret_value=False}

B � {(f_long L)<(f_long M)}

I � {(f_long L)<=(f_long M)<=(f_long M₀) � L=L₀ �

ret_value=f_prefijo L M � M=f_cola M}

Qc � {(f_long L)=(f_long M) � L=L₀ � ret_value f_prefijo L M}

FV = f_long M

function Subcadena (L:lista de char,M:lista de char):Bool

ret_value:=False;

while (Long(L)<Long(M)) do

if (Prefijo(L,M)==True) then ret_value:=True;

else skip;

fi;

Cola(M);

od;

endfunction

12-iii)

P � {L=L₀ � M=M₀}

Q � {ret_value=f_sacar_primero L₀ M₀}

Pc � {ret_value=[]}

Qc � {ret_value=f_sacar_primero L₀ M₀ �

L=f_drop L₀ ((f_long M₀)-(f_long (f_sacar_primero L₀ M₀))) � M=[]}

B � {(f_long M)>0}

I � {M=f_drop M₀ ((f_long M₀)-(f_long M)) �

ret_value=f_take (f_sacar_primero L₀ M₀) ((f_long M₀)-(f_long M)) �

� L=f_drop L₀ (f_long M₀ -(f_long M + f_long ret_value))

� (0≤(f_long M)≤f_long M₀)}

FV = (f_long M)

function Sacar_Primero(L:lista de char,M:lista de char):lista de char

var

i:integer:=0;

ret_value:=[];

while (Long(M)>0) do

if ((Prefijo L M) && (not(Long(L)==0)) then

Cola(L);

Cola(M);

else

AgregarAtras(ret_value,Primero(M));

Cola(M);

fi;

od;

endfunction

EJERCICIOS 2-99

5v)

Ei � {L=L₀ � M=M₀}

Ef � {ret_value=f_concatenar L₀ M₀}

Eic � {ret_value=L₀}

Efc � {ret_value=f_concatenar L₀ M₀ � M=[]}

B � {long(M)>0}

I � {ret_value=L₀ ++ f_take M₀ ((f_longitud M₀)-(f_longitud M))}

Fv = long(M)

function Concatenar(L:lista de integer,M:lista de integer):lista de integer

ret_value:=L;

while (long(M)>0) do

AgregarAtras(ret_value,Primero(M));

Cola(M);
od;

endfunction

5vi)

Ei � {L=L₀ � f_longitud (L₀)>0}

Ef � {ret_value=f_maximo L₀}

Eic � {L=f_drop L₀ 1 � ret_value=f_cabeza L₀}

Efc � {L=[] � ret_value=f_maximo L₀}

B � {long(L)>0}

I � {ret_value=f_maximo (f_take L₀ (f_longitud L₀)-(f_longitud L)) �

� L=drop L₀ ((f_longitud L₀)-(f_longitud L))}

Fv = long(L)

//maximo:: [Int] -> Int

//maximo [x] = x

//maximo (x:y:xs) | x > y = maximo (x:xs)

// | otherwise = maximo (y:xs)

function Maximo(L:lista de integer):integer

ret_value:=Primero(L);

Cola(L);

while (long(L)>0) do

if (Primero(L)>ret_value) then

ret_value:=Primero(L);

else

skip;

fi;

Cola(L);

od;

endfunction

5vii)

Ei � {A=A₀}

Ef � {ret_value=f_sumar_todos A₀^dim(A)}

Eic � {ret_value=0 � i=0}

Efc � {ret_value=f_sumar_todos A₀^i � i=dim(A)}

B � {i<dim(A)}

I � {ret_value=f_sumar_todos A₀^i � (0≤i≤dim(A))}

Fv = dim(A)-i

//sumar_todos:: [Int] -> Int

//sumar_todos [x] = x

//sumar_todos (x:xs) = x + sumar_todos xs

function Sumar_todos(A:arreglo de integer):integer

var

i:integer:=0;

ret_value:=0;

while (i<dim(A)) do

ret_value:=ret_value+A[i];

i:=i+1;

od;

endfunction

5viii)

Ei � {A=A₀}

Ef � {ret_value=f_sumar_pares A₀^dim(A)}

Eic � {ret_value=0 � i=0}

Efc � {ret_value=f_sumar_pares A₀^i � i=dim(A)}

B � {i<dim(A)}

I � {ret_value=f_sumar_pares A₀^i � (0≤i≤dim(A))}

Fv = dim(A)-i

//sumar_pares:: [Int] -> Int

//sumar_pares [x] | par x = x

// | otherwise = 0

//sumar_pares (x:xs) | par x = x + sumar_pares xs

// | otherwise = sumar_pares xs

function Sumar_pares(A:arreglo de integer):integer

var

i:integer:=0;

ret_value:=0;

while (i<dim(A)) do

if (Par(A[i]) then

ret_value:=ret_value+A[i];

else

skip;

fi;

i:=i+1;

od;

endfunction

// Función auxiliar Par

Ei � {n=N₀}

Ef � {ret_value=f_par N₀}

//par:: Int -> Bool

//par x = x `mod` 2 == 0

function Par (n:integer):Bool

if (Resto(n,2)==0) then

ret_value:=True;

else

ret_value:=False;

fi;

endfunction

6i)

Ei � {L=L₀}

Ef � {ret_value=f_obtener_pares L₀ � L=[]}

Eic � {ret_value=[]}

Efc � {ret_value=f_obtener_pares L₀ � L=[]}

B � {long(L)>0}

I � {ret_value=f_obtener_pares (take L₀ ((f_longitud L₀)-(f_longitud L))) �

� L=drop L₀ ((f_longitud L₀)-(f_longitud L))}

Fv = long(L)

function Obtener_pares(L:lista de integer):lista de integer

ret_value:=[];

while (long(L)>0) do

if Par(Primero(L)) then

AgregarAtras(ret_value,Primero(L));

else

skip;

fi;

Cola(L);

od;

endfunction

6ii)

Ei � {L=L₀}

Ef � {ret_value=f_obtener_primos L₀ � L=[]}

Eic � {ret_value=[]}

Efc � {ret_value=f_obtener_primos L₀ � L=[]}

B � {long(L)>0}

I � {ret_value=f_obtener_primos (take L₀ ((f_longitud L₀)-(f_longitud L))) �

� L=drop L₀ ((f_longitud L₀)-(f_longitud L))}

Fv = long(L)

function Obtener_primos(L:lista de integer):lista de integer

ret_value:=[];

while (long(L)>0) do

if Primo(Primero(L)) then

AgregarAtras(ret_value,Primero(L));

else

skip;

fi;

Cola(L);

od;

endfunction

6iii)

Ei � {A=A₀}

Ef � {ret_value^(dim(A)*2)=f_duplicar A₀^dim(A)}

Eic � {i=0 � j=0}

Efc � {i=dim(A) � j=2*dim(A) � ret_value^(dim(A)*2)=f_duplicar A₀^dim(A)}

B � {i<dim(A)}

I � {ret_value^j=f_duplicar A₀^i � (0≤i≤dim(A))}

Fv = dim(A)-i

function Duplicar(A:arreglo de integer):arreglo de integer

var

ret_value[0..(2*dim(A))]:arreglo de integer;

i:integer:=0;

j:integer:=0;

while (i<dim(A)) do

ret_value[j]:=A[i];

ret_value[j+1]:=A[i];

i:=i+1;

j:=2*i;

od;

endfunction