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:
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.:
Monografías
