3 Divide y vencerás

"Divide et vinces", frase célebre de Julio César que significa "divide y vencerás", nos conduce a una buena estrategia recursiva para resolver problemas que se puedan dividir en subproblemas más sencillos.

3.1 Búsqueda binaria

Imagina que deseas encontrar el número de teléfono de algún amigo en el directorio telefónico. Por supuesto, lo único que sabes es el nombre de tu amigo y que, afortunadamente, el directorio telefónico está ordenado alfabeticamente. Una forma sencilla de encontrar el teléfono es como sigue. Compara la primera entrada del directorio con el nombre de tu amigo, si son iguales ya acabaste, si no compara la segunda entrada del directorio con el nombre de tu amigo, si son iguales ya acabaste, si no compara la tercere entreda... Esto funciona muy bien si el directorio tiene muy pocas entradas, pero si tiene muchas resulta bastante lento. ¿Qué pasaría si el nombre de tu amigo comienza con Z?

Una forma mejor es como sigue: Abre el directorio a la mitad y compara la entrada que veas con el nombre de tu amigo. Si son iguales ya acabaste. ¿Qué pasa si no son iguales? Una de dos: o bien el nombre de tu amigo está antes del que viste, o bien está después. En cualquier caso, has reducido la tarea de encontrar a tu amigo en todo el directorio a encontrarlo en una de sus mitades. Es decir, has dividido la tarea en dos. Por supuesto, el método continúa de la misma forma con la mitad restante, hasta que finalmente obtengas una sección del directorio que contiene solamente una entrada. En ese momento, puede ser esa entrada corresponda con el nombre de tu amigo, o que tu amigo no estuviera en el directorio.

Para simplificar, supongamos que la lista contiene números en lugar de nombres y que los números están ordenados de forma ascendente. Llamemos N a la cantidad de números, L1, L2, ..., LN a los miembros de la lista, y X al número que estamos buscando. También llamemos IZQ al índice izquierdo, DER al índice derecho y MED al punto medio de la parte de la lista que aún estamos considerando. Al principio IZQ = 1 y DER = N. Entonces, podemos ver que el siguiente algoritmo funciona como queremos:

Binaria(IZQ, DER)
Comienza
Si IZQ < DER entonces
MED = (IZQ + DER)/2
Si LMED < X entonces
Binaria(MED, DER)
Si no entonces
Binaria(IZQ, MED)
Si no entonces si LIZQ = X
Imprime "Encontrado en la posición" IZQ
Si no entonces
Imprime "El elemento buscado no está"
Termina

A continuación mostramos dos funciones recursivas, una en C y la otra en Pascal, que implementan nuestro algoritmo. Estas funciones regresan la posición en la que se encuentra el dato buscado, o un -1 si el dato no está.

C
Pascal
int binaria(int izq, int der, int x, int l[])
{
  int med;

  if (izq < der) {
    med = (izq + der)/2;
    if (l[med] < x)
      return binaria(med, der, x, l);
    else return binaria(izq, med, x, l);
  } else if (l[izq] == x)
    return izq;
  else return -1;
}
function binaria(izq, der, x : integer, l : array[1..N] of integer) : integer
var med : integer;
begin
  if izq < der then begin
    med := (izq + der) div 2;
    if l[med] < x then
      binaria := binaria(med, der, x, l);
    else binaria := binaria(izq, med, x, l);
    end
  else if l[izq] = x then
    binaria := izq;
  else binaria := -1;
end


3.2 Las torres de Hanoi

Una antigua leyenda dice que en cierto monasterio de Hanoi había tres postes y que en uno de ellos había 64 discos de tamaño decreciente, uno encima de otro y con el mayor hasta abajo. Los monjes del monasterio han estado trabajando sin cesar para llevar los discos desde su poste original hasta algún otro siguiendo una regla sencilla: solamente pueden mover un disco a la vez de un poste a otro, siempre y cuando queda arriba de uno mayor. La leyenda indica que el mundo terminará en el momento en que los monjes hayan logrado su propósito. Nuestra labor será ayudarle a los monjes en el proceso.

Llamemos a los postes A, B y C (siendo A el poste original y C el poste al que queremos mover todos los discos). Si solamente hubiera un disco, la tarea hubiera sido muy sencilla: movamos el único disco del poste A al poste C (y el mundo se hubiera terminado en un santiamén). Si solamente hubieran dos discos, la tarea no hubiera sido mucho más difícil: basta mover el disco pequeño al poste B, después el disco grande al poste C y finalmente el disco pequeño al poste C. Si continuamos de esta manera, pronto nos daremos cuenta que la labor monumental de mover los 64 discos se reduce a la siguiente: movamos los 63 discos más pequeños del poste A al B, movamos el disco más grande del poste A al C y finalmente movamos los 63 discos más pequeños del poste B al C. ¿Cómo hacemos para mover los 63 discos? Lo haremos de la misma forma, excepto que renombrando los postes adecuadamente.

Observa que, de esta manera, hemos dividido la tarea de mover n discos en dos tareas menores. Así, podemos convencernos de que el siguiente algoritmo recursivo mueve n discos de un poste original a un poste destino utilizando un tercer poste auxiliar:

Hanoi(n, Original, Auxiliar, Destino)
Comienza
Si n es mayor que 0 entonces
Hanoi(n-1, Original, Destino, Auxiliar)
Mueve un disco de Original a Destino
Hanoi(n-1, Auxiliar, Original, Destino)
Termina

Por ejemplo, si n es igual a 4, nuestro algoritmo haría los siguientes movimientos (denotamos por AB la operación de mover un disco de A a B, etcétera):

AB, AC, BC, AB, CA, CB, AB, AC, BC, BA, CA, BC, AB, AC, BC.

A continuación mostramos dos funciones recursivas, una en C y la otra en Pascal, que implementan nuestro algoritmo. Por supuesto, debemos llamar a estas funciones con el valor adecuado de n (64 para ayudar a los pobres monjes de la leyenda) y con tres valores distintos en a, b y c (digamos a = 1, b = 2 y c = 3).

C
Pascal
void hanoi(int n, int a, int b, int c)
{
  if (n > 0) {
    hanoi(n-1, a, c, b);
    printf("%d%d\n", a, c);
    hanoi(n-1, b, a, c);
  }
}
procedure hanoi(n, a, b, c : integer)
begin
  if n > 0 then begin
    hanoi(n-1, a, c, b);
    writeln(a, c);
    hanoi(n-1, b, a, c);
  end
end

Si los monjes hacen un movimiento por segundo, ¿cuánto durará el mundo según nuestro algoritmo? ¿Habrá algún algoritmo más rápido, es decir, alguno que requiera menos movimientos?

3.3 Permutaciones

Ya habíamos hablado de las permutaciones en la sección 2.1 y dijimos que n! contaba el número de ellas. Pero, si las necesitaramos ¿cómo las generaríamos? Para darnos una idea, demos un vistazo a las 4! = 24 permutaciones de los números 1, 2, 3 y 4:

1234 1243 1324 1342 1423 1432 2134 2143 2314 2341 2413 2432 3124 3142 3214 3241 3412 3421 4123 4132 4213 4231 4312 4321.

Si observas bien, notarás que las 24 permutaciones de los cuatro números 1, 2, 3 y 4 se pueden obtener de la siguiente forma: primero escribamos las 3! = 6 permutaciones que comienzan con 1, luego las 6 que comienzan con 2, luego las 6 que comienzan con 3 y finalmente las 6 que comienzan con 4. Es decir, hemos dividido la tarea de escribir las 4! permutaciones en las 4 tareas de escribir un elemento y las 3! permutaciones de los 3 restantes. En general, podemos dividir la tarea de escribir las n! permutaciones de n elementos en las n tareas de escribir uno de ellos y las (n-1)! permutaciones de los demás.

Aquí puedes encontrar un programa en C y un programa en Pascal que tienen como entrada un número n del 1 al 10 y escriben las n! permutaciones de {1, 2, ..., n}.