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 del Parcial 18.

Agregado: 17 de JULIO de 2003 (Por Michel Mosse) | Palabras: 806 | 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
  • Mandatos: renuncia.:
  • Oficios: a banco para que informe sobre datos de una cuenta corriente (art. 25 cpcc).:
  • C++: Tipos básicos, funciones, estructuras de control, etc.: Programación. Lenguaje C++. Operaciones entre tipos básicos. Declaración y definición de funciones. Función especial main. Estructuras de control. Ejecución condicional: IF. Ciclo, la estructura WHILE. Expresiones multivaluadas: SWITCH.

  • 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 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 0j<dim(B)) al finalizar el programa

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

    1-d)

    Pc {i=0} P

    Qc {i=dim(A) ("j)(0j<dim(A0) => Propiedad (A,A0,j,B0)) B=B0}

    B {i<dim(A)}

    I {0idim(A) ("j)(0j<i => Propiedad (A,A0,j,B0)) B=B0

    ("j)(ij<dim(A) => A[j]=A0[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)>idim(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 idim(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)(0j<(f_min dim(A0) dim(B0)) => Propiedad(A,A0,j,B0))} )


    1-g)

    P {A=A0 B=B0 Dim(A)=Dim(B) (0j<dim(A0) => A0[j]0 B0[j]0)}

    Q {ret_value=f_contarceros (f_ej1 A0 B0)}

    Pc {i=0 ("j)(0j<dim(A0) => Propiedad(A,A0,j,B0)) ret_value=0}

    Qc {i=dim(A) ret_value=f_contarceros (f_take (f_ej1 A0 B0) i) B=B0

    ("j)(0j<dim(A0) => Propiedad(A,A0,j,B0))}

    B {i<dim(A)}

    I {0idim(A) ret_value=f_contarceros (f_take A i) B=B0

    ("j)(0j<dim(A0) => Propiedad(A,A0,j,B0))}

    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 L0 0if_long L0 0f_long Lf_long L0

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

    I ⌐B {f_long L=0 L=[] 0if_long L0 ret_value=f_suma (f_take L0 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 L0


    Ejercicio 3

    P {L=L0 n=N0 N0>0}

    Q {ret_value=f_promn L0 N0}

    Pc {i=0 ret_value=[]}

    Qc {i=f_div_entera (f_long L0) N0 ret_value=f_take (f_promn L0 N0) i

    L=L0 n=N0}

    B {i<f_div_entera (f_long L) n}

    I {0if_div_entera (f_long L) n L=L0 n=N0

    ret_value=f_take (f_promn L0 N0) 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=L0 n=N0 ind=ind0 f_long Lind0*N0}

    Q {ret_value=f_suma (f_take (f_drop L0 ind0*N0) N0)/2}

    Pc {i=0 ret_value=0}

    Qc {i=n ret_value=f_suma (f_take (f_drop L0 ind0*N0) i)}

    I {0in ret_value=f_suma (f_take (f_drop L0 ind0*N0) 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


    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 »