Algoritmos y Estructuras de Datos I - ALIPSO.COM: Monografías, resúmenes, biografias y tesis gratis.
Aprende sobre marketing online, desarrollo de sitios web gratis en Youtube
Suscribite para recibir notificaciones de nuevos videos:
Jueves 28 de Marzo de 2024 |
 

Algoritmos y Estructuras de Datos I

Imprimir Recomendar a un amigo Recordarme el recurso

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. Programación.

Agregado: 17 de JULIO de 2003 (Por Michel Mosse) | Palabras: 4792 | Votar | Sin Votos | Sin comentarios | Agregar Comentario
Categoría: Apuntes y Monografías > Computación > Programación >
Material educativo de Alipso relacionado con Algoritmos Estructuras Datos
  • Corrosión en estructuras y puentes.:
  • Estructuras de datos: Tipos abstractos de datos. Un concepto importante en ingeniería: el de Caja Negra. El rol de las Estructuras de Datos en un programa. Definición y propiedades de los TADs. Bases de datos.
  • Bases de datos: Objetivos de las “Bases de Datos”. Abstracción de datos. Facilidades del “Sistema de Gestión de Bases de Datos” (SGBD). Estructura general de los SGBD. Algoritmos. Cobertura canónica.

  • Enlaces externos relacionados con Algoritmos Estructuras Datos

    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=N0 m=M0}

    1.1.ii)

    b) Q {ret_value = M0*N0}

    1.1.iii)

    b)Pc {ret_value = 0 i = 0 n=N0 m=M0}

    B {i < f_abs n }

    I {ret_value = m*i 0 i (f_abs n) n=N0 m=M0}

    Fv = (f_abs n) - i

    Qc {ret_value = (f_abs n) * m n=N0 m=M0}

    1.1.iv)

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

    P {n=N0}

    Q {ret_value = f_abs N0}

    1.2.i) a) P {n=N0 }

    1.2.ii) c) Q { (ret_value = f_primo(N0) ) }

    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=I0 n=N0 I0>0 (f_par(I0) N00)}

    a-ix) Q{ret_value=f_raizEnesima I0 N0}

    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 = N0 m = M0 }

    Pc { i=m ret_valuefalse ((N0>=M0) => (n=N0 m=M0 ))

    ((N0<M0) => (n=M0 m=N0)}

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

    n = N0 m = M0 N0 <= M0 }

    B ( i>n )

    //Fv = m - i

    //Qc Q { ret_value ($k)(( N0 <= k <= M0) 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=N0 m=M0 M0>0 N00}

    Q {ret_value=f_resto N0 M0}

    Pc {ret_value=N0}

    Qc Q

    B {ret_valuem}

    I {(f_resto ret_value m = f_resto N0 M0) (0ret_valuen)}

    Fv = (f_resto N0 M0) - 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_valuem) do

    ret_value:=ret_value-m;

    od;

    endfunction

    6-ii)

    P {n=N0 m=M0 M0>0 N00}

    Q {ret_value = f_division N0 M0}

    Pc {ret_value=0}

    Qc Q

    B {nm}

    I {(f_resto n m = f_resto N0 M0) (ret_value*m + n = N0) (0nN0)}

    Fv = n - (f_resto N0 M0)

    //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 (nm) do

    n:=n-m;

    ret_value:=ret_value+1;

    od;

    endfunction

    6-iii)

    P {n=N0 m=M0 ⌐(N0=0 M0=0) (N00) (M00)}

    Q {ret_value = f_mcd N0 M0}

    Pc P

    Qc {n=f_mcd N0 M0 m=n}

    B {nm}

    I {f_mcd(N0,M0)=f_mcd(n,m) (f_mcd(N0,M0)nN0) (f_mcd(N0,M0)mM0)}

    FV = (n+m) - 2*(f_mcd N0 M0)

    //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 (nm) do

    if (n>m) then

    n:=n-m;

    else

    m:=m-n;

    od;

    ret_value:=n;

    endfunction

    Ejercicio 7

    7-i)

    P {n=N0 m=M0 N0M0 N0>0 M00}

    Q {ret_value=f_comb N0 M0}

    //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=N0 m=M0}

    Q {ret_value=f_divisor N0 M0}

    //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=N0 N0>=0}

    Q {ret_value=($j)(0jN0 j*j=N0)}

    Pc {i=0 ret_value=False}

    Qc {i=N0+1 ret_value=($j)(0jN0 j*j=N0)}

    B {in}

    I {0in+1 ret_value=($j)(0≤j<i j*j=N0)}

    Fv = N0-(i-1)

    Cuadrado_perfecto(n:integer):bool

    var

    i:integer:=0;

    ret_value:=False;

    while (in) do

    if (i*i)=n) then

    ret_value:=True;

    else

    skip;

    fi;

    i:=i+1;

    od;

    endfunction


    7-iv)

    P {n=N0 N0>0}

    Q {ret_value=f_sumadiv N0}

    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=N0 N0>0}

    Q {ret_value=f_primo2 N0}

    //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=N0}

    Q {ret_value=f_sig_primo N0}

    Pc {n=N0+1}

    Qc {n=f_sig_primo N0}

    B {⌐(Primo(n)}

    I {(f_sig_primo N0 = f_sig_primo (n-1)) (N0<n<=f_sig_primo N0)}

    Fv = f_sig_primo N0 - 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=N0 N0>=0}

    Q {ret_value=f_cant_prim N0}

    Pc {i=1 ret_value=0}

    Qc {i=N0+1 ret_value=f_cant_prim N0}

    I {(ret_value=f_cant_prim (i-1)) (1<=i<=N0+1)}

    Fv = N0+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=A0 }

    Q {ret_value=f_normaDos A0^Dim(A0)}

    8-b)

    P {l=L0 n=N0 N0<Long(L0)}

    Q {(f_mismosElementos L0 ret_value) ("i)(0iLong(L0)

    (i < N0 ( f_iesimo ret_value i ) < ( f_iesimo L0 N0 )) ú

    (i N0 ( f_iesimo ret_value i) (f_iesimoL0 N0))}

    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 N0 es primo, antes me daba el siguiente primo, ahora me podría dar el mismo N0 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=L0 elem=elem0}

    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=L0}

    Q {ret_value=f_reverso L0}

    Pc {ret_value=[]}

    Qc {L=[] ret_value=f_reverso L0} P

    B {long(L)>0}

    I {f_concatenar (f_reverso ret_value) L =s= L0}

    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=L0 iesimo=iesimo0}

    Q {ret_value=f_i_esimo L0 iesimo0}

    Pc {i=0} P

    Qc {i=iesimo L=f_drop L0 i}

    B {(iiesimo)}

    I {L=f_drop L0 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 (iiesimo) do

    Cola(L);

    i:=i+1;

    od;

    ret_value:=Primero(L);

    endfunction


    10-iii)

    P {L=L0 pos=pos0 elem=elem0}

    Q {ret_value=f_asignar L0 pos0 elem0}

    Pc1 {ret_value=[] lorig=f_long L0 pos0<f_long L0} P

    Qc1 {ret_value=f_take L0 pos0 L=f_drop L0 pos0 pos=pos0 elem=elem0}

    Pc2 {ret_value=(f_take L0 pos0 ++ [elem0]) L=f_drop L0 (pos0+1) pos=pos0 elem=elem0}

    Qc2 {ret_value=(f_take L0 pos0 ++ [elem0] ++ f_drop L0 (pos0+1)) L=[] pos=pos0 elem=elem0}

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

    I1 {ret_value=f_take L0 ((f_long L0)-(f_long L))

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

    Fv1 = pos0-(lorig-(f_longitud L))

    B2 {(f_long L)>0}

    I2 {ret_value=f_take L0 pos0 ++ [elem0] ++

    ++ f_drop (f_take ((f_long L0)-(f_long L))) (pos0+1)

    L=f_drop L0 ((f_long L0)-(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=L0}

    Q {ret_value=f_comienzo L0}

    //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=L0 (f_long L0)>0}

    Q {ret_value=f_ultimo L0}

    //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=A0}

    Q {ret_value=f_reverso A0^dim(A)}

    Pc {i=0}

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

    B {i<dim(A)}

    I {ret_value^i=f_reverso (f_drop (A0^dim(A)) (dim(A)-i)) (0idim(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=A0}

    Q {ret_value=f_capicua A0^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=L0}

    Q {ret_value=f_limpiar_duplicados L0}

    Pc {ret_value=[] i=0}

    Qc {ret_value=f_limpiar_duplicados L0 L=[]

    i=(f_long L0)-(f_contar_repetidos L0)}

    B {(f_long L)>0}

    I {ret_value=f_take (f_limpiar_duplicados L0) i L=f_sacar_elmtos_hasta L0 i

    (0i≤((f_long L0)-(f_contar_repetidos L0))

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

    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 L0) i" estoy tomando todos los elementos de f_limpiar_duplicados L0 (o sea que i es la longitud de la lista original menos los repetidos (i=(f_longitud L0)-(f_contar_repetidos L0))

    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=L0 elem=elem0}

    Q {ret_value=f_sacar_elemento elem0 L0}

    Pc {ret_value=[] i=0}

    Qc {ret_value=f_sacar_elemento elem0 L0 i=f_long L0 L=[]}

    B {i<f_long L}

    I {ret_value=f_sacar_elemento elem0 (f_take L0 i) L=f_drop L0 i

    (0if_long L0)}

    Fv = long(L0)-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=L0}

    Q {ret_value=f_limpiar_duplicados L0}

    Pc {ret_value=[] i=0} P

    B {i<(f_long L)}

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

    Qc {i=(f_long L0) ret_value=f_limp_dup_hta L0 (f_long L0)}

    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=L0 elem=elem0}

    Q {ret_value=f_pertenece elem0 L0}

    Pc {i=0 ret_value=False} P

    B {i<(f_long L)}

    I {0<=i<=(f_long L) ret_value=f_pertenece elem0 (f_take L0 i) L=L0}

    Qc {i=(f_long L) ret_value=f_pertenece elem0 (f_take L0 (f_long L0))}

    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=L0}

    Q {ret_value=f_apariciones L0}

    Pc {i=0 ret_value=[]} P

    B {i<(f_long L)}

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

    Qc {i=(f_long L) ret_value=f_alternar_hta L0 (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=L0 elem=elem0}

    Q {ret_value=f_pertenece_pospar elem0 L0}

    Pc {i=0 ret_value=False} P

    B {i<long(L)}

    I {0<=i<=(f_long L) ret_value=f_pertenece_pospar elem0 (f_take L0 i) L=L0}

    Qc {i=(f_long L) ret_value=f_pertenece_pospar elem0 (f_take L0 (long(L0))

    // 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=L0 elem=elem0}

    Q {ret_value=f_cantidad_apariciones L0 elem0}

    Pc {i=0 ret_value=0} P

    B {i<(f_long L0)}

    I {0<=i<=(f_long L0) ret_value=f_cantidad_apariciones (f_take L0 i) elem0}

    Qc {i=(f_long L0) ret_value=f_cantidad_apariciones (f_take L0 (f_long L0)) elem0}

    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=A0}

    Q {ret_value=f_elev_cuad A0^dim(A)}

    Pc {i=0 ret_value=[]}

    B {i<dim(A)}

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

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

    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=A0}

    Q {ret_value=f_ordenar_dec A0^dim(A0)}

    Pc {L=A0^dim(A0) i=0 L=L0 ret_value=[]}

    Qc {i=dim(A) ret_value=f_take (f_ordenar_dec L0) i A=A0 L=[]}

    B {i<dim(A)}

    I {0idim(A) A=A0 L=(f_sacar_mayores_hta L0 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=A0}

    Q {ret_value=A0^dim(A0)}

    Pc {i=0 ret_value=[] A=A0}

    Qc {i=dim(A0) ret_value=A0^dim(A0)}

    B {i<dim(A)}

    I {0idim(A0) A=A0 ret_value=A0^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=L0 f_long L0>0}

    Q {ret_value=f_mayor L0}

    Pc {i=1 ret_value=f_head L0}

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

    B {i<f_long L}

    I {1if_long L0 ret_value=f_mayor (f_take L0 i) L=L0}

    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=elem0 L=L0 f_pertenece elem0 L0}

    Q {ret_value=f_sacar_uno elem0 L0}

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

    Qc {i=f_long L0 saque?=True ret_value=f_take (f_sacar_uno elem0 L0) (i-1)}

    B {i<f_long L}

    I {0if_long L L=L0 elem=elem0

    ((saque?=True ret_value=f_take (f_sacar_uno elem0 L0) (i-1)) ú

    (saque?=False ret_value=f_take (f_sacar_uno elem0 L0) 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=A0}

    Q {ret_value=f_ordenar_dec A0^dim(A0)}

    Pc {i=0} P

    Qc {i=dim(A0) A^dim(A0)=f_ordenar_dec A0^dim(A0)}

    B {i<dim(A)}

    I {0idim(A)

    f_drop A^dim(A) (dim(A)-i)=f_ordenar_dec (f_drop A0^dim(A0) (dim(A0)-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=A0 i=i0}

    Q {f_drop A^dim(A) (dim(A)- i0)=f_drop (f_ordenar A0^dim(A)) (dim(A)- i0)}

    Pc {j=1}

    Qc {j=dim(A)} Q

    B {j<dim(A)}

    I {1jdim(A)


    Ejercicio 12

    12-i-a) VERSION 1

    P {L=L0 M=M0 (f_long M0)>=(f_long L0)}

    Q {ret_value=f_prefijo L0 M0}

    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=L0 M=M0}

    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=L0 M=M0}

    Q {ret_value=f_prefijo L0 M0}

    Pc {i=0 ret_value=True f_long L0f_long M0}

    B {i<f_long L}

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

    Qc {i=f_long L ret_value=("j)(0j<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=L0 M=M0 (f_long M0)>=(f_long L0)}

    Q {ret_value=f_sufijo L0 M0}

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

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

    endfunction


    12-ii-b)

    P {L=L0 M=M0}

    Q {ret_value=f_subcadena L0 M0}

    Pc {ret_value=False}

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

    I {(f_long L)<=(f_long M)<=(f_long M0) L=L0

    ret_value=f_prefijo L M M=f_cola M}

    Qc {(f_long L)=(f_long M) L=L0 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=L0 M=M0}

    Q {ret_value=f_sacar_primero L0 M0}

    Pc {ret_value=[]}

    Qc {ret_value=f_sacar_primero L0 M0

    L=f_drop L0 ((f_long M0)-(f_long (f_sacar_primero L0 M0))) M=[]}

    B {(f_long M)>0}

    I {M=f_drop M0 ((f_long M0)-(f_long M))

    ret_value=f_take (f_sacar_primero L0 M0) ((f_long M0)-(f_long M))

    L=f_drop L0 (f_long M0 -(f_long M + f_long ret_value))

    (0≤(f_long M)≤f_long M0)}

    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=L0 M=M0}

    Ef {ret_value=f_concatenar L0 M0}

    Eic {ret_value=L0}

    Efc {ret_value=f_concatenar L0 M0 M=[]}

    B {long(M)>0}

    I {ret_value=L0 ++ f_take M0 ((f_longitud M0)-(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=L0 f_longitud (L0)>0}

    Ef {ret_value=f_maximo L0}

    Eic {L=f_drop L0 1 ret_value=f_cabeza L0}

    Efc {L=[] ret_value=f_maximo L0}

    B {long(L)>0}

    I {ret_value=f_maximo (f_take L0 (f_longitud L0)-(f_longitud L))

    L=drop L0 ((f_longitud L0)-(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=A0}

    Ef {ret_value=f_sumar_todos A0^dim(A)}

    Eic {ret_value=0 i=0}

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

    B {i<dim(A)}

    I {ret_value=f_sumar_todos A0^i (0idim(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=A0}

    Ef {ret_value=f_sumar_pares A0^dim(A)}

    Eic {ret_value=0 i=0}

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

    B {i<dim(A)}

    I {ret_value=f_sumar_pares A0^i (0idim(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=N0}

    Ef {ret_value=f_par N0}

    //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=L0}

    Ef {ret_value=f_obtener_pares L0 L=[]}

    Eic {ret_value=[]}

    Efc {ret_value=f_obtener_pares L0 L=[]}

    B {long(L)>0}

    I {ret_value=f_obtener_pares (take L0 ((f_longitud L0)-(f_longitud L)))

    L=drop L0 ((f_longitud L0)-(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=L0}

    Ef {ret_value=f_obtener_primos L0 L=[]}

    Eic {ret_value=[]}

    Efc {ret_value=f_obtener_primos L0 L=[]}

    B {long(L)>0}

    I {ret_value=f_obtener_primos (take L0 ((f_longitud L0)-(f_longitud L)))

    L=drop L0 ((f_longitud L0)-(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=A0}

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

    Eic {i=0 j=0}

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

    B {i<dim(A)}

    I {ret_value^j=f_duplicar A0^i (0idim(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


    Votar

    Ingresar una calificación para del 1 al 10, siendo 10 el máximo puntaje.

    Para que la votación no tenga fraude, solo se podrá votar una vez este recurso.

    Comentarios de los usuarios


    Agregar un comentario:


    Nombre y apellido:

    E-Mail:

    Asunto:

    Opinión:



    Aún no hay comentarios para este recurso.
     
    Sobre ALIPSO.COM

    Monografias, Exámenes, Universidades, Terciarios, Carreras, Cursos, Donde Estudiar, Que Estudiar y más: Desde 1999 brindamos a los estudiantes y docentes un lugar para publicar contenido educativo y nutrirse del conocimiento.

    Contacto »
    Contacto

    Teléfono: +54 (011) 3535-7242
    Email:

    Formulario de Contacto Online »