Ejemplo: números de Fibonacci

Como ejemplo, consideraremos el siguiente problema computacional:

Entrada:
un número entero n.
Salida:
el n-ésimo número de Fibonacci.

Entendiendo el problema

Los números de Fibonacci F_k son una sucesión de números naturales definidos de la siguiente manera:

\begin{split}F_0 &= 0, \\ F_1 &= 1, \\ F_k &= F_{k - 1} + F_{k - 2}, \qquad\text{cuando } k\ge 2.\end{split}

En palabras simples, la sucesión de Fibonacci comienza con 0 y 1, y los siguientes términos siempre son la suma de los dos anteriores.

En la siguiente tabla, podemos ver los números de Fibonacci desde el 0-ésimo hasta el duodécimo.

n 0 1 2 3 4 5 6 7 8 9 10 11 12 ...
F_n 0 1 1 2 3 5 8 13 21 34 55 89 144 ...

Nuestro algoritmo recibirá como entrada un número n que está en la primera fila de la tabla, y deberá entregar como salida el número F_n que está en su misma columna.

Proponiendo una estrategia

Una observación útil para simplificar nuestro problema es que no necesitamos llenar una tabla como la de arriba, pues a medida que vamos avanzando hacia la derecha, siempre necesitamos conocer solamente los dos últimos valores anteriores. Por ejemplo, cuando necesitamos calcular F_9, nos basta conocer F_8 = 21 y F_7 = 13. Los valores de F_6 y anteriores ya no interesan.

El algoritmo, por lo tanto, recordará en cada paso el número de Fibonacci actual y el anterior. Para ello ocuparemos dos variables, llamadas actual y anterior.

En cada paso, las variables serán actualizadas de la siguiente manera:

  • anterior tomará el valor que tenía actual;
  • actual pasará a ser la suma de los valores que tenían anterior y actual.

Para saber cuándo hemos llegado al número deseado, hay que llevar la cuenta de en qué paso vamos. Para ello, utilizaremos una variable adicional que denominaremos cuenta. En cada paso, la iremos incrementando en 1.

La siguiente tabla muestra cómo cambiarán las variables a medida que el algoritmo avanza.

cuenta 0 1 2 3 4 5 6 7 ...
anterior 0 1 1 2 3 5 8 13 ...
actual 1 1 2 3 5 8 13 21 ...

Diseñando el algoritmo

Lo primero de lo que nos ocuparemos es de cómo actualizar anterior y actual como lo propusimos más arriba.

La manera ingenua (e incorrecta) de usar las asignaciones es la siguiente:

anterior = actual
actual = anterior + actual

El problema aquí es que ambas variables dependen una de la otra. Cuando cambiamos el valor de una, el valor previo (que es el que nos interesa) se pierde para siempre.

La solución es introducir una variable adicional, para guardar uno de los valores mientras actualizamos las variables. Lo que haremos será guardar el resultado de la suma en una variable nueva.

Las asignaciones correctas son:

suma = anterior + actual
anterior = actual
actual = suma

La cuenta la actualizaremos sumándole 1 en cada paso:

cuenta = cuenta + 1

Esta operación se puede escribir también de manera abreviada:

cuenta += 1

La cuenta indica qué número de Fibonacci (es decir, qué valor de k, según la definición de arriba) es el que está en la variable actual.

Como lo que buscamos es el n-ésimo número de Fibonacci, debemos detener la iteración cuando cuenta haya llegado hasta n.

El único caso que no hemos cubierto es n = 0. Este caso es especial porque en él no existe un número anterior. La manera más sencilla de cubrirlo es comenzar el algoritmo preguntando si estamos en este caso especial. Si es así, ya sabemos que la respuesta es 0. En caso contrario, usamos el algoritmo tal como lo habíamos diseñado.

El algoritmo terminado

(Diagrama de flujo del algoritmo de Fibonacci)

Tarea

  1. Modificar el algoritmo de arriba para resolver el siguiente problema computacional:

    Entrada:

    un número entero n.

    Salida:

    los n primeros números de Fibonacci.

Por ejemplo, para n = 7, el algoritmo debe entregar 0 1 1 2 3 5 8.
  1. Modificar el algoritmo de arriba para resolver el siguiente problema computacional:

    Entrada:

    un número entero m.

    Salida:

    o no, dependiendo de si m es o no un número de Fibonacci.

Por ejemplo, para m = 17, el algoritmo debe decir no. Para m = 21, el algoritmo debe decir .