Algoritmos y Estructuras de Datos

Nelson Baloian

Nociones básicas de programación

1. Validación de Programas Iterativos
2. Diagramas de Estados
3. Recursividad
4. Recursividad y Tabulación (Programación Dinámica)

En esta sección se revisarán los elementos básicos que se van a utilizar para escribir programas. Esto supone que los alumnos ya saben programar, y es sólo un resumen y una ordenación de conceptos. La notación utilizada es la del lenguaje Java, pero los conceptos son más generales y se aplican a muchos otros lenguajes similares.

Validación de programas iterativos (Clase de Miércoles 10 de Septiembre)

(como explicarlos de modo de demostrar que hacen lo que uno quiere que hagan)

¿Cómo escribir un ciclo?

1. Encontrar un invariante adecuado. Para esto, a menudo es conveniente "relajar" la meta (estado final) al que se desea llegar. Por ejemplo, si se desea obtener:

// m == max(a[1].,,,.a[n])

se puede re-escribir esta condición separándola en dos condiciones que se puedan satisfacer independientemente:

// m == max(a[1].,,,.a[k]) && k==n

Esto, que puede parecer ocioso, es muy útil, porque a continuación se relaja la exigencia de esta condición, haciendo que se cumpla la primera parte, pero dejando que la segunda se satisfaga con "k<=n".

2. Escribir la inicialización, la cual debe asegurar que el invariante se cumpla antes de empezar a iterar.
3. Encontrar la condición de término. Esto se obtiene de comparar "qué le falta" al invariante para ser igual al estado final.
4. Escribir el cuerpo del ciclo, el cual debe:
• conseguir que el proceso avance, de modo que termine algún día, y

o preservar el invariante.

Estos dos últimos objetivos suelen ser contrapuestos. Al efectuar un avance en el proceso, los valores de las variables cambian, con el resultado que a menudo se deja de satisfacer el invariante. Por lo tanto, el resto del cuerpo del ciclo se suele dedicar a tratar de recuperar la validez del invariante.

Algoritmos simples de ordenación

Considere el problema de poner los elementos de un arreglo a[0],...,a[n-1] en orden ascendente.

Se estudiarán varias soluciones, todas ellas consistentes en algoritmos sencillos, pero no muy eficientes. Estas distintas soluciones van a provenir de escoger distintos invariantes, o distintas maneras de preservarlos.

Ordenación por inserción

Este algoritmo va construyendo un trozo ordenado del arreglo al extremo izquierdo, y en cada iteración le agrega un nuevo elemento a ese grupo.

Invariante:

Esto es: los k primeros elementos ya están ordenados.

// Ordenar a[0],...,a[n-1] por inserción (borrador)
k = 0; // inicialmente no hay elementos ordenados (k=1 también funcionaría)
while( k<n )
 {
 Insertar a[k] entre a[0],...,a[k-1];
 ++k;
 }

Si la inserción se efectúa correctamente, es evidente que el programa anterior ordena correctamente al conjunto.

El siguiente problema es ver cómo se realiza la inserción:

Insertar a[k] entre a[0],...,a[k-1] =>
for( j=k; j>0 && a[j-1]>a[j]; --j )
 {
 // intercambiar a[j-1] con a[j]
 t = a[j];
 a[j] = a[j-1];
 a[j-1] = t;
 }

Al seguir el proceso de la inserción, se puede observar que la variable t toma siempre el mismo valor: el del elemento que se está insertando. Por lo tanto, se puede optimizar el programa realizando una única asignación a t antes de comenzar el ciclo. Otra observación es que la mayoría de las asignaciones a a[j-1] son inútiles, porque esa variable va a ser sobre-escrita en la iteración siguiente. Luego, se puede evitar esas asignaciones, reemplazándolas por una sola al final del ciclo:

Insertar a[k] entre a[0],...,a[k-1] =>
// versión optimizada
t = a[k];
for( j=k; j>0 && a[j-1]>t; --j )
 a[j] = a[j-1];
a[j] = t;

Efectuando la sustitución de esta versión, se obtiene la siguiente versión final para el algoritmo de ordenación:

// Ordenar a[0],...,a[n-1] por inserción
k = 0; // inicialmente no hay elementos ordenados (k=1 también funcionaría)
while( k<n )
 {
 // Insertar a[k] entre a[0],...,a[k-1]
 t = a[k];
 for( j=k; j>0 && a[j-1]>t; --j )
 a[j] = a[j-1];
 a[j] = t;
 
 ++k;
 }

El tiempo que demora este algoritmo en el peor caso es del orden de n², lo que se denotará O(n²).Se puede demostrar que esto mismo es cierto si se considera el caso promedio.

Ordenación por Selección

Este algoritmo se basa en hacer pasadas sucesivas sobre los datos. En cada pasada, se encuentra el máximo del arreglo, y se lo lleva al extremo derecho. Una vez hecho esto, ese elemento deja de ser considerado, porque se encuentra ya en su posición definitiva. Esto conduce al siguiente invariante:

En palabras: "Los elementos desde k hasta n-1 ya están ordenados y son mayores que los primeros k".

// Ordenar a[0], ..., a[n-1] por selección
 
k = n; // inicialmente los n primeros están desordenados
while( k>=2 )
 {
 Llevar el max de a[0], ..., a[k-1] hacia a[k-1];
 --k;
 }

Donde

Llevar el max de a[0], ..., a[k-1] hacia a[k-1] =>
i = 0; // a[i] es el max hasta el momento
for( j=1; j<=k-1; ++j )
 if( a[j]>a[i] )
 i = j;
// ahora intercambiamos a[i] con a[k-1]
t = a[i];
a[i] = a[k-1];
a[k-1] = t;

El tiempo que demora este algoritmo es O(n²), y no hay diferencia entre el peor caso y el caso promedio.

Más adelante se verá una forma diferente de realizar el proceso de encontrar el máximo, que permitirá que ese proceso sea más eficiente. Básicamente, se trata que al encontrar el máximo una vez, es posible obtener información adicional que facilite encontrar luego el segundo máximo, y así sucesivamente.

Una forma de hacer esto es construir un torneo balanceado, al estilo de los torneos de tenis. Una vez que se han jugado todos los partidos del torneo, con n jugadores, si se desea encontrar al (verdadero) sub-campeón, basta con sustituir imaginariamente al campeón por un jugador pésimo, y jugar de nuevo los log n partidos en que estuvo involucrado el campeón. El resultado es un método de ordenación que demora tiempo O(n log n).

Ordenación de la Burbuja

Este método se basa en hacer pasadas de izquierda a derecha sobre los datos, intercambiando pares de elementos adyacentes que estén fuera de orden. Al final de cada pasada, en forma natural el máximo estará en la posición de más a la derecha (que es su posición final) y puede por lo tanto ser excluido en pasadas sucesivas.

Esto conduce al siguiente invariante (idéntico al de ordenación por selección):

El borrador del programa es:

// Ordenar a[0], ..., a[n-1] por la burbuja (borrador)
k = n;
while( k>1 )
 {
 Hacer una pasada sobre a[0], ..., a[k-1];
 Disminuir k;
 }

Donde

Hacer una pasada sobre a[0], ..., a[k-1] =>
for( j=0; j<=k-2; ++j )
 if( a[j]>a[j+1] )
 { // Intercambiar a[j] con a[j+1]
 t = a[j];
 a[j] = a[j+1];
 a[j+1] = t;
 }

y

Disminuir k =>
--k;

Esto último puede parecer ocioso, pero pronto se verá que el expresarlo de esta manera da una flexibilidad que resulta útil.

Un problema que presenta este programa es que si el archivo está incialmente ordenado, el programa igual hace n pasadas, cuando después de la primera ya podría haberse dado cuenta que el archivo ya estaba ordenado.

Para aprovechar cualquier posible orden que pueda haber en el archivo, se puede hacer que el programa anote ("recuerde") el lugar en donde se produjo el último intercambio. Si la variable i se define de manera que el último intercambio en una pasada dada fue entre a[i-1] y a[i], entonces todos los elementos desde a[i] en adelante están ya ordenados (de lo contrario habría habido intercambios más hacia la derecha), y por lo tanto k se puede disminuir haciendo que sea igual a i:

Hacer una pasada sobre a[0], ..., a[k-1] =>
i=0;
for( j=0; j<=k-2; ++j )
 if( a[j]>a[j+1] )
 { // Intercambiar a[j] con a[j+1]
 t = a[j];
 a[j] = a[j+1];
 a[j+1] = t;
 //Recordar el lugar del último intercambio
 i = j+1;
 }
Disminuir k =>
k=i;

El tiempo que demora este algoritmo tanto en el peor caso como en promedio es O(n²).

Cálculo de xⁿ

Un algoritmo simple consiste en multiplicar n veces:

// Algoritmo simple
y = 1;
for( j=n; j>0; --j )
 y = y*x;

Este algoritmo evidentemente toma tiempo O(n), y su invariante se puede escribir como

 y * xj == xn

Es posible encontrar un algoritmo sustancialmente más eficiente de la siguiente manera. Primero se desvinculan las dos ocurrencias de x en el invariante:

y = 1;
z = x;
for( j=n; j>0; --j )
 y = y*z;

con invariante

 y * zj == xn

Esto podría parecer ocioso, pero permite hacer una optimización al observar que está permitido modificar la variable z al inicio del ciclo siempre que se mantenga la validez del invariante. En particular, si j resulta ser par, podemos elevar z al cuadrado si al mismo tiempo dividimos j por 2. De esta manera, el invariante sigue igual, pero j disminuye mucho más rápido.

Mejor todavía, si esto se puede hacer una vez, entonces se puede hacer muchas veces siempre que j siga siendo par:

y = 1;
z = x;
for( j=n; j>0; --j ) // Invariante: y * zj == xn
 {
 while( j es par )
 {
 z = z*z;
 j = j/2;
 }
 y = y*z;
 }

La detección que j es par se puede implementar como

j es par =>
j&1 == 0

Este algoritmo demora tiempo O(log n), lo cual se debe a que j sólo se puede dividir log n veces por 2 antes de llegar a 1. Es cierto que j sólo se divide cuando es par, pero si es impar en una iteración del for, está garantizado que será par a la siguiente.

Diagramas de Estados (Clase de Miércoles 17 de Septiembre)

Un diagrama de estados nos permite visualizar los diferentes estados por los que va pasando un programa. Las transiciones de un estado a otro se realizan ya sea incondicionalmente o bajo una condición. Además, pueden ir acompañadas de una acción que se realiza junto con la transición.

Ejemplo: Contar palabras en una frase.

Para simplificar, supongamos que la frase está almacenada en un string s, y supongamos que la frase termina con un punto. Por ejemplo,

 String s = "Este es un ejemplo.";

Para los fines de este ejemplo, diremos que una "palabra" es cualquier secuencia de caracteres consecutivos distintos de blanco (y punto).

Para resolver este problema, examinaremos los caracteres del string de izquierda a derecha, usando charAt(k), y lo que se haga con cada caracter depende si estábamos dentro o fuera de una palabra. Esto último correspnde al estado del programa.

Veremos dos formas distintas de llevar este diagrama de transición a un programa. A pesar que ambos se ven muy distintos, en realidad representan exactamente el mismo proceso:

// Version 1
 
np = 0;
estado = FUERA;
for( k=0; (c=s.charAt(k))!='.'; ++k )
 {
 if( estado==FUERA )
 {
 if( c!=' ' )
 {
 ++np;
 estado = DENTRO;
 }
 }
 else // estado==DENTRO
 if( c==' ' )
 estado = FUERA;
 }
// Version 2
 
k = 0;
np = 0;
while( s.charAt(k)!='.' )
 { // estado==FUERA
 while( s.charAt(k)==' ' )
 ++k;
 if( s.charAt(k)=='.' )
  break;
 ++np;
 ++k;
 
 // estado==DENTRO
 while( s.charAt(k)!=' ' && s.charAt(k)!='.' )
 ++k;
 if( s.charAt(k)=='.' )
 break;
 ++k;
 }

Problema

Escribir una función con encabezado pubic static double valor(String s) que recibe como parámetro un string  que contiene un número real terminado con un ; y entregue su valor. Si el número está ma escrito debe retornar Math.MAXDOUBLE (el máximo double que puede guardar java).

Esto se puede abordar con ayuda de un diagrama de estados:

// Version 1

double valor = 0;

int n;

int final ENTERO =1, DECIMAL =2, ERROR =3, FIN =0;
estado = ENTERO;
for( k=0; k < s.length() && estado != FIN && estado != ERROR; ++k ){

if( estado== ENTERO)
if( s.charAt(k) <= '9' && s.charAt(k) >= '0' )

valor = valor*10 + s.charAt(k)-'0';

else if (s.charAt(k) == ';')

estado = FIN;

else if (s.charAt(k) == '.') {

          n = 10;

estado = DECIMAL;

else estado = ERROR;

else if(estado == DECIMAL)

if( s.charAt(k) <= '9' && s.charAt(k) >= '0' ) {

valor = valor + (s.charAt(k)-'0')/n;

n = n*10;

        }

else if (s.charAt(k) == ';')

estado = FIN;

else estado = ERROR;

}

if (estado == FIN)return valor else return Math.MAXDOUBLE;

// Version 2

double valor = 0;

k = 0;
while(k < s.length() && s.charAt(k) <= '9' && s.charAt(k) >= '0') {

valor = valor*10 + s.charAt(k)-'0';

k++;

}

if (s.charAt(k) == ';') return valor

else if (s.charAt(k) != '.') return Math.MAXDOUBLE;

int n = 10;

while (k < s.length() && s.charAt(k) <= '9' && s.charAt(k) >= '0') {

valor = valor + (s.charAt(k)-'0')/n;

n = n*10;

k++;

}

if (s.charAt(k) == ';') return valor

else return Math.MAXDOUBLE;

Problema Propuesto (traer solución el Miércoles 24 de Septiembre)

escribir una función que tenga el encabezado public static true valido(String s) que retorna true si el string s empieza con uno o más caracteres 'a' seguidos por uno o más caraceters 'b' y terminados con uno o más caracteres 'c' seguido por un carácter ';'. Además debe imprimir (con System.out.println(....) ) la cantidad de caracteres a, b y c que venían en la secuencia.

por ejemplo: aabbbbcc; , abbbbc; , abc;, aaabc; son secuencias válidas. bbbccc; , axbbccc; , aaaccc; , aabcc  (no tiene ';' al final) son inválidas.

El diagrama de estados que resuelve este problema es el siguiente: 

Recursividad (Clase de Miércoles 24 de Septiembre)

Al programar en forma recursiva, buscamos dentro de un problema otro subproblema que posea su misma estructura.

Ejemplo: Calcular xⁿ.

// Version 1
 
public static float elevar( float x, int n )
 {
 if( n==0 )
 return 1;
 else
  return x * elevar(x, n-1);
 }
// Version 2
 
public static float elevar( float x, int n )
 {
 if( n==0 )
 return 1;
 else if( n es impar )
 return x * elevar( x, n-1 );
 else
 return elevar( x*x, n/2 );
 }

Ejemplo: Torres de Hanoi.

public class TorresDeHanoi
 {
 static void Hanoi( int n, int a, int b, int c )
 {
 if( n>0 )
 {
 Hanoi( n-1, a, c, b );
 System.out.println( a + " --> " + c );
 Hanoi( n-1, b, a, c );
 }
 }
 public static void main( String[] args )
 {
 Hanoi( Integer.parseInt(args[0]), 1, 2, 3 );
 }
  }

Recursividad y Tabulación (Programación Dinámica)

A veces la simple recursividad no es eficiente.

Ejemplo: Números de Fibonacci.

Los números de Fibonacci se definen mediante la recurrencia

fn = fn-1+fn-2 (n>=2)
f0 = 0
f1 = 1

cuyos primeros valores son

n  0 1 2 3 4 5 6 7 8 9 10 11 . . .
fn 0 1 1 2 3 5 8 13 21 34 55 89 . . .

Se puede demostrar que los números de Fibonacci crecen exponencialmente, como una función O(øⁿ) donde ø=1.618....

El problema que se desea resolver es calcular f_n para un n dado.

La definición de la recurrencia conduce inmediatamente a una solución recursiva:

public static int F( int n )
 {
 if( n<= 1)
 return n;
 else
 return F(n-1)+F(n-2);
 }

Lamentablemente, este método resulta muy ineficiente. En efecto, si llamamos T(n) al número de operaciones de suma ejecutadas para calcular f_n, tenemos que

T(0) = 0
T(1) = 0
T(n) = 1 + T(n-1) + T(n-2)

La siguiente tabla mustra los valores de T(n) para valores pequeños de n:

 n 0 1 2 3 4 5 6 7 8 9 10 ...
T(n) 0 0 1 2 4 7 12 20 33 54 88 ...

Ejercicio: Demostrar que T(n) = f_n+1-1.

Por lo tanto, el tiempo que demora el cálculo de F(n) crece exponencialmente con n, lo cual hace que este método sea inútil excepto para valores muy pequeños de n.

El origen de esta ineficiencia es que la recursividad calcula una y otra vez los mismos valores, porque no guarda memoria de haberlos calculado antes.

Una forma de evitarlo es utilizar un arreglo auxiliar fib[], para anotar los valores ya calculados. Un método general es inicializar los elementos de fib con algún valor especial "nulo". Al llamar a F(n), primero se consulta el valor de fib[n]. Si éste no es "nulo", se retorna el valor almacenado en el arreglo. En caso contrario, se hace el cálculo recursivo y luego se anota en fib[n] el resultado, antes de retornarlo. De esta manera, se asegura que cada valor será calculado recursivamente sólo una vez.

En casos particulares, es posible organizar el cálculo de los valores de modo de poder ir llenando el arreglo en un orden tal que, al llegar a fib[n], ya está garantizado que los valores que se necesitan (fib[n-1] y fib[n-2]) ya hayan sido llenados previamente. En este caso, esto es muy sencillo, y se logra simplemente llenando el arreglo en orden ascendente de subíndices:

fib[0] = 0;
fib[1] = 1;
for( j=2; j<=n; ++j )
 fib[j] = fib[j-1]+fib[j-2];

El tiempo total que esto demora es O(n).

Esta idea se llama programación dinámica cuando se la utiliza para resolver problemas de optimización, y veremos algunas aplicaciones importantes de ella a lo largo del curso.

¿Es posible calcular f_n más rápido que O(n)? Si bien podría parecer que para calcular f_n sería necesario haber calculado todos los valores anteriores, esto no es cierto, y existe un método mucho más eficiente.

Tenemos

fn = fn-1+fn-2
f0 = 0
f1 = 1

Esta es una ecuación de recurrencia de segundo orden, porque f_n depende de los dos valores inmediatamente anteriores. Definamos una función auxiliar

gn = fn-1

Con esto, podemos re-escribir la ecuación para f_n como un sistema de dos ecuaciones de primer orden:

fn = fn-1+gn-1
gn = fn-1
f1 = 1
g1 = 0

Lo anterior se puede escribir como la ecuación vectorial

 
fn = A*fn-1
 

donde

fn = [ fn ] A = [ 1 1 ]
  [ gn ] [ 1 0 ]

con la condición inicial

f1 = [ 1 ]
  [ 0 ]

La solución de esta ecuación es

 
fn = An-1*f1
 

lo cual puede calcularse en tiempo O(log n) usando el método rápido de elevación a potencia visto anteriormente.

Backtraking (resolver por prueba y error)

Problema: se tiene una matriz de caracteres de dimensiones M+1xN+1 que representa un laberinto. En los elementos donde hay un caracter ‘*’ significa que hay una pared y no se puede pasar por esa posición y por donde hay un espacio ‘ ‘ se puede pasar. Un ejemplo sería:

* * * * * * * * *

* * * *

* * * *

* * * *

* * * * * *

* * *

* * * *

* * * * * * * * *

Se le pide escribir un método public static boolean salida(char[][] x, int i, int j, int M, int N) que retorne true si a desde la posición i,j se puede encontrar una salida.

Recursivamente esto se puede programar de la siguiente manera probando todos los caminos posibles:

1- si en la posición donde estoy (i,j) hay un ‘*’ no hay salida y retorno false.

2- si estoy en una posición (i,N) o (M,j) y hay un ‘ ‘ entonces estoy fuera y retorno true.

3- si estoy en posición (i,j) y hay un espacio, pruebo recursivamente si hay salida por alguna de las 4 vecinas (i+1,j), (i-1,j), (i,j+1), (i,j-1).

si alguna de las llamadas retorna true, yo retorno true (suponemos que no se puede mover en diagonal). Si todas retornan false, retorno false.

if (x[i][j] == ‘*’) return false;

if (i == M || i == N) return true; //aqui ya no puede ser ‘*’

if (salida(x, i+1, j, M, N) return true;

if (salida(x, i-1, j ,M, N) return true;

if (salida(x, i, j+1, M, N) return true;

if (salida(x, i, j-1, M, N) return true;

return false;

Esta solución tiene el problema que puede generar llamadas infinitas. Por ejemplo, si llamamos a salida(x, a, b, M,N) y esá vacía pero no es salida, esta llamará a salida(x,a+1,b,M,N). Si la celda (a+1,b) está vacía y no es salida, llamará a salida(x, a+1-1,b,M,N), generandose así un ciclo infinito. Para evitar esto podemos ir “marcando” (por ejemplo, con una x) los lugares por donde hemos pasado para no pasar de nuevo por ahí:

if (x[i][j] == ‘*’ || x[i][j] == ‘+’) return false;

if (i == M || i == N) return true; //aqui ya no puede ser ‘*’

x[i][j] == ‘x’

if (salida(x, i+1, j, M, N) return true;

if (salida(x, i-1, j ,M, N) return true;

if (salida(x, i, j+1, M, N) return true;

if (salida(x, i, j-1, M, N) return true;

return false;

Y ahora, ¿ como podemos “rescatar” el camino? Podemos retornar un string que contenga la secuencia de (i,j) por donde hay que pasar para llegar a la salida. Para eso debemos modificar el encabezado:

public static String sailda(char[][] x, int i, int j, int M, int N) {

if (x[i][j] == ‘*’ || x[i][j] == ‘+’) return null;

if (i == M || i == N) return “(“+i+”,”+j+”)”; //aqui ya no puede ser ‘*’

x[i][j] == ‘x’

String camino = salida(x, i+1, j, M, N)

if (camino != null)

return “(“+i+”,”+j+”)”+camino; //ponemos el i,j donde estamos al camino

camino = salida(x, i-1, j ,M, N)

if (camino != null)

return “(“+i+”,”+j+”)”+camino;

camino = salida(x, i, j+1, M, N);

if (camino != null)

return “(“+i+”,”+j+”)”+camino;

camino = salida(x, i, j-1, M, N);

if (camino != null)

return “(“+i+”,”+j+”)”+camino;

return null;

}

Finalmente, queremos saber cuánto mide el camino (de existir) entre la celda i,j y la salida más próxima. Para esto tenemos que probar todas las posibilidades y nos quedamos con la mejor (más corta):

public static int sailda(char[][] x, int i, int j, int M, int N) {

if (x[i][j] == ‘*’ || x[i][j] == ‘+’) return -1;

if (i == M || i == N) return 0; //aqui ya no puede ser ‘*’

int mascorto = M*N+1;

x[i][j] == ‘x’

int camino = salida(x, i+1, j, M, N)

if (camino != -1 && camino < mascorto)

mascorto = camino;

camino = salida(x, i-1, j ,M, N)

if (camino != -1 && camino < mascorto)

mascorto = camino

camino = salida(x, i, j+1, M, N);

if (camino != -1 && camino < mascorto)

mascorto = camino

camino = salida(x, i, j-1, M, N);

if (camino != -1 && camino < mascorto)

mascorto = camino

if mascorto = M*N+1 return -1 else return mascorto +1;

x[i][j] = ‘ ‘; //Desmarcar !!!

}

El problema de las 8 reinas: como poner 8 reinas en un tablero de ajedrez sin que se coman entre ellas:

reducimos a el problema a poner la reina en la i-esima fila.

public static boolean reinas(char[][] x, int i) {

//probar en la fila i

if (i = 8) {

imprimir_tablero(x);

return true;

}

for (int k = 0; k < 8; k+)

if (x[i][k] == ' ' && noLaComen(x,i,j)){

x[i][k] = ‘*’;

if(reinas(x,i+1))

return true;

x[i][k] = ‘ ‘;

}

return false;

}

Hagamos una función que me ayuda a evaluar qué tan buena es una jugada en el gato. Esto suponiendo que tanto mi contrincante como yo vamos a seguir escogiendo la mejor jugada posible en cada etapa.

//retorno 1 si gano con la jugada x,y, 0 si empato, -1 si pierdo

//suponiendo que el contrincante hace su mejor jugada

int gato(char[][] t, int x, int y, char z) {

t[x][y] = z;

//si gano retorno 1

if (gano(t, z))

return 1;

if (empate(t,x,y,z))

return 0;

char contrincante = 'O';

if (z == 'O')

contrincante = 'X';

int mejorCont = -1;

for (int i = 0; i <= 2; i++)

for (int j = 0; j <= 2; j++)

if (t[i][j] == ' ') {

int c = gana(t,i,j,contrincante);

if (c > mejorCont)

mejorCont = c;

}

return -mejorCont:

}

boolean gano(char[][] t, char z) {

boolean gane = false;

if (t[0][0] == z && t[0][1] == z && t[0][2] == z)

gane = true;

if (t[1][0] == z && t[1][1] == z && t[1][2] == z)

gane = true;

if (t[2][0] == z && t[2][1] == z && t[2][2] == z)

gane = true;

if (t[0][0] == z && t[0][1] == z && t[0][2] == z)

gane = true;

if (t[1][0] == z && t[1][1] == z && t[1][2] == z)

gane = true;

if (t[1][1] == z && t[1][2] == z && t[1][3] == z)

gane = true;

if (t[2][0] == z && t[2][1] == z && t[2][2] == z)

gane = true;

if (t[0][0] == z && t[1][1] == z && t[2][2] == z)

gane = true;

if (t[2][0] == z && t[1][1] == z && t[0][2] == z)

gane = true;

return gane;

}

boolean empate(char[][] t) {

//se empata cuando el tamblero esta lleno

for (int i = 0; i <= 2; i++)

for (int j = 0; j <= 2; j++)

if (t[i][j] != ' ')

return false;

return true;

}