Nociones básicas de programación
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.
Los programas representan la información que manejan mediante valores llamados "constantes", y dichos valores se almacenan en "variables".
Variables
int k; // entero
float x; // real
double prom; // real de doble precisión
boolean condicion; // verdadero o falso
char c; // un carácter
String nombre; // secuencia de caracteres
Nótese que la secuencia "//" indica el comienzo de un comentario, el cual se extiende hasta el final de la línea.
Constantes
3 // int
4.50 // float
1e-6 // float
'a' // char
"hola" // String
Instrucciones Elementales
Asignación
Esta es la instrucción más simple, que permite modificar el valor de una variable:
a = E; // asigna a la variable 'a' el valor de la expresión 'E'
Ejemplos:
k = 0;
k = k+1;
k += 1;
++k;
k++;
Las tres últimas son abreviaturas. La notación "+=" permite evitar repetir el lado izquierdo de la asignación. Las dos últimas incrementan el valor de la variable en 1, pero difieren respecto del valor retornado. En el primer caso (preincremento) se incrementa primero y luego se retorna el valor resultante. El el segundo caso (postincremento) se incrementa después, y se retorna el valor previo de la variable.
Salida
System.out.println("¡Hola!");
Estas instrucciones se forman agrupando a otras instrucciones, ya sean elementales o compuestas, usando las reglas de secuencia, alternación (if) e iteración (while).
Secuencia de instrucciones
Un grupo de instrucciones escritas una a continuación de la otra se ejecutan en ese mismo orden:
instrucción1;
instrucción2;
. . .
También es posible agrupar las instrucciones entre llaves para que sean equivalentes a una sola instrucción:
{
instrucción1;
instrucción2;
. . .
}
Ejemplo:
// Intercambiar dos valores a y b
{
int aux = a;
a = b;
b = aux;
}
Instrucciones condicionales
Forma 1:
if( condición )
instrucción1;
else
instrucción2;
Forma 2:
if( condición )
instrucción;
Nota: No existe el "endif". Si lo que se desea ejecutar en cada caso es más de una instrucción, hay que escribirlas encerradas entre llaves.
Ejemplo:
// m = max(a,b)
if( a>b )
m = a;
else
m = b;
Ejemplo:
// a = abs(a)
if( a<0 )
a = -a; // se omite el "else" si es vacío
Ejemplo:
// Ordenar a, b (borrador)
if( a>b )
intercambiar a, b;
La línea destacada no es una instrucción real del lenguaje, es sólo una forma de dejar pendiente esa parte del programa. Más adelante se podrá "refinar" esa seudo-instrucción definiendo:
intercambiar a, b =>
{
int aux = a;
a = b;
b = aux;
}
Si se efectúa la sustitución del texto refinado en lugar del que se había escrito originalmente, resulta un texto de programa refinado que cumple con las reglas del lenguaje. Para ayudar a la auto-documentación del programa, se puede conservar la seudo-instrucción como comentario:
// Ordenar a, b
if( a>b )
{ // intercambiar a, b
int aux = a;
a = b;
b = aux;
}
Ejemplo: Encontrar el máximo entre un conjunto de variables
// m = max(a,b,c)
// Solución 1 (borrador)
if( a>b )
m = max(a,c);
else
m = max(b,c);
Realizando las sustituciones respectivas, se obtiene la siguiente versión "refinada":
// m = max(a,b,c)
// Solución 1 (versión refinada)
if( a>b )
{
if( a>c )
m = a;
else
m = c;
}
else
{
if( b>c )
m = b;
else
m = c;
}
Nota: En este caso, las llaves no son realmente necesarias, pero pueden utiizarse si ayudan a la claridad del programa.
Este enfoque de solución tiene la desventaja que es difícil de generalizar. Por ejemplo, el programa que encuentra el máximo de cuatro variables tiene aproximadamente el doble de líneas que éste, y por lo tanto el tamaño del programa va creciendo exponencialmente. Además no hay forma de escribir un programa para un número de variables que no sea conocido a priori.
// m = max(a,b,c)
// Solución 2 (borrador)
m = a;
m = max(m,b);
m = max(m,c);
Sustituyendo las seudo-instrucciones, resulta:
// m = max(a,b,c)
// Solución 2 (versión refinada)
m = a;
if( b>m )
m = b;
if( c>m )
m = c;
Con cada instrucción que se ejecuta, el estado del proceso cambia. Para entender lo que está sucediendo en el programa, puede resultar útil intercalar comentarios que describan lo que sabemos que se cumple después de cada instrucción:
// m = max(a,b,c)
// Solución 2 (versión refinada y con afirmaciones)
m = a;
// m == max(a)
if( b>m )
m = b;
// m == max(a,b)
if( c>m )
m = c;
// m == max(a,b,c)
Ese tipo de comentarios se llaman afirmaciones (assertions), y en casos más complejos son fundamentales para entender lo que está sucediendo en un proceso.
La generalización para encontrar el máximo de cuatro o más variables es directa, y en cada caso requiere sólo agregar dos líneas al programa. Más adelante se verá una versión para un número variable de datos.
Instrucción iterativa
La forma general es:
while( condición )
instrucción;
La instrucción se ejecuta en forma reiterada mientras la condición sea verdadera.
Cada vez que se intenta iniciar una nueva iteración (incluyendo la primera vez que ello ocurre) el programa se encuentra en un estado I llamado el invariante del ciclo.
En general, al escribir un ciclo, se debe establecer la validez inicial del invariante, a través de una inicialización. El objetivo del ciclo es llegar a un estado final F. En cada iteración se debe, además, preservar la validez del invariante.
Ejemplo:
Considere el problema de encontrar el máximo de un número variable de datos, almacenados en un arreglo a[1], …, a[n]. Para verlo en forma iterativa, imagine un proceso en que los datos se van examinando uno a uno, comparándolos con el máximo encontrado hasta el momento. De esta manera, si en un instante dado ya se han examinado los datos hasta a[k], entonces se conoce el máximo hasta esa variable.
// m = max(a[1],…,a[n]);
k = 1;
m = a[1];
// m == max(a[1])
// De esta manera trivial se incializa el siguiente invariante:
// Invariante: k<=n && m == max(a[1],…,a[k])
while( km )
m = a[k];
// k<=n && m == max(a[1],…,a[k])
}
// m = max(a[1],…,a[n])
Esta última afirmación se deduce del hecho que al terminar el ciclo se sabe que el invariante sigue siendo verdadero, pero la condición del ciclo es falsa. En estricto rigor, la afirmación que podríamos hacer ahí es
// k>=n && k<=n && m == max(a[1],,,a[k])
de la cual se deduce la señalada al final del programa.
¿Cómo escribir un ciclo?
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".
Escribir la inicialización, la cual debe asegurar que el invariante se cumpla antes de empezar a iterar.
Encontrar la condición de término. Esto se obtiene de comparar "qué le falta" al invariante para ser igual al estado final.
Escribir el cuerpo del ciclo, el cual debe:
conseguir que el proceso avance, de modo que termine algún día,
y 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.
Ejemplos de programas iterativos
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 n2, lo que se denotará O(n2).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(n2), 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(n2).
Cálculo de xn
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
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
Reordenar los elementos de a[0], …, a[n] dejando a la izquierda los <0 y a la derecha los >=0.
Solución 1:
Invariante:
// Version 1 i = 0; j = n; while( i<j ) { if( a[i]<0 ) ++i; else if( a[j]>=0 ) –j; else { a[i] <-> a[j]; ++i; –j; } } |
| // Version 2 i = 0; j = n; while( i<j ) { while( i<j && a[i]<0 ) ++i; while( i<j && a[j]>=0 ) –j; if( i<j ) { a[i] <-> a[j]; ++i; –j; } } | |||||||||
Solución 2:
Invariante:
i = 0;
for( j=0; j<=n; ++j )
if( a[j]<0 )
{
a[i] <-> a[j];
++i;
}
Al programar en forma recursiva, buscamos dentro de un problema otro subproblema que posea su misma estructura.
Ejemplo: Calcular xn.
// 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 );
}
}
}
Este es un método de diseño de algoritmos que se basa en subdividir el problema en sub-problemas, resolverlos recursivamente, y luego combinar las soluciones de los sub-problemas para construir la solución del problema original.
Ejemplo: Multiplicación de Polinomios.
Supongamos que tenemos dos polinomios con n coeficientes, o sea, de grado n-1:
A(x) = a0+a1*x+ … +an-1*xn-1
B(x) = b0+b1*x+ … +bn-1*xn-1
representados por arreglos a[0], …, a[n-1] y b[0], …, b[n-1]. Queremos calcular los coeficientes del polinomio C(x) tal que C(x) = A(x)*B(x).
Un algoritmo simple para calcular esto es:
// Multiplicación de polinomios
for( k=0; k<=2*n-2; ++k )
c[k] = 0;
for( i=0; i
for( j=0; j
c[i+j] += a[i]*b[j];
Evidentemente, este algoritmo requiere tiempo O(n2). ¿Se puede hacer más rápido?
Supongamos que n es par, y dividamos los polinomios en dos partes. Por ejemplo, si
A(x) = 2 + 3*x – 6*x2 + x3
entonces se puede reescribir como
A(x) = (2+3*x) + (-6+x)*x2
y en general
A(x) = A'(x) + A"(x) * xn/2
B(x) = B'(x) + B"(x) * xn/2
Entonces
C = (A' + A"*xn/2) * (B' + B"*xn/2)
= A'*B' + (A'*B" + A"*B') * xn/2 + A"*B" * xn
Esto se puede implementar con 4 multiplicaciones recursivas, cada una involucrando polinomios de la mitad del tamaño que el polinomio original. Si llamamos T(n) al número total de operaciones, éste obedece la ecuación de recurrencia
T(n) = 4*T(n/2) + K*n
donde K es alguna constante cuyo valor exacto no es importante.
Teorema
Las ecuaciones de la forma
T(n) = p*T(n/q) + K*n
con tienen solución
T(n) = O(nlogq p) (p>q)
T(n) = O(n) (p
T(n) = O(n log n) (p=q)
Por lo tanto la solución del problema planteado (p=4, q=2) es
T(n) = O(nlog2 4) = O(n2)
lo cual no mejora al algoritmo visto inicialmente.
Pero… hay una forma más eficiente de calcular C(x). Si calculamos:
D = (A'+A") * (B'+B")
E = A'*B'
F = A"*B"
entonces
C = E + (D-E-F)*xn/2 + F*xn
Lo cual utiliza sólo 3 multiplicaciones recursivas, en lugar de 4. Esto implica que
T(n) = O(nlog2 3) = O(n1.59)
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(øn) donde ø=1.618….
El problema que se desea resolver es calcular fn 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 fn, 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) = fn+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 fn más rápido que O(n)? Si bien podría parecer que para calcular fn 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 fn depende de los dos valores inmediatamente anteriores. Definamos una función auxiliar
gn = fn-1
Con esto, podemos re-escribir la ecuación para fn 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.
Conceptos de Programación Orientada al Objeto (OOP)
Un objeto combina datos y operaciones (métodos).
El principio básico es el de encapsulamiento (ocultamiento de información). Esto permite separar el "qué" (especificación funcional, pública) del "cómo" (implementación, privada).
Conceptos asociados a la programación orientada a objetos, para apoyar la reutilización de codigo:
Código genérico: la lógica de un algoritmo debe poder escribirse independientemente del tipo de los datos.
Herencia: permite extender la funcionalidad de un objeto.
Polimorfismo: permite que se seleccione automáticamente la operación apropiada según el tipo y número de los parámetros.
Clases
En Java un objeto es una instancia de una clase.
Ejemplo:
// Clase Entero, que permite leer y
// guardar un valor en una variable entera
public class Entero
{
// Datos privados
private int valor;
// Métodos públicos
public int leer()
{
return valor;
}
public void guardar( int x )
{
valor = x;
}
}
// Ejemplo de programa principal
public class Prueba
{
public static void main( String[] args )
{
Entero m = new Entero();
m.guardar( 5 );
System.out.println( "m=" + m.leer() );
}
}
Tipos de métodos Constructores
Permiten inicializar el objeto. Puede haber varios constructores con distinto número y tipos de parámetros.
Si no hay un constructor definido, los campos se inicializan automáticamente con valores nulos.
El constructor debe tener el mismo nombre que la clase.
Ejemplo: Clase para almacenar fechas:
public class Fecha
{
private int a;
private int m;
private int d;
// Constructor con parámetros
public Fecha( int aa, int mm, int dd )
{
a = aa;
m = mm;
d = dd;
}
// Constructor sin parámetros
public Fecha()
{
a = 2001;
m = 1;
d = 1;
}
}
Ejemplos de uso:
Fecha f1 = new Fecha();
Fecha f2 = new Fecha( 2001, 4, 11 );
"Mutators" y "accessors"
Las variables de una clase tipicamente son privadas. Para mirar su valor, o para modificarlo, hay que utilizar métodos ad hoc (como leer y guardar en el ejemplo de la clase Entero).
Esto es un mayor grado de burocracia, pero aisla a los usuarios de una clase de los detalles de implementación de ella, y evita que se vean afectados por eventuales cambios en dicha implementación.
toString
Al imprimir un objeto a usando println, automáticamente se invoca a
a.toString()
para convertirlo a una forma imprimible. Esto mismo ocurre cada vez que se utiliza a en un contexto de String.
En el ejemplo, si vamos a imprimir objetos de tipo Fecha, debemos proveer una implementación de toString dentro de esa clase:
public String toString()
{
return d + "/" + m + "/" + a;
}
equals
El método equals se utiliza para ver si dos objetos tienen el mismo valor. Se invoca
if( x.equals(y) )
y se declara como
public boolean equals( Object b )
El tipo Object usado aquí es un tipo de objeto "universal" del cual se derivan todos los otros. El siguiente ejemplo muestra una implementación de equals para la clase Fecha:
public boolean equals( Object b )
{
if( !(b instanceof Fecha) )
return false; // el otro objeto no era de tipo Fecha
Fecha f = (Fecha) b; // para verlo como una Fecha
return a==f.a && m==f.m && d==f.d;
}
this
La referencia this identifica al objeto actual. Permite desde dentro de la clase accesar los campos propios diciendo, por ejemplo, this.a. Esto en realidad es redundante, porque significa lo mismo que decir simplemente a, pero puede ser más claro en la lectura.
También permite comparar si este objeto es el mismo que otro (no sólo si tienen el mismo contenido, sino si ambas referencias apuntan al mismo objeto).
El otro uso de this es como constructor, para llamar a otro constructor de la misma clase. Por ejemplo, el constructor sin parámetros de la clase Fecha podría haber sido declarado como:
public Fecha()
{
this( 2001, 1, 1 );
}
Campos estáticos
Hay dos tipos de campos estáticos:
public final static double PI = 3.14159; // constante
private static int precioActual = 1300; // variable compartida
// por todos los objetos de esa clase
Métodos estáticos
Los métodos estáticos están asociados a una clase, no a objetos particulares dentro de ella.
Ejemplos:
Math.sin
Integer.parseInt
Los métodos estáticos no pueden hacer uso de la referencia this.
Packages
Las clases se pueden agrupar en "paquetes". Para esto, cada clase debe precederse de
package P;
class C
{
. . .
}
Cuando a una variable no se le pone public ni private, es visible sólo dentro del mismo package.
La clase C se denomina P.C, pero si antes decimos import P.C; o bien import P.*;, entonces podemos referirnos a la clase simplemente como C;
Herencia
Principio que permite reutilizar trabajo ya hecho. Se basa en la relación is-a.
Ejemplo:
Círculo is-a FiguraAuto is-a Vehículo
Las clases forman una jerarquía en base a la relación de herencia.
Otro tipo de relación distinta es has-a. Por ejemplo:
Auto has-a Manubrio
Este tipo de relación se llama agregación y a menudo es más importante que la herencia.
Clase base:
La clase de la cual se derivan otras
Clase derivada:
Hereda todas las propiedades de la clase base. Luego puede agregar campos y métodos, o redefinir métodos.
Los cambios que se hagan en la clase derivada no afectan a la clase base.
Sintaxis:
public class Derivada extends Base
{
. . .
}
Los campos adicionales generalmente son privados.
Los métodos de la clase base que no se redefinen en la clase derivada se heredan sin cambio, excepto por el constructor.
Los métodos que se redefinen tienen prioridad.
Se pueden agregar nuevos métodos.
Los métodos públicos se pueden redefinir como privados.
Visibilidad
Los campos privados de la clase base no se ven desde las clases derivadas. Para que un campo de este tipo sea visible debe declararse como protected. Esta posibilidad debe usarse con mucho cuidado.
Constructores
Cada clase define su propio constructor, el cual lleva el mismo nombre que la clase.
Si no se define un constructor, se genera automáticamente un constructor sin parámetros que:
llama al constructor con cero parámetros de la clase base, para la parte heredada, y luego
inicializa con valores nulos los campos restantes.
Si se escribe un constructor, su primera instrucción puede ser una llamada a
super( … );
lo cual invoca al constructor de la clase base.
final
Si un método se declara como final, entonces no puede ser redefinido en las clases derivadas.
Análogamente, una clase declarada como final no puede ser extendida.
Métodos abstractos
Un método abstracto declara funcionalidad, pero no la implementa. Las clases derivadas deben proveer implementaciones para estos métodos.
Una clase abstracta es una clase que tiene al menos un método abstracto. No se puede crear objetos pertenecientes a una clase abstracta (no se puede ejecutar new).
Ejemplo:
abstract class Figura
{
private String nombre;
abstract public double area();
public Figura( String n )
{
nombre = n;
}
// Este constructor no puede ser invocado directamente,
// sólo lo usan las clases derivadas
final public double compArea( Figura b )
{
return area() – b.area();
}
| Página siguiente |