Manual del estudiante de Ingeniería en Sistemas de UTN/Diseño e Implementación de Estructuras de Datos/Guías prácticas/Recursividad

Ejercicio 1

El cálculo del máximo común divisor de dos números se puede realizar de forma recursiva mediante el algoritmo de Euclides. La implementación recursiva se basa en la siguiente propiedad:

$mcd(a,b)=mcd(b,amodb)$

con $a\geq b$, $b\neq 0$

Por ejemplo: $mcd(96,36)=mcd(36,24)=mcd(24,12)=mcd(12,0)$

Cuando b se hace cero, no es necesario continuar, ya que $mcd(a,0)=a$.

El siguiente programa permite calcular el mcd de dos números recursivamente.

public class Mcd
{
  public static int mcd(int a, int b)
  {
    return mcd(b, a%b);
  }

  public static void main(String args[])
  {
    int a= 96, b= 36;
    System.out.println("mcd("+a+", "+b+")= "+mcd(a,b));
  }
}

El programa no funciona. Corregirlo para que funcione correctamente. Solución

Ejercicio 2

Analizar la traza de ejecución del programa. Para ello, hacer que al inicio del método mcd se imprima en pantalla un mensaje que indique el inicio del método y el valor de los parámetros, y lo mismo para cuando finalice el método, justo antes de retornar, y después de haber realizado el cálculo del valor a retornar. Predecir qué secuencia de mensajes aparecerá por pantalla. Solución

Ejercicio 3

Se trata de determinar cuantos cuadrados de un patrón dado rodean a determinado punto. El patrón es recursivo, se genera a partir de un número $k$, que será el lado del cuadrado, que a su vez tendrá en cada vértice un cuadrado con lado ${\frac {k}{2}}$. El mínimo valor de $k$ es 2.

1. Diseñar una clase patrón que responda a un método int rodean(int x, int y), que resuelva el problema.
2. Codificar el método recursivo.
3. Calcular la complejidad del método.
4. Transformar el método recursivo en iterativo.
5. Tratar de mejorar la complejidad acotando el problema.

Solución

Ejercicio 4

1. Modelar un clase que implemente un método:

public Vector generate(String source);

que a partir de la cadena de origen “source”, genere todas las palabras que sean combinaciones de sus letras. Por ejemplo, si la cadena de origen fuera “Chau”, el Vector debería llenarse con las siguientes cadenas: Chau, Chua, Cahu, Cauh, Cuha, Cuah, hCau, hCua, haCu, hauC, huCa, huaC, aChu, aCuh, ahCu, ahuC, auCh, auhC, uCha, uCah, uhCa, uhaC, uaCh, uahC.

2. Calcule la complejidad del algoritmo desarrollado.

3. Plantee también el problema de transformar a iterativo el método “generate”.

Solución

Ejercicio 5

1. Modele la clase Imagen, que deberá representar los puntos de color de un dibujo –píxeles. Cada carácter correspondiente a una letra minúscula del alfabeto, representará cada color posible, y un par <x, y> referenciará al punto en la fila x, columna y.

Las líneas de código expuestas a continuación realizan las siguientes operaciones:

• Crear la imagen que se observa en la figura “Imagen de entrada”.
• Mostrar la imagen de entrada.
• Aplicar la operación pintar descrita a continuación, con los siguientes parámetros:
  • Color “r” en el punto <0,0>
  • Color “g” en el punto <6,4>
  • Color “c” en el punto <4,7>
  • Color “p” en el punto <0,7>
  • Color “q” en el punto <1,3>
• Mostrar nuevamente la imagen.

char pixels[]={'w','w','w','b','b','w','w','w',
               'w','w','b','w','w','b','w','w',
               'w','w','w','b','w','b','w','w',
               'w','w','w','w','b','w','w','b',
               'w','w','b','b','b','b','b','w',		
               'w','b','w','w','b','w','w','w',
               'w','w','w','b','w','b','w','w',
               'w','b','b','w','w','w','b','b'};

Imagen i=new Imagen(pixels);
i.show();
i.pintar('r',0,0);
i.pintar('g',6,4);
i.pintar('c',4,7);
i.pintar('p',0,7);
i.pintar('q',1,3);
i.show();

Operación pintar

Un área se define como el conjunto de puntos que no atraviesa el trazo imaginario que une los centros de los puntos frontera, que serán los que tengan un color diferente al del punto de inicio. La operación “pintar” consiste en desparramar un color hacia todos los puntos que comparten un área con el punto de inicio.

2. Implemente el método pintar, de forma recursiva, y calcule su complejidad.

3. A partir del método recursivo del ejercicio 6, desarrolle su equivalente iterativo, y calcule su complejidad.

Solución