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. Práctica 5. Procedimientos. Funciones. Programación.

Agregado: 17 de JULIO de 2003 (Por Michel Mosse) | Palabras: 1705 | 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
  • Datos, informacion y comunicacion: El proceso de tomas de decisiones, subsistema de planeacion, subsistema de comercializacion, subsistema de contabilidad y finanzas, sistemas, etc.
  • Algoritmos y Estructuras de Datos I.: 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 5. La longitud de L es Par. Programación. Algoritmos.
  • Mandatos: acredita personeria.acompana poder.:

  • 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

    Práctica 5

    Procedimientos

    Fecha sugerida de finalización: 7 /7 /2000.

    Declaración de procedimientos: (Continuación de la sintaxis definida en la Práctica 4.)

    <procedimiento> ::= procedure <NombreProcedimiento> (<ListaParamInOut>)

    <declaración>

    <sec_sentencia>

    endprocedure

    <ListaParamInOut> ::= [in | out | in-out] <IdParam> : <Tipo>

    | <ListaParamInOut>, [in | out | in-out] <IdParam> : <Tipo>

    En los procedimientos no existe la variable ret_value, ya que un procedimiento no devuelve ningún valor.

    El llamado a un procedimiento es una <sentencia>.

    Nota: En los ejercicios donde se pide definir funciones o procedimientos se deben escribir las precondiciones y postcondiciones de cada uno. Además hay que plantear los invariantes y las funciones variantes en los casos en los cuales incluyan ciclos y realizar todas las demostraciones correspondientes.

    Ejercicio 1

    Dado un procedimiento que recibe una matriz cuadrada y la invierte, indicar cual es la precondición, y postcondición adecuadas.

    i)                     { ret_value = f_invertirMatriz M0 }

    ii)                   { n m = N0 M0}

    iii)                  { f_esMatrizIdentidad? ( f_multiplicarMatrices N0 m n) }

    iv)                 { n = N0 Ù m = M0}

    v)                   { n m = N0 M0 Ù esSimetrica?( in/out: N0 M0 ) }

    vi)                 { f_esMatrizIdentidad? ( f_multiplicarMatrices M0 m ) }

    vii)                TRUE

    viii)              { n m = invertirMatriz(in/out: N0M0) }

    ix)                  { ("i)("j) ( 1 £i £ Dim(nm) Ù 1 £j £ Dim(nm) Þ ( i =j Ù valor(nm,i,j) = 1 )ú ( Ø(i = j) Ù valor(nm,i,j) = 0 ) ) }

    x)                    { m = M0 Ù f_esNoSingular? M0 }

    xi)                  { f_esLaInversa? n m }

    xii)                 { ret_value = invertirMatriz(in/out N0M0) }

    Ejercicio 2

    Dado un procedimiento cuyas Precondición y Postcondición son las siguientes :

    I P º { L = L0 }

    Q º { Par( f_Long( L ) ) Ù ElementosPares ( L , L0 ) Ù ParesDistintos(L) Ù ( " i ) ( 0 £ i < f_Long( L )-1

    Ù Par ( i ) Þ f_Iésimo ( L , i + 1 ) = f_Apariciones ( f_Iésimo( L , i ) , L0 ) ) }

    donde :

    ElementosPares ( L , M ) º ( " i ) ( $ j ) ( 0 £ i < f_Long( L ) Ù Par ( i ) Ù 0 £ j < f_Long( M ) Þ

    ( $ j ) (0 £ j < f_Long( M ) Ù f_Iésimo( L, i ) = f_Iésimo( M, j ) ) ) Ù

    ( " i ) ( $ j ) ( 0 £ j < f_Long( L ) Ù Par ( j ) Ù 0 £ i < f_Long( M ) Þ

    ( $ j ) ( 0 £ j < f_Long( L ) Ù Par ( j ) Ù f_Iésimo( L, i ) = f_Iésimo( M, j ) ) )

    ParesDistintos( L ) º ( " i )(" j ) ( 0 £ i < f_Long( L ) Ù Par ( i ) Ù 0 £ j < f_Long( L ) Ù Par ( j ) Ù i¹j Þ

    f_Iésimo( L, i ) ¹ f_Iésimo( L, j ) )

    Long( L ) es una función que devuelve la longitud de la lista pasada como parámetro

    Iésimo( L , n ) es una función que devuelve el elemento de la lista L que está en la posición n

    Apariciones( n, L ) es una función que devuelve la cantidad de apariciones del elemento n en la lista L

    Explicar coloquialmente cual cuál es el comportamiento del procedimiento.

    Explicar que qué sucedería si se realizaran los siguientes cambios :

    i. Q º { Par( f_Long( L ) ) Ù ParesDistintos(L) Ù ( " i ) ( 0 £ i < f_Long( L ) - 1

    Ù Par ( i ) Þ f_Iésimo ( L , i + 1 ) = f_Apariciones ( f_Iésimo( L , i ) , L0 ) ) }

    ii. Q º { Par( f_Long( L ) ) Ù ElementosPares ( L , L0 ) Ù ( " i ) ( 0 £ i < f_Long( L ) - 1

    Ù Par ( i ) Þ f_Iésimo ( L , i + 1 ) = f_Apariciones ( f_Iésimo( L , i ) , L0 ) ) }

    iii. Q º { ElementosPares ( L , L0 ) Ù ParesDistintos(L) Ù ( " i ) ( 0 £ i < f_Long( L ) - 1

    Ù Par ( i ) Þ f_Iésimo ( L , i + 1 ) = f_Apariciones ( f_Iésimo( L , i ) , L0 ) ) }

    Ejercicio 3

    Escribir los siguientes procedimientos:

    i.                     El procedimiento Incrementar que recibe un entero y le suma 1.

    ii.                    Un procedimiento que recibe dos enteros y los devuelve ordenados: el mayor en el primer parámetro y el menor el segundo.

    iii.                  Un procedimiento que recibe un entero; si éste es par lo divide por dos, y si es impar lo deja como está.

    iv.                  Un procedimiento que recibe tres enteros, los suma y al resultado lo multiplica por el primer entero. El resultado final se guarda en el primer parámetro.

    v.                   Un procedimiento que incrementa todos los elementos del arreglo de enteros pasado como parámetro, usando el procedimiento del punto i.

    Ejercicio 4

    Dados dos arreglos de enteros que representan dos polinomios (los enteros del arreglo representan los coeficientes del polinomio), definir procedimientos para:

    i.                     Obtener un tercer vector que represente al polinomio obtenido al sumarlos.

    ii.                    Obtener un tercer vector que represente al polinomio obtenido al multiplicarlos.

    iii.                  Evaluar un polinomio en un punto.

    iv.                  Evaluar la suma de dos polinomios en un punto, usando el los puntos i y iii.

    Evaluar la suma de dos polinomios en un punto, usando el punto iii.

    Ejercicio 5

    Ahora, los polinomios están representados mediante una lista, en la cual las posiciones pares indican exponentes y las impares coeficientes. Por ejemplo, [2,1,0,3,5,2] = 2X5 + X2 + 3(X0). Con esta nueva representación, definir un procedimiento Ordenar que toma un polinomio y lo modifica, dejando en la primera posición el coeficiente de grado cero y así sucesivamente. PorUn ejemplo, Ordenar debe satisfacer: {L = [1,2,0,3,5,2]}; Ordenar(L); {L == [0,3,1,2,5,2]}.

    Ejercicio 6

    i.                     Escribir el procedimiento Ordenar_Arreglo, que ordena los elementos del arreglo de enteros pasado como parámetro.

    ii.                    Escribir el procedimiento Ordenar_Arreglo, usando el procedimiento del Ejercicio 13.ii.

    Ayuda: Es importante utilizar funciones o procedimientos auxiliares para resolver un problema (la demostración de la corrección del programa también se ve simplificada).

    Ejercicio 7

    Dado un vector de direcciones (las direcciones válidas son arriba, abajo, izquierda y derecha) y una posición inicial (un par ordenado de naturales, que representa las coordenadas sobre el plano), definir:

    i.                     Una función que obtenga la posición final.

    ii.                    Una función que calcule si la lista va a dar origen a algún ciclo.

    iii.                  Una función que calcule, para una posición dada, cuántas veces se va a pasar por ahí.

    iv.                  Una función que calcule la mayor subsecuencia sin ciclos.

    Ejercicio 8

    Se cuenta con las siguientes funciones del tipo tablero:

           Cant_filas, que dado un tablero devuelve la cantidad de filas del mismo.

           Cant_columnas, que dado un tablero devuelve la cantidad de columnas del mismo.

           Fila, que dados un tablero y un número devuelve un vector de colores.

           Columna, que dados un tablero y un número devuelve un vector de colores.

           Color, que dados un tablero y dos números devuelve el color de esa posición.

    Por ejemplo:

    Tab1

    Tab2

    Tab3

    Fila(Tab1,1) = [blanco,negro,negro,blanco]

    Fila(Tab2,3) = [blanco,negro,blanco,blanco]

    Columna(Tab3,3) = [negro,negro,blanco]

    Color(Tab2,1,4) = negro

    Se pide definir funciones para:

    i.                     Calcular la cantidad de casillas negras de un tablero, usando solamente las funciones Cant_filas, Cant_columnas y Fila.

    ii.                    Calcular la cantidad de casillas negras de un tablero, usando solamente las funciones Cant_filas, Cant_columnas y Columna.

    iii.                  Calcular la cantidad de casillas negras de un tablero, usando solamente las funciones Cant_filas, Cant_columnas y Color.

    Ejercicio 9

    Para el juego del tone, mostrado en la Práctica 3, y usando las funciones dadas altura y dirección, definir las siguientes funciones:

    i.                     Se_va_a_invertir, que devuelve verdadero si para un juego dado, una cierta casilla se va a invertir al tirar una pelota.

    ii.                    Se_va_a_invertir_n, que es verdadero si para un juego dado, una cierta casilla va a quedar invertida tras tirar n pelotas.

    Ejercicio 10

    Se tiene la función check_diagonal(M : Matriz,n:integer,v:integer):bool , cuyos estados sona especificación es:

    Ei º {M = M0 Ù v = v0 Ù n = n0 Ù 1 - dim(M) £ n £ dim(M) -1}

    Ef º { M = M0 Ù v = v0 Ù n = n0 Ù

    ret_value = ("x)("y)(x -y = n Ù 1 £ x £ dim(M) Ù 1 £ y £ dim(M) Þ M(x,y) = v)}

    P. ej.:

    check_diagonal aplicada a la matriz

    1

    2

    3

    1

    2

    43

    3

    1

    3

    4

    12

    9

    3

    8

    3

    1

    0

    4

    7

    6

    2

    -2

    5

    6

    7

    con n igual a -2 y v igual a 3 es True, porque todos los elementos de la diagonal x-y = -2 son tres. check_diagonal(M,0,2) es False, porque hay elementos en la diagonal principal que son distintos de cero.

    Se pide escribir, usando check_diagonal, la función Es_Identidad?(M : matriz):bool, que dice si una matriz es o no la identidad. La matriz identidad aquella que tiene unos en la diagonal y ceros en el resto de los elementos. Como adicional, escribir también el código de la función check_diagonal.


    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 »