[C con Clase] Problema OIE "Juego de cartas"

Davidson, Steven srd4121 en njit.edu
Sab Oct 1 01:49:14 CEST 2016


Hola Marcelo,

En matemáticas, se llama una relación recurrente, mientras que en la
informática se llama recursividad o función recursiva. No entra en un bucle
infinito, porque la solución indica que el caso base (o mínimo) es:
f(0) = 0

Esto significa que al calcular f(0), dejamos de usar la definición de f(n)
y pasamos a usar la definición del caso base. Por ejemplo,

Si n=2,

f(2) = 1 + min( f(1), f(-3), f(-6), f(-12) )

Como no tiene sentido usar números negativos, ya que "n" es un número
natural, entonces sólo miramos el caso de f(1); o sea,

f(1) = 1 + min( f(0), f(-4), f(-7), f(-13) )

pasamos a calcular,

f(0) = 0

Ahora, regresamos a las definiciones anteriores:

f(1) = 1 + min( 0, inválido, inválido, inválido ) = 1
f(2) = 1 + min( 1, inválido, inválido, inválido ) = 2

El resultado es 2.


En cuanto a la programación dinámica, se trata de una "optimización
dinámica", que se basa en descomponer un problema complejo en varios
problemas simples (o menos complejos). Típicamente, se aplica alguna mejora
para no tener que recalcular la misma solución en diferentes
descomposiciones. Por ejemplo,

f(16) = 1 + min( f(15), f(11), f(8), f(2) )

Tenemos que calcular los cuatro subproblemas:

f(15) = 1 + min( f(14), f(10), f(7), f(1) )
f(11) = 1 + min( f(10), f(6), f(3), f(-3) )
f(8)  = 1 + min( f(7), f(3), f(0), f(-6) )
f(2)  = 1 + min( f(1), f(-3), f(-6), f(-12) )

Ahora tendríamos que calcular cada recursividad de cada cuarteto de
subproblemas; es decir, f(14), f(10), f(7), f(1), f(10), f(6), f(3), f(7),
f(3), f(0), f(1). Como puedes ver, sin optimizaciones, acabaríamos
recalculando ciertas funciones varias veces, como por ejemplo, f(10), f(7),
f(1), y f(3). Estos recálculos se agravarían cuanto más profundicemos en la
descomposición de cada subproblema. Para optimizar este algoritmo,
simplemente guardamos el resultado de cada subproblema para no tener que
recalcular el mismo ciegamente.

En este caso, podemos usar un mapa (o array asociativo); por ejemplo,

f( mapa sol, entero n ) --> entero
1.  Si n no es una clave válida (o índice válido), entonces
2.     sol[n] <-- 1 + min( f(sol,n-1), f(sol,n-5), f(sol,n-8), f(sol,n-14) )
3.  Terminar( sol[n] )

Para usar esta función recursiva, con n=16, tenemos que crear el mapa y
asignar un valor inicial para el caso base:

1.  m : Crear mapa
2.  m[0]  <--  0  // Caso base
3.  resultado  <--  f(m,16)
4.  Terminar.

Como puedes ver, guardamos cada solución en su lugar, para no tener que
calcular la misma solución en otro momento.

Otra optimización es usar un método iterativo y no uno recursivo, para no
tener que recalcular las mismas soluciones, comenzando por los cálculos de
los casos más pequeños.


Espero que esto te oriente.

Steven


2016-09-30 16:26 GMT-04:00 Marcelo Miquel <marcelomiquel en gmail.com>:

> Hola comunidad,
>
> Estoy aprendiendo C++ para la OIE (Olimpiada Infomática Española) y me he
> topado con un problema de su web que por entender no entiendo ni la
> solución.
>
> Enunciado del problema: https://olimpiada-informatica.org/problem/
> cardgame/cardgame.pdf
> Solución: https://olimpiada-informatica.org/problem/cardgame/solution/
>
> Dice la solución que f(n) son el número mínimo de cartas para sumar n.
> Pero, ¿ no es f(n) un bucle infinito ?
> Agradecería que alguien me explicara esto de la programación dinámica ya
> que no lo he encontrado en c.conclase.
>
> Saludos.
>
>
------------ próxima parte ------------
Se ha borrado un adjunto en formato HTML...
URL: <http://listas.conclase.net/pipermail/cconclase_listas.conclase.net/attachments/20160930/8cb8f32e/attachment.html>


Más información sobre la lista de distribución Cconclase