[C con Clase] Recursividad

[Davidson, Steven]

Hola César,

2013/7/6 César Arias <sinatra435 en hotmail.com>

> Hola, tengo un problema.
>
> Sucede que estoy aprendiendo sobre recursividad y me encontré con un
> problema propuesto que dice:
>
> __________________________________________________________________
> Desarrolle un método recursivo (y prográmelo) para calcular la cantidad de
> maneras diferentes en las cuales un entero *k* puede escribirse como una
> suma en la cual cada uno de sus operandos es menor que k.
> _________________________________________________________________
>
> Supongo que se tiene que sacar todas las posibilidades para *k* con un
> numero de 2 o mas operandos.
>
> He encontrado la condición "trivial" con la cual se puede sostenerse la
> recursión, que es:
>
> if(k==2)
>     return 1;
>
> Bueno, es todo lo que he podido conseguir, espero me den mas ideas para
> para terminar el programa.
>
>
>
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).

Veamos algunos ejemplos,

Si k=1,

Es 1 posibilidad. Este caso nos interesa para analizar el comportamiento
del problema y así diseñar una solución.


Si k=2,

1 + 1

Por lo que hay 1 sola posibilidad.


Si k=3,

2 + 1

1 + 2
1 + 1 + 1

Hay 3 posibilidades.


Si k=4,

3 + 1

2 + 2
2 + 1 + 1

1 + 3
1 + 2 + 1
1 + 1 + 2
1 + 1 + 1

Por lo que hay 7 posibilidades.

Como podemos oibservar, el caso de k=4 agrupa las permutaciones del caso
k=3, cuando el primer operando es 1; o sea,

1 + 3
1 + 2 + 1
1 + 1 + 2
1 + 1 + 1

implica lo siguiente:

1 + Suma(k=3)

lo que sugiere que,

Suma(k=4) = 1 + Suma(k=3)

También observamos que hay dos permutaciones del caso k=2, cuando el primer
operando es 2; esto es,

2 + 2
2 + 1 + 1

Esto sugiere que,

Suma(k=4) = 2 + Suma(k=2)

Lo mismo podríamos hacer con el caso de k=3. Observamos que,

1 + 2
1 + 1 + 1

sugiere lo siguiente,

Suma(k=3) = 1 + Suma(k=2)


En general, vemos que seguimos el siguiente patrón:

Suma( k ) = (k-i) + Suma( i ),  donde i=[1, k-1], con tal de k>0


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,

Cantidad de sumas de k=3:

+1, para 2 + Suma(1)   <=  Cantidad de k=1 es 1
+1, para 1 + 2             <=  Cantidad es 1
+1, para 1 + Suma(2)   <=  Cantidad de k=2 es 1
-----
3 cantidades diferentes (permutaciones) para expresar una suma de 3.

En este caso, hacemos esta cuenta: P( Suma(1) ) + 1 + P( Suma(2) ),  donde
P representa las permutaciones.


Te dejo que termines el diseño del problema y su implementación. Espero que
esto te ayude.

Steven
------------ próxima parte ------------
Se ha borrado un adjunto en formato HTML...
URL: <http://listas.conclase.net/pipermail/cconclase_listas.conclase.net/attachments/20130706/3ab84878/attachment.html>