Fibonacci

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 problemaLos números de Fibonacci Fk son una sucesión de números naturales definidos de la siguiente manera:
F0 F1 Fk =0, =1, =Fk−1+Fk−2,cuando k≥2.
En palabras simples, la sucesión de Fibonacci comienza con0 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 910 11 12 ...
Fn 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 elnúmero Fn 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 quevamos avanzando hacia la derecha, siempre necesitamos conocer solamente los dos últimos valores anteriores. Por ejemplo, cuando necesitamos calcular F9, nos basta conocer F8=21 y F7=13. Los valores deF6 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.
Encada 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 sabercuá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 en1.
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...