<div dir="ltr">Hola César,<div class="gmail_extra"><br><div class="gmail_quote">2013/7/6 César Arias <span dir="ltr"><<a href="mailto:sinatra435@hotmail.com" target="_blank">sinatra435@hotmail.com</a>></span><br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">
<div><div dir="ltr"><font face="Courier New">Hola, tengo un problema.</font><br><font face="Courier New"></font> <br><font face="Courier New">Sucede que estoy aprendiendo sobre recursividad y me encontré con un problema propuesto que dice:</font><br>
<font face="Courier New"></font> <br><font face="Courier New">__________________________________________________________________</font><br><font face="Courier New">Desarrolle un método recursivo (y prográmelo) para calcular la cantidad de maneras diferentes en las cuales un entero <em>k</em> puede escribirse como una suma en la cual cada uno de sus operandos es menor que k.</font><br>
<font face="Courier New">_________________________________________________________________</font><br><font face="Courier New"></font> <br><font face="Courier New">Supongo que se tiene que sacar todas las posibilidades para <em>k</em> con un numero de 2 o mas operandos.</font><br>
<font face="Courier New"></font> <br><font face="Courier New">He encontrado la condición "trivial" con la cual se puede sostenerse la recursión, que es:</font><br><font face="Courier New"></font> <br><font face="Courier New">if(k==2)</font><br>
<font face="Courier New"> return 1;</font><br><font face="Courier New"></font> <br><font face="Courier New">Bueno, es todo lo que he podido conseguir, espero me den mas ideas para para terminar el programa.</font><br><font face="Courier New"></font> <br>
<font face="Courier New"></font></div></div><div dir="ltr"><br></div></blockquote><div><br></div><div>Si se trata de buscar todas las posibilidades con diferentes operandos y operadores, entonces se trata de un problema de permutaciones; o sea, combinatoria. Sospecho que no tomamos en cuenta el operando 0 (cero).</div>
<div><br></div><div>Veamos algunos ejemplos,</div><div><br></div><div>Si k=1,</div><div><br></div><div>Es 1 posibilidad. Este caso nos interesa para analizar el comportamiento del problema y así diseñar una solución.</div>
<div><br></div><div><br></div><div>Si k=2,<br></div><div><br></div><div>1 + 1</div><div><br></div><div>Por lo que hay 1 sola posibilidad.</div><div><br></div><div><div><br></div><div>Si k=3,<br></div><div><br></div><div>2 + 1</div>
<div><br></div><div>1 + 2</div><div><div>1 + 1 + 1</div></div><div><br></div><div>Hay 3 posibilidades.</div></div><div><br></div><div><div><br></div><div>Si k=4,<br></div><div><br></div><div>3 + 1</div><div><br></div><div>
2 + 2</div><div>2 + 1 + 1</div><div><br></div><div>1 + 3</div><div>1 + 2 + 1</div><div>1 + 1 + 2<br></div><div>1 + 1 + 1<br></div><div><br></div><div>Por lo que hay 7 posibilidades.</div></div><div><br></div><div>Como podemos oibservar, el caso de k=4 agrupa las permutaciones del caso k=3, cuando el primer operando es 1; o sea,</div>
<div><br></div><div><div>1 + 3</div><div>1 + 2 + 1</div><div>1 + 1 + 2<br></div><div>1 + 1 + 1<br></div></div><div><br></div><div>implica lo siguiente:<br><br>1 + Suma(k=3)</div><div><br></div><div>lo que sugiere que,</div>
<div><br></div><div>Suma(k=4) = 1 + Suma(k=3)</div><div><br></div><div>También observamos que hay dos permutaciones del caso k=2, cuando el primer operando es 2; esto es,</div><div><br></div><div><div>2 + 2</div><div>2 + 1 + 1</div>
</div><div><br></div><div>Esto sugiere que,</div><div><br></div><div><div>Suma(k=4) = 2 + Suma(k=2)</div></div><div><br></div><div>Lo mismo podríamos hacer con el caso de k=3. Observamos que,</div><div><br></div><div><div>
1 + 2</div><div>1 + 1 + 1</div></div><div><br></div><div>sugiere lo siguiente,</div><div><br></div><div><div>Suma(k=3) = 1 + Suma(k=2)</div></div><div><br></div><div><br></div><div>En general, vemos que seguimos el siguiente patrón:<br>
<br>Suma( k ) = (k-i) + Suma( i ), donde i=[1, k-1], con tal de k>0</div><div><br></div><div><br></div><div>Como nos interesa la cantidad de diferentes sumas, podemos formular tal comportamiento basándonos en las fórmulas de las sumas anteriores y lo que dijimos previamente. Por ejemplo,</div>
<div><br></div><div>Cantidad de sumas de k=3:<br><br>+1, para 2 + Suma(1) <= Cantidad de k=1 es 1</div><div>+1, para 1 + 2 <= Cantidad es 1<br></div><div>+1, para 1 + Suma(2) <= Cantidad de k=2 es 1</div>
<div>-----</div><div>3 cantidades diferentes (permutaciones) para expresar una suma de 3.</div><div><br></div><div>En este caso, hacemos esta cuenta: P( Suma(1) ) + 1 + P( Suma(2) ), donde P representa las permutaciones.</div>
<div><br></div><div><br></div><div>Te dejo que termines el diseño del problema y su implementación. Espero que esto te ayude.</div><div><br></div><div>Steven</div><div><br></div></div><br></div></div>