Arreglos - Recorridos

Arreglos: Recorridos

Los arreglos, no son otra cosa mas que matrices dentro de los lenguajes de programación. Se utilizan para almacenar, organizar y manipular grandes cantidades de información, por grandes nos referimos a cantidades para las cuales no resulta muy conveniente o práctico utilizar variables separadas.

Una de las operaciones más importantes en los arreglos y que puede llegar a resultar algo confusa, son los recorridos. Antes de entrar a hablar sobre recorridos, recordemos un poco sobre los arreglos. 

Los arreglos, al igual que las matrices, son estructuras que contienen información en cada "casilla" o posición del arreglo. Para hacer referencia a una "casilla" o posición especifica del arreglo, se hacen uso de los índices, que sirven para identificar la fila y columna a la que nos estamos refiriendo en caso de los arreglos bidimensionales, en el caso de los arreglos unidimensionales se necesita un sólo numero para hacer referencia a algún elemento del arreglo. 

Como podemos observar, en C# es muy sencillo hacer referencia a una celda específica del arreglo. Ahora bien, ya que vimos como se hace eso, podemos hablar de recorridos. El mas común y sencillo se basa en dos estructuras de iteración, como puede ser el for, while o do-while, en este caso usaremos el for. Se dice que es el recorrido mas común porque es sencillo, empieza en la posición [0,0] del arreglo, recorre toda la primera fila hasta quedar en la posición final [5,0], después repite la operación pero ahora comenzando en la posición [0,1] para terminar en la posición [5,1]; se repite el mismo procedimiento para las otras 4 filas. 

El algoritmo para este procedimiento es bastante sencillo, apenas unas cuantas lineas;

Para i = 0 hasta i = n - 1 hacer

   Para j = 0 hasta j = n - 1 hacer

       Escribir "["+j+","+i+"]"

   Fin Para

Fin Para

Donde n es la dimensión del arreglo, por ejemplo para un arreglo de 5x5, n = 5.

Y esto en código de C# es aún más sencillo. Por ejemplo, para llenar un arreglo con números en orden, es decir, 1,2,3,4... n*n, podría implementarse el siguiente código.

public int[,] numOrden(int[,] arreglo, int n)

{

int c = 1;

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

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

   {

      arreglo[ j , i ] = c;

      c = c + 1;

   } 

return arreglo;

}

Imaginando que n = 3, este método lo que hará, en un principio será situarse en la posición [j,i] del arreglo, en un inicio tanto i como j valen 0, por lo tanto estariamos situados en [0,0] y es ahí donde se almacena el valor de c (1 al principio). Después, el for mas interno hace la comparación j < 3, como j vale 0, el ciclo se repite, la próxima vez que se ejecute la comparación, j valdrá 1, la siguiente 2 y por último 3 < 3, como eso es falso, entonces el for interno no se ejecuta de nuevo, ahora el for externo es el que entra en ejecución y hace la comparación i < 3, como i  en un principio vale 0, todo el proceso se repite nuevamente. 

En otras palabras, el for interno se ejecuta 3 veces por sí mismo, y el for externo hace que éste se ejecute 3 veces, por lo tanto las repeticiones del for interno por las repeticiones del for externo nos dan un total de 9 repeticiones, es decir, habrá visitado cada lugar del arreglo.

Éste mismo código puede utilizarse para recorrer el arreglo columna por columna en vez de fila por fila, solamente tendria que cambiar arreglo[j,i] por arreglo[i,j]. De la misma forma podría usarse para recorrer el arreglo desde el final ( [n-1,n-1] ) hasta el principio, todo depende de las necesidades del programador así como de su imaginación. 

Recorrido en espiral

Arreglo 3x3

Uno de los sencillos recorridos que se pueden hacer sobre un arreglo, es el recorrido de espiral. A simple vista, y sobre todo en arreglos grandes, puede parecer un procedimiento difícil de programar, pero nada mas lejos de la realidad, solo hay que encontrar patrones.

Primero que nada, si nos detenemos a observar con atención el recorrido, podemos darnos cuenta que independientemente de las dimensiones del arreglo, siempre y cuando sea cuadrado, los primeros 3 movimientos (derecha, abajo, izquierda) son de la misma longitud, es decir, si en el arreglo de la imagen estamos posicionados en [0,0] para llegar al final de la fila hay que movernos 2 unidades ( [0,0] → [2,0] ), desde el final de la fila, hasta el final de la columna también son 2 unidades ( [2,0] → [2,2] ), desde el final de la fila hasta el principio son otras 2 unidades ( [2,2] → [0,2] ) hasta ahí, esos 3 movimientos son iguales. Como decíamos al principio, esos 3 movimientos son iguales en todos los arreglos, en términos generales, si el arreglo es de 3x3 entonces n = 3, y podemos decir que los 3 primeros movimientos son de n - 1 unidades.

Habiendo definido esto, los desplazamientos a partir de aquí están dados por un patrón. El siguiente movimiento es hacia arriba, pero esta vez el movimiento no será de n - 1 unidades, a partir de aquí el movimiento es de n - 2 unidades, es decir de 3 - 2 = 1 unidad hacia arriba ( [0,2] → [0,1] ), después 1 unidad hacia la derecha ( [0,1] → [1,1] ), en este punto  el desplazamiento es de n - 3 = 3 - 3 = 0 unidades, entonces el proceso termina cuando el desplazamiento llega a ser de 0 unidades. 

Si observamos con atención, existe un patrón que describe el movimiento en espiral dentro del arreglo. A continuación el algoritmo.

Teniendo un arreglo de 3x3 por ejemplo, donde;

n  = 3; 
mov = n - 1;



col = 0
fil = 0
Para i = 0 hasta i = mov hacer
   Escribir arreglo[col,fil]
   col = col + 1
Fin para
Para i = 0 hasta i = mov hacer
   Escribir arreglo[col,fil]
   fil = fil + 1
Fin para
Para i = 0 hasta i = mov hacer
   Escribir arreglo[col,fil]
   col = col - 1
Fin para
mov = mov - 1
Mientras( mov >= 1) hacer   //Comienza el patrón
   Para i = 0 hasta i = mov hacer
      Escribir arreglo[col,fil]
      fil = fil - 1
   Fin para
   Para i = 0 hasta i = mov hacer
      Escribir arreglo[col,fil]
      col = col + 1
   Fin para
   mov = mov - 1
   Para i = 0 hasta i = mov hacer
   Escribir arreglo[col,fil]
      col = col + 1
      Fin para
   Para i = 0 hasta i = mov hacer
      Escribir arreglo[col,fil]
      fil = fil + 1
   Fin para
   mov = mov -1
Fin Mientras

Este algoritmo esta hecho para funcionar con cualquier arreglo cuadrado sin importar sus dimensiones y utiliza estructuras básicas de iteración. No es ni por mucho el único algoritmo ni el más eficiente, pero sirve para dar una idea de cómo se puede hacer este recorrido en un arreglo cuadrado. A continuación el código en C#.

public int[,] Espiral(int[,] a, int n)

{

int c = 1;
int cx = 0;
int cy = 0;
int lim = n - 1;
for(int i = 0; i< lim; i++)
{
  a[cx,cy] = c;
  cx++; //mueve hacia la derecha
  c++;
}
for(int i = 0; i < lim; i++)
{
  a[cx,cy] = c;
  cy++; //mueve hacia abajo
  c++;
}
for(int i = 0; i < lim; i++)
{
   a[cx,cy] = c;
   cx--; //mueve hacia la izquierda
   c++;
}
lim--;
while(lim>=1)
{
   if(lim>=1)
       for(int i = 0; i<lim; i++)
       {
           a[cx,cy] = c;
           cy--; //hacia arriba
           c++;
       }
    if(lim>=1)
        for(int i = 0; i<lim; i++)
        {
            a[cx,cy] = c;
            cx++; //hacia la derecha
            c++;
        }
     lim--;
     if(lim>=1)
         for(int i = 0; i<lim; i++)
         {
            a[cx,cy] = c;
            cy++; //hacia abajo
            c++;
         }
     if(lim>=1)
         for(int i = 0; i<lim; i++)
         {
             a[cx,cy] = c;
             cx--; //hacia la izquierda
             c++;
          }
      lim--;
}
return a

}

Claramente, este código contiene algunas validaciones que el algoritmo original no tiene, aunque dichas validaciones aparecen por si mismas al estar implementando el algoritmo en un lenguaje de programación. 

El recorrido análogo del espiral, el espiral desde el centro, funciona de una manera muy similar, comienza del centro, hace un movimiento en alguna dirección, hace otro movimiento, aumenta la cantidad de desplazamientos, hace un movimiento en cierta dirección, hace otro movimiento, nuevamente aumenta en 1 la cantidad de desplazamientos y el ciclo se repite hasta llegar al principio del arreglo. 

Próximamente se incluirán algunos otros recorridos típicos de los arreglos de cuadrados. 

Recursividad - Triángulo de Sierpinski

Triángulo de Sierpinski 

La recursividad está presente en todo, incluso en el mundo real y tangible donde vivimos. Por ejemplo los átomos, los átomos de un mismo elemento son idénticos, y estos a su vez, están presentes miles de millones de veces para formar algún material, podemos decir entonces que son estructuras que se repiten muchas veces para formar una estructura mas grande. 

Otros ejemplos son por ejemplo las hojas de los árboles o los copos de nieve, son estructuras que se repiten varias veces a distintas escalas. A estos patrones se les conoce como fractales.

Existe un fractal muy curioso llamado triángulo de Sierpinski, el cual presenta una característica muy interesante, es una figura que a medida que más se repiten los patrones, su área tiende a 0.

Otro punto importante de éste fractal, y que como programadores nos concierne un poco más que su área, es que su construcción puede llevarse a cabo mediante un proceso recursivo. 

Antes de entrar al aspecto programático, haciendo un pequeño análisis de este fractal, podemos darnos cuenta que su construcción es bastante sencilla; partiendo del triangulo  equilátero inicial, basta con unir con una linea los 3 puntos medios de cada lado del triangulo, de esa manera el triangulo queda dividido en 4 triángulos mas pequeños de los cuales 3, son similares al triangulo inicial. Si aplicamos el mismo procedimiento a cada uno de los 3 triángulos que obtuvimos en el paso anterior,  tendremos ahora 13 triángulos de los cuales 9 son similares al triangulo inicial, y así sucesivamente.

Aquí es donde entramos nosotros como programadores a elaborar un algoritmo recursivo que nos permita construir este fractal.

Como se mencionaba, basta con tomar el triángulo equilátero inicial, determinar sus puntos medios, y en base a ellos dibujar los 3 triángulos mas pequeños, el proceso se repite en cada uno de los triángulos obtenidos las veces que se desee.

A partir de esa definición podemos construir el algoritmo y posteriormente el código en C# tomando como información de entrada las coordenadas de los vértices y una variable para determinar cuántas veces ha de repetirse el proceso. vert_1 es el vértice izquierdo, vert_2 el de arriba y vert_3 el derecho. p_medio1 es el punto medio de la izquierda, p_medio2 es el punto medio de abajo y p_medio3 el de la derecha.

Algoritmo:

fractal( vert_1, vert_2, vert_3, repe)                    

    Si( repe == 0 )                                       

       dibujar triangulo con las coordenadas              

    Sino                                                  

       calcular p_medio1                                  

       calcular p_medio2                                  

       calcular p_medio3                                  

       fractal(vert_1, p_medio1, p_medio2, repe - 1)      

       fractal(p_medio1, vert_2, p_medio3, repe - 1)      

       fractal(p_medio2, p_medio3, vert_3, repe - 1)      

En esas sencillas lineas se puede resumir la construcción de este particular fractal. Únicamente cabe destacar como se mencionaba en una entrada anterior, que la recursividad funciona en base a una pila de llamadas, y las llamadas empiezan a retornar valores hasta que se llega al caso base, es decir, aquel en el que no es necesario que el método vuelva a llamarse a si mismo. En este caso, dado un triángulo inicial, el método continuaría llamándose a si mismo las veces que sea necesario hasta llegar al caso en que repe es igual a 0, entonces es cuando empezaría a dibujar los triángulos, lógicamente los que corresponden a las últimas llamadas del método, es decir, los triángulos mas pequeños.

En palabras menos complicadas, el método lo único que hace es tomar un triángulo inicial, y dividirlo n veces, hasta el momento que lo tiene dividido las veces necesarias, es cuando comienza a dibujar. 

Ahora bien, pasemos a analizar el código en C#

 private void Triangulo(int x1, int y1, int x2, int y2, int x3, int y3, Graphics g,  int n)

 {

    if (n == 0)

    {

    SolidBrush b = new SolidBrush(Color.Teal);

    Point[] puntos = new Point[3];

    puntos[0] = new Point(x1, y1);

    puntos[1] = new Point(x2, y2);

    puntos[2] = new Point(x3, y3);

    g.FillPolygon(b, puntos);

    }

    else

    {

    int pm1x = (x1 + x2) / 2;

    int pm1y = (y1 + y2) / 2;

    int pm2x = (x1 + x3) / 2;

    int pm2y = (y1 + y3) / 2;

    int pm3x = (x2 + x3) / 2;

    int pm3y = (y2 + y3) / 2;

    Triangulo(x1, y1, pm1x, pm1y, pm2x, pm2y,g,n - 1);

    Triangulo(pm1x, pm1y, x2, y2, pm3x, pm3y, g, n - 1);

    Triangulo(pm2x, pm2y, pm3x, pm3y, x3, y3, g ,n - 1);

    }

 }     

Adjunto el proyecto Sierpinski en Visual C# 2010 
Descargar

Recursividad

Recursividad :B

Introducción

"Para entender la recursividad, primero hay que entender la recursividad"

Para aquellos que están metidos en esto de la programación, en algún momento tendrán que toparse con el concepto de la recursividad. Para muchos de nosotros no es algo sencillo de comprender y mucho menos sencillo de aplicar. Formalmente se dice que es un procedimiento o función que está definido en términos de sí mismo. Esto quiere decir que, hablando en términos de programación orientada a objetos, es un método que para poder ejecutarse, puede llegar a requerir llamarse a si mismo en varias ocasiones.

La recursividad aplica la conocida filosofía de divide y vencerás, es decir, toma un problema grande y lo va dividiendo en problemas mas pequeños que sean mas sencillos de resolver. Todo esto quedara un poco mas claro con un pequeño ejemplo.

Todos conocemos lo que es el factorial de un numero, y para los que no, no es otra cosa mas que la multiplicación sucesiva de un numero, por cada uno de sus antecesores. Por ejemplo si tenemos 5! = 5x4x3x2x1 = 120. Aunque no se aprecie claramente, en esa operación se hace uso de la recursividad :p

Para calcular el factorial de un numero, hay dos reglas sencillas, el factorial de 1 y de 0, en ambos casos es 1, para todos los demás números, hay que multiplicarse por cada antecesor, entonces podemos hacer un pequeño ejemplo;

"Fulanito quería saber cuanto era 4!, entonces le marcó a su hermano Sutanito para preguntarle, él le contesto que era fácil, 4! era 4 x 3!, pero se quedo con la duda y tuvo que marcarle a Manganito para preguntar cuanto era 3!, él le contesto que 3! era 3 x 2!, pero él también se quedo con la duda de cuanto era 2! asi que tuvo que preguntarle a Perenganito y él le contesto que 2! era 2 x 1!, pero él no sabia cuanto era 1!, así que busco en Gúgl, y se dio cuenta que 1! era 1,  entonces pudo contestarle a Manganito y decirle que 2! era 2. Después como Manganito ya sabía que 2! era 2, pudo contestarle a Sutanito que 3x2! era 6. Luego como Sutanito ya sabía que 3! era 6, pudo contestarle a Fulanito que 4x3! era 24, y por último, fue como Fulanito pudo saber que 4! era 24."

Intentado descifrar la enredosa llamada telefónica, podemos observar algo como lo siguiente

A grandes rasgos es así como trabaja la recursividad, toma un problema grande (el 4! por ejemplo), y lo va dividiendo en problemas más pequeños y lógicamente mas sencillos de resolver (las llamadas entre fulanitos) hasta que llega a un punto en que no se necesitan hacer mas divisiones (el 1!) y se pueden empezar a retornar los datos (las llamadas devueltas) para resolver el problema inicial (el dichoso 4!).

El ejemplo del factorial es un clásico para tratar de explicar como trabaja la recursividad, aunque es un ejemplo muy básico a comparación de los problemas donde realmente tiene aplicaciones la recursividad, sirve para dar un panorama general, como en todo, el dominio de esta técnica de programación reside en la práctica :p

El código en C# del método que sirve para calcular factoriales sería el siguiente:

public long fact(int n)

{

   if(n == 1 || n == 0)

      return 1;

   else

      return n * fact(n - 1);

}

Más a fondo

A un nivel un poco más profundo, se puede decir que las estructuras de datos y la recursividad están íntimamente ligadas. Por un lado, la recursividad es posible gracias a una estructura llamada Pila o Stack, que tiene sus propias características en las que no vamos a profundizar de momento, solamente como dato general la pila es una estructura de tipo lifo o último en entrar, primero en salir, por ejemplo; en una pila de platos, para tomar el plato que se encuentra hasta abajo primero hay que comenzar extrayendo el plato que se encuentra en la cima, después el que le sigue y así sucesivamente.

Con eso en mente, podemos darnos cuenta que en la imagen anterior, la primera llamada (Fulanito preguntando cuanto era 4!) fue la última en ser contestada, y a su vez, la última llamada (Perenganito investigando cuanto era 1!) fue la primera en devolver información sin dudas. Entonces a nivel estructura de datos, podemos explicar el orden de llamadas del código anterior utilizando una pila.

Como se puede apreciar, las llamadas se van almacenando en una pila dependiendo del orden en que se hacen. Otro punto remarcable es el hecho de que las últimas llamadas en realizarse, son las primeras en ser desapiladas, y las primeras llamadas en la pila son las últimas en ser desapiladas. Tal es el caso de la llamada inicial fact(4), es la última en devolver una respuesta.