Petando la pila. Problemas y retos usando recursividad.

[Pantaláimon]

¡Hola de nuevo!

¡Llegó el día! Así que aquí os traigo dos problemas más:

1) Crear una función comb que reciba dos parámetros y te devuelva el coeficiente binomial. La fórmula del coeficiente binomial es: n! / (k! * (n-k)!) donde "!" es el signo del factorial. La firma de la función será:

Código C:

unsigned comb(unsigned n, unsigned k);
 

Una de las utilidades del coeficiente binomial es para calcular el numero de subconjuntos sin repetición ni orden que podemos obtener de otro conjunto. Por ejemplo, imaginemos una bolsa con 5 bolas con las letras A, B, C, D y E y que, entonces, sólo podemos coger 3 bolas. ¿Cuantas posibles combinaciones podemos obtener contando que sacar A,B,E es lo mismo que sacar A,E,B? Pues ese número te lo da: comb(5,3)

2) Dado un número, podemos jugar al siguiente juego:
a) Si es par, lo dividimos entre 2.
b) Si es impar, lo multiplicamos por 3 y luego le sumamos 1.
Podemos realizar estas reglas sobre el número que nos retorna tantas veces como nos dé la gana. Por ejemplo con el 6:

Código explicación:

6 -> 3 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1 -> 4 -> 2 -> 1 -> 4 -> 2 -> 1 -> 4 ...
 

Se puede ver que llega un punto en que hay un ciclo 4 -> 2 -> 1 que se repite indefinidamente. Lothar Collatz, observó que con todos los números que iba probando -tardara más o menos- siempre llegaba al ciclo 4 -> 2 -> 1 y conjeturó que esto debía pasar con todos los números (aún no se ha demostrado que sea cierto pero para el rango de número con que vamos a trabajar es cierto).

En este segundo problema deberemos crear una función promedioCollatz que dado un numero n, nos diga el promedio de pasos que tienen que hacer los numeros del 1 al n para llegar al número 1. Por ejemplo:
1 => 0 pasos para llegar al 1
2 => 1 paso para llegar al 1
3 => 7 pasos para llegar al 1
4 => 2 pasos para llegar al 1
5 => 5 pasos para llegar al 1

Entonces la función promedioCollatz se comportaría de la siguiente manera:

Código explicación:

[B]promedioCollatz(1)[/B] == 0 / 1 == 0
[B]promedioCollatz(2)[/B] == (0+1) / 2 == 0.5
[B]promedioCollatz(3)[/B] == (0+1+7) / 3 == 2.6666..
[B]promedioCollatz(4)[/B] == (0+1+7+2) / 4 == 2.5
[B]promedioCollatz(5)[/B] == (0+1+7+2+5) / 5 == 3
etc...
 

La firma de la función será la siguiente:

Código C:

double promedioCollatz(unsigned num)
 

Los problemas se pueden resolver tanto en C como en C++.

Y ahora, ¡A petar la pila!