<div dir="ltr">Hola Marcelo,<div class="gmail_extra"><br></div><div class="gmail_extra">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:<br>f(0) = 0</div><div class="gmail_extra"><br></div><div class="gmail_extra">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,</div><div class="gmail_extra"><br></div><div class="gmail_extra">Si n=2,<br><br>f(2) = 1 + min( f(1), f(-3), f(-6), f(-12) )<br><br>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,</div><div class="gmail_extra"><br></div><div class="gmail_extra">f(1) = 1 + min( f(0), f(-4), f(-7), f(-13) )<br><br></div><div class="gmail_extra">pasamos a calcular,</div><div class="gmail_extra"><br></div><div class="gmail_extra">f(0) = 0<br><br>Ahora, regresamos a las definiciones anteriores:<br><br>f(1) = 1 + min( 0, inválido, inválido, inválido ) = 1<br>f(2) = 1 + min( 1, inválido, inválido, inválido ) = 2<br><br>El resultado es 2.</div><div class="gmail_extra"><br></div><div class="gmail_extra"><br></div><div class="gmail_extra">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,</div><div class="gmail_extra"><br></div><div class="gmail_extra">f(16) = 1 + min( f(15), f(11), f(8), f(2) )</div><div class="gmail_extra"><br></div><div class="gmail_extra">Tenemos que calcular los cuatro subproblemas:<br><br>f(15) = 1 + min( f(14), f(10), f(7), f(1) )<br>f(11) = 1 + min( f(10), f(6), f(3), f(-3) )</div><div class="gmail_extra">f(8) = 1 + min( f(7), f(3), f(0), f(-6) )<br></div><div class="gmail_extra">f(2) = 1 + min( f(1), f(-3), f(-6), f(-12) )</div><div class="gmail_extra"><br></div><div class="gmail_extra">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.</div><div class="gmail_extra"><br></div><div class="gmail_extra">En este caso, podemos usar un mapa (o array asociativo); por ejemplo,</div><div class="gmail_extra"><br></div><div class="gmail_extra">f( mapa sol, entero n ) --> entero<br>1. Si n no es una clave válida (o índice válido), entonces<br></div><div class="gmail_extra">2. sol[n] <-- 1 + min( f(sol,n-1), f(sol,n-5), f(sol,n-8), f(sol,n-14) )</div><div class="gmail_extra">3. Terminar( sol[n] )</div><div class="gmail_extra"><br></div><div class="gmail_extra">Para usar esta función recursiva, con n=16, tenemos que crear el mapa y asignar un valor inicial para el caso base:</div><div class="gmail_extra"><br></div><div class="gmail_extra">1. m : Crear mapa<br></div><div class="gmail_extra">2. m[0] <-- 0 // Caso base</div><div class="gmail_extra">3. resultado <-- f(m,16)</div><div class="gmail_extra">4. Terminar.</div><div class="gmail_extra"><br></div><div class="gmail_extra">Como puedes ver, guardamos cada solución en su lugar, para no tener que calcular la misma solución en otro momento.</div><div class="gmail_extra"><br></div><div class="gmail_extra">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.</div><div class="gmail_extra"><br></div><div class="gmail_extra"><br></div><div class="gmail_extra">Espero que esto te oriente.</div><div class="gmail_extra"><br></div><div class="gmail_extra">Steven</div><div class="gmail_extra"><br></div><div class="gmail_extra"><br><div class="gmail_quote">2016-09-30 16:26 GMT-04:00 Marcelo Miquel <span dir="ltr"><<a href="mailto:marcelomiquel@gmail.com" target="_blank">marcelomiquel@gmail.com</a>></span>:<br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr">Hola comunidad,<div><br></div><div>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.</div><div><br></div><div>Enunciado del problema: <a href="https://olimpiada-informatica.org/problem/cardgame/cardgame.pdf" target="_blank">https://olimpiada-<wbr>informatica.org/problem/<wbr>cardgame/cardgame.pdf</a></div><div>Solución: <a href="https://olimpiada-informatica.org/problem/cardgame/solution/" target="_blank">https://olimpiada-<wbr>informatica.org/problem/<wbr>cardgame/solution/</a></div><div><br></div><div>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 ? </div><div>Agradecería que alguien me explicara esto de la programación dinámica ya que no lo he encontrado en c.conclase.</div><div><br></div><div>Saludos.</div></div>
<br></blockquote><div><br></div></div></div></div>