Ejemplo

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 con 0 y 1, ylos 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
...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 el número Fnque está en su mismacolumna.
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 F9, nos basta conocer F8=21 y F7=13. Los valores de F6 y anteriores ya no interesan.
Elalgoritmo, 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ánactualizadas 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 yactual.
Para saber cuándo hemos llegado al número deseado, hay quellevar 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ánlas 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...