Non podes ir polo mundo da programación sen ter escrito varias veces e en distintas linguaxes un algoritmo da serie de Fibonacci.
Problema
Calcular o termo n da serie de Fibonacci.
Análise
- Definimos a serie de Fibonacci recursivamente como F(n) = F(n-1) + F(n-2), é decir, unha serie na que cada termo é a suma dos dous termos anteriores. Por definición os dous primeiros termos son 0 e 1, ou sexa F(0) = 0 e F(1) = 1 (a isto é o que lle chamamos paso base en recursividade), polo que a serie será 0 1 1 2 3 5 8 13 21...
Algoritmo
- Podemos facelo de varios xeitos, neste caso imos utilizar a recursividade.
- É interesante comprobar que neste caso a recursividade non é unha solución óptima, sería moito mellor a iteración.
Outra opción distinta en Scratch:
- Creamos unha lista e almacenamos a serie na lista.
- O índice da lista equivale ao índice do termo da serie, polo que só temos que indicar o último termo da lista.
[Scratch: Fibonacci recursivo]
Exercicios:
- En Python, escribir e gardar nunha lista os termos da serie ata o número indicado, como fixemos en Scratch.
- Dado un número indicar cal é o termo da serie de Fibonacci anterior (por exemplo: se das o 10 díría 8).
- Máis avanzado: dado un número, indicar se é un termo da serie de Fibonacci.
- Engadir no anterior, que se o número dado é da serie escribir a serie ata ese número.