CyM98 - Recurrencia con tablas

<< Recurrencia con tablas >>

Lecciones anteriores:

En el Segundo Pretorneo de Computación y Matemática se tomó el siguiente problema:

Se define f(n) como la cantidad de formas distintas en que puede escribirse a n como suma de enteros positivos (sin importar en que orden se sumen, por ejemplo 15 = 7 + 3 + 5 y 15 = 5 + 3 + 7 se consideran la misma forma). Calcular f(120).

Vamos a ver como resolverlo.

Sea G(n,s) la cantidad de formas distintas en que puede escribirse a n como suma de enteros positivos menores o iguales a s.

De esta manera G(n,1) = 1 ya que n = 1+1+...+1 (n veces), y esta es la única manera de expresar a n como suma de 1.

Es fácil ver que f(n)=G(n,n).

Ahora intentemos calcular G(n,s). Cualquier forma de sumar n con números menores o iguales a s, puede tener o no algún sumando s. Por tanto, intentemos calcular la cantidad de estas sumas que tienen un sumando s, y la cantidad de las que no lo tienen.

La cantidad de formas de sumar n con sumandos no mayores a s, que no contienen ningún sumando s, no es más que G(n,s-1).

Si por el contrario, hay algún sumando s. El resto de los sumandos también son no mayores a s, y suman n-s. La cantidad de formas de hacer esto será entonces G(n-s,s)

Por lo tanto G(n,s)=G(n,s-1)+G(n-s,s). Y se puede implementar recursivamente.

Function G(n,s:LongInt):LongInt;
begin
	if n<0 Then G:=0
	else
	begin
		if s=1 Then G:=1
		else G:=G(n-s,s)+G(n,s-1);
	end;
end;

Ahora la función f se define simplemente:

Function F(n:LongInt):LongInt;
begin
	F:=G(n,n);
end;

Como ven, es muy fácil resolver recursivamente el problema si uno se da cuenta de que puede hacerse en forma recursiva. Las otras formas son mucho más difíciles.

Este programa para calcular f funciona bastante bien para valores de n relativamente chicos. Pero por los motivos explicados en la anterior lección consume mucho tiempo y memoria si n es grande.

Con memoria suficiente, el calculo de f(120) podría llevar un largo rato incluso en la mejor computadora.

¿Cómo podemos solucionar esto? Cualquiera que haya leído la lección anterior diría: "¡¡Hagámoslo iterativamente!!". Pero aquí es donde uno se pregunta: "¿Y esto como se hace iterativamente?"

Cada valor de G(n,s) se calcula a partir de varios valores de la misma función. Sabemos que en algún momento el proceso termina porque como s y n siempre se decrementan, deben llegar a uno de los casos iniciales.

Lo más razonable que se puede hacer es una tabla con todos los valores de G(n,s). En la posición n de la fila s de un array bidimensional iría el valor de G(n,s). La primera fila, que corresponde a s=1 se inicializa con todos 1s. Y luego se calculan los valores de las demás filas uno por uno. Se debe tener especial cuidado en el orden en que se calculan los valores de la tabla. Un orden incorrecto podría hacer que se acceda en algún momento a valores que no han sido calculados aún, dando valores erróneos.

Function G(n,s:LongInt):LongInt;
var
Tabla:Array[0..150,1..150] of LongInt; 
	{No molesta usar memoria de más}
i,j:LongInt;
begin
	For i:=0 To n do
		Tabla[i,1]:=1; {Inicializacion de la tabla}
	For j:=2 To n do {Iteracion por filas}
	begin
		For i:=0 To n do {Cada elemento de la fila}
		begin
			if i>=j Then 
			 Tabla[i,j]:=Tabla[i-j,j]+Tabla[i,j-1]
			else Tabla[i,j]:=Tabla[i,j-1];
		end;
	end;
	G:=Tabla[n,s];
end;

Bueno, esto es rápido. Funciona. Es corto. ¿Tendrá algún defecto?

A mí me parece bastante complicado. La solución que se me ocurrió inicialmente es la recursiva. Para lograr calcular f(120) en forma efectiva hice lo que voy a explicar a continuación. Este procedimiento iterativo lo hice sólo para escribir esta lección y no se me hubiera ocurrido jamás si no lo pensaba antes de manera recursiva. Además en otros problemas puede ser difícil darse cuenta en que orden debe ser llenada la tabla. En este caso se puede llenar fila por fila, pero podría ser bastante más complicado.

Si se varía un poco el código de la implementación recurso se puede obtener un algoritmo eficiente sin que el código deje de verse como uno espera.

La idea es guardar en una tabla los valores que ya se calcularon para no volver a calcularlos otra vez.

Hay que definir una estructura del tipo:

type
item=record
		v:LongInt;
		calculado:Boolean;
		end;
var
Tabla:array[0..150,1..150] of item;

Y agregar un procedimiento para inicializarlo:

Procedure initTabla;
var
i,j:LongInt;
begin
	For i:=0 To 150 do
	begin
		Tabla[i,1].v:=1;
		Tabla[i,1].calculado:=True;
	end;
	For i:=0 To 150 do
	For j:=2 To 150 do
		if j=1 Then Tabla[i,j].calculado:=false;
end;

Ahora G se ve así:

Function G(n,s:LongInt):LongInt;
begin
	if n<0 Then G:=0
	else
	begin
		if not Tabla[n,s].calculado Then
		{Si todavía no esta calculado, lo calculo}
		begin
	 	Tabla[n,s].v:=G(n,s-1)+G(n-s,s);
	 		Tabla[n,s].calculado:=True;
		end;
		G:=Tabla[n,s].v;
	end;
end;

Si no fuera por la inicialización, podría decir que así es más corto. De todas maneras el procedimiento initTabla es totalmente rutinario, y no se tarda nada en hacerlo.

(Versión en QB del código)

Espero que estén de acuerdo en que así es mucho más fácil que en la solución iterativa. No tengo que preocuparme por qué es lo que se calcula primero, sólo debo asegurarme que la recursión termine. Además es un fiel reflejo de lo que yo pense para resolver el problema, no como la otra solución donde lo único que se ve a simple vista es un puñado de "For" uno adentro del otro. Eso sí, no se olviden de llamar a initTabla antes de llamar a f por primera vez.

El tiempo de ejecución es aproximadamente el mismo. Con el agregado de que como este último método se guarda los resultados que va calculando, la segunda vez que se llame a f se calculará más rápido de lo esperado.

Otra ventaja es que si ya implementamos un proceso iterativo y notamos que va demasiado lento, no es muy difícil agregarle una tabla para que no calcule dos veces lo mismo.

Una de las mayores limitaciones de todo esto es la memoria que consume. En algunas raras ocasiones, no nos alcanza la memoria para guardar una tabla muy grande. Una alternativa es no guardar todos los resultados que calculamos en la tabla sino sólo algunos. Decidir cuales depende del problema. Podrían ser los primeros, los últimos, o se podría usar un algoritmo de reemplazo al estilo memoria cache.

Ejercicios:

Calcular de cuantas maneras puede dividirse el conjunto {1,...,100} en dos subconjuntos de igual suma.
En una jaula se desean colocar 3 especies de ratas: blancas, negras y marrones. Se sabe que si en algún momento hay mas ratas de alguna especie que la suma de las otras dos, entonces el grupo mayoritario atacará a las otras especies, por lo tanto esto nunca debe suceder. Se van a colocar 20 ejemplares de cada especie, y se introducirán en la jaula de a uno por vez. ¿De cuántas maneras es posible hacer esto?
Calcular cuántos números enteros de 20 cifras hay tales que cada una de sus cifras es 1, 2 o 3 y no hay cuatro cifras consecutivas iguales.
Por ejemplo: 12312311, 1112223331, 1212121212, 3212233311, etc.
Expresar 64 usando sólo un 4 y las operaciones: ! (factorial), raíz cuadrada, [] (parte entera) y techo (el menor entero mayor o igual al número).
Por ejemplo si pidiera expresar 6 el resultado sería:
6 = techo( raizCuadrada( raizCuadrada( 4! )))!
Pero como lo que hay que expresar es 64, la solución va a ser mucho más larga.

Lecciones siguientes:

Por ahora ninguna.

La idea es que hagan los ejercicios y piensen que otras cosas interesantes se pueden hacer relacionadas con estos temas. Cuéntennos lo que consiguieron y pregunten lo que no les salió. Envíen sus preguntas, dudas, sugerencias, experiencias y propuestas. Nuestra dirección es cym98@oma.org.ar .

También nos gustaría saber tu opinión sobre esta clase. Les pedimos que se tomen unos instantes y contesten estas preguntas. Con tu ayuda podremos hacer un curso cada vez mejor.

OmaNet Curso CyM98	OmaNet - Educación Interactiva www.oma.org.ar/omanet \| omanet@oma.org.ar
mensajes: webmaster@oma.org.ar