Aunque el primero no fue muy bien recibido siempre es bueno poner un desafío un poco más entretenido.
Definamos la siguiente función.....
ninja(x)
{
if (x==0) return 0;
if (x==1) return 1;
if (x==2) return 1; //ninja line
return ninja(x-1) + ninja(x-2);
}
La pregunta es: si comentamos la linea con el comentario "ninja line", ¿cuántas llamadas más se hacen a la función ninja en términos de n?
Acertijo Geek #2
Enviado por Gert Findel
el 03/06/2008 a las 10:29
Etiquetas: programacion acertijo
Compártelo |
 | Comentar |
    Publicidad por Bligoo.com
Enviado por Felipe Saint-Jean
el 04/06/2008 a las 14:42
 Esta bueno el problema! Acá tiro mi intento de solución: El número de invocaciones se define por la recurrencia: T(n)=T(n-1) + T(n-2) + 1 en los dos casos. Lo que cambia es la condición de borde, o en que momento se acaba la recurrencia. La solución de la recurrencia es T(n)=2 * fib(n-1) + 2*fib(n-2) -1 con fib la función de fibonacci (fib(n) = fib (n-1) + fib(n-2) y fib(0)=1 fib(1)=1). La observación es que si ninja sin comentar se ejecuta T(n), ninja con cometario se ejecuta T(n+1) veces. Por lo que la cantidad extra de ejecuciones es T(n+1)-T(n) que es 2 * fib(n-1) - 2 * fib(n-3) o T(n-2)+1
Me tinca que hay alguna solución más simple que no requiere resolver la recurrencia, pero esta parece funcionar.
Comentarios de este artículo en RSS
|
Lo más leído
Usuarios BligooComentarios recientes
Etiquetas |
|||
|
|
||||
Ojo que este require un poco de cálculo.
PD: Aún pueden dar una explicación para el primer acertijo.