Fibonacci en cinco minutos

El ejercicio que compartimos hoy es ideal para los programadores que quieren aprender rápidamente la sintaxis PHP porque vamos a practicar un montón de cosas distintas a la vez: funciones, arrays y bucles PHP.

Tenemos un vídeo que muestra cómo programar la función Fibonacci en cinco minutos con el ejercicio correspondiente disponible en GitHub.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...

Eso sí, requiere algo de esfuerzo neuronal, hay que devanarse un poco los sesos, pensar.

Si no cuentas con mucha experiencia, no te preocupes, haz pausa donde quieras e investiga por tu cuenta las cosas que todavía no conozcas bien.

Ahora voy a contar un secreto. En realidad este vídeo es un poco satírico porque quiere notar que hay algunos cursos de programación e informática, o bootcamps, que prometen aprender todo en 1 semana.

Sin embargo al final de este post vas a encontrar lo contrario: un enlace a un artículo de Peter Norvig muy recomendable para que aprendas a programar con paciencia en diez años. Allá ustedes con la contradicción.

Pero volviendo al ejercicio, está programado en PHP CLI. El código es sencillo, simplemente se define la función Fibonacci y justo a continuación se llama para imprimir la sucesión.

/**
 * Calcula la sucesión de Fibonacci hasta $n
 * @param int $n Número enésimo de Fibonacci
 * @return array Los $n primeros números de Fibonacci
 */
function fibonacci($n)
{
    $numbers = [1,1];
    for($i=0;$i<$n-2;$i++)
    {
        $last = count($numbers);
        $numbers[] = $numbers[$last-1] + $numbers[$last-2];        
    }
    return $numbers;
}

print_r(fibonacci(7));

Una cosa muy importante es el número de veces que se ejecuta el cuerpo del bucle.

$last = count($numbers);
$numbers[] = $numbers[$last-1] + $numbers[$last-2];

Fíjate que se ejecuta n-2 veces:

for($i=0;$i<$n-2;$i++)

Así, por ejemplo, si el usuario de la función pasa un 10, el cuerpo del bucle se ejecutará 8 veces. No queremos ejecutarlo 10 veces porque ya se incluyen los dos primeros elementos de la sucesión.

$numbers = [1,1];

Si el usuario pasa un 9, se ejecutará 7 veces, y así sucesivamente...


En el video anterior fuimos tan rápido que no reparamos en un pequeño error conceptual en nuestro algoritmo Fibonacci. ¿Lo ves? Bueno, para ser precisos no se trata de un error porque aquel programa funciona bien; es más bien una cuestión de eficiencia.

Muchas veces cuando programamos rápido podemos pasar por alto aspectos del código que no se ven a primera vista tales como la eficiencia o rapidez con que se ejecuta nuestro código, y como resultado el algoritmo anterior es un poco redundante.

Entonces cabe preguntarse, ¿es necesario contar todos los elementos del array $numbers en cada interación del bucle? En esta ocasión la respuesta es no.

function fibonacci($n)
{
    $numbers = [1,1];
    for($i=2;$i<$n;$i++)
    {        
        $numbers[] = $numbers[$i-1] + $numbers[$i-2];        
    }
    return $numbers;
}

En esta variante de Fibonacci comenzamos a iterar en $i=2 y acabamos en $i<$n. Lo que importa es el número de veces que se ejecuta el cuerpo del bucle. Ahora pues empezamos a contar los elementos más convenientemente desde $i=2.

El índice $i nos sirve para llevar el conteo de los elementos que se van añadiendo a $numbers.

También te puede interesar leer esto...

Previous Post Next Post