Algoritmos y Estructuras de Datos I

Solución del Tercer Parcial – Segundo cuatrimestre de 1998

Problema 1

Algoritmo de la función "PrimerGame"

function PrimerGame (L: lista de bool): bool

var

i: integer := 1;

tanteador: string := "0-0";

res: bool

while i £ long(L)  and  not (tanteador = "Game")  do

Puntaje (tanteador, i-ésimo(L, i));

i := i + 1

od;

if tanteador = "Game"

then res := i-ésimo(L, i - 1)

else Error("Nadie ganó.")

fi;

return res

endfunction

Metalenguaje

Ei_función º { True }

Ei_ciclo º { i = 1  Ù  tanteador = "0–0" }

B º { i £ long(L)  Ù  tanteador ¹ "Game" }

Fv = ÚltimoPunto L + 1 – i

I º { 1 £ i £ long(L) + 1  Ù  tanteador = Juego "0–0" (take L (i – 1))
      Ù ( i > 1 Þ Juego "0–0" (take L (i – 2)) ¹ "Game") }

Ef_ciclo º { i = ÚltimoPunto L + 1  Ù tanteador = Juego "0–0" L }

Ef_función º { res = PrimerGame L }

Nota: la última parte del invariante (i > 1 Þ Juego ...) es indispensable para
poder realizar la implicación I Ù ØB Þ Ef_ciclo­ .

Definición de las funciones usadas en el metalenguaje

La función Juego recibe un string y una lista de bool. Devuelve el estado del tanteador
después de jugarse los puntos de la lista, a partir del tanteador del string.

Juego :: string ® [bool] ® string

Juego  s  [ ]  =  s

Juego  s  x:xs  =  IF s == "Game"                THEN                s

                                                               ELSE                Juego  (Puntaje s x)  xs

Si la lista recibida tiene puntos suficientes para terminar el game, la función PrimerGame
devuelve el ganador del mismo; en caso contrario, devuelve Error.

PrimerGame :: [bool] ® bool

PrimerGame  xs  =  IF  Juego "0–0" xs == "Game"                THEN                i-ésimo xs (ÚltimoPunto xs)

                                                                                              ELSE                Error ("Nadie ganó.")

La función ÚltimoPunto devuelve la posición en la lista del último punto jugado en el primer game.
Es decir, el punto en el cual se define el primer game.
Nótese que si el game no termina, devuelve la longitud de la lista.

ÚltimoPunto :: [bool] ® integer

ÚltimoPunto [ ] = 0

ÚltimoPunto x:xs =  IF  Juego "0–0" (comienzo x:xs) == "Game"                THEN                ÚltimoPunto (comienzo x:xs)

                                                                                                                             ELSE                longitud(x:xs)

Las funciones restantes ya fueron definidas en las prácticas:

i-ésimo :: [bool] ® integer ® bool

comienzo :: [bool] ® [bool]

longitud :: [bool] ® integer

Problema 2

Algoritmo de la función "Concéntrica"

function Concéntrica (M: Matriz): bool

var

i: integer := 1;

res: bool := True

while i £ div(dim(M), 2) do

res := res and Anillo(i, M);

i := i + 1

od;

return res

endfunction

Metalenguaje

Ei_función º { True }

Ei_ciclo º { i = 1  Ù  res = True }

B º { i £ div (dim M) 2 }

Fv = div (dim M) 2 + 1 – i

I º { 1 £ i £ (div (dim M) 2) + 1  Ù  res = ("j) (1 £ j < i Þ Anillo (j, M)) }

Ef_ciclo º { res = ("j) (1 £ j < (div (dim M) 2) + 1  Þ Anillo (j, M)) }

Ef_función º { res = ("j) (1 £ j < (div (dim M) 2) + 1  Þ  Anillo (j, M)) }

Definición de los predicados usados en el metalenguaje

Anillo (j, M) º {  ($x) ( ("k) (j £ k £ dim M – j + 1  Þ  M(j, k) = x  Ù  M(k, j) = x  Ù  M(dim M – j + 1, k) = x
                                Ù  M(k, dim M – j + 1) = x ) ) }

Algoritmo de la función "Anillo"

function Anillo (i: integer, M: Matriz): bool

var

x: integer := M(i, i);

j: integer := i;

res: bool := True

while j £ dim(M)-i+1 do

res := res and (M(i, j) = k and M(j, i) = k and M(Dim(M)-i+1, j) = k

and M(j, Dim(M)-i+1) = k);

j := j + 1

od;

return res

endfunction

Metalenguaje

Ei_función º { i £ div (dim M) 2 }

Ei_ciclo º { j = i  Ù  x = M(i, i)  Ù  res = True }

B º { j £ dim M – i + 1 }

Fv = dim M – i + 2 – j

I º { i £ j £ dim M – i + 2  Ù  x = M(i, i)  Ù  res = ("k) ( i £ k < j  Þ  M(i, k) = x  Ù  M(k, i) = x
                      Ù  M(dim M – i + 1, k) = x  Ù  M(k, dim M – i + 1) = x ) }

Ef_ciclo º { x = M(i, i)  Ù  res = ("k) ( i £ k < dim M – i + 2  Þ  M(i, k) = x  Ù  M(k, i) = x
                  Ù  M(dim M – i + 1, k) = x  Ù  M(k, dim M – i + 1) = x ) }

Ef_función º { res = Anillo (i, M) }