Fibonacci

8 octubre 2006

En muchas asignaturas de algoritmia utilizan la sucesión de Fibonacci como ejemplo de algoritmo recursivo.

La peor forma de darnos la sucesión de Fibonacci es así: 1,1,2,3,5,8…
Otra forma con la que queda totalmente definida es a través de su término general:

fib(n) = n                            si         n < = 1
fib(n) = fib(n-1) + fib(n-2)          si         n > 1

A la vista de la segunda definición de la sucesión de Fibonacci es muy fácil darse cuenta del algoritmo recursivo múltiple que hay que hacer para resolver el problema de hallar el n-ésimo término de la sucesión.

func fib (n:entero) dev (res:entero)
alg
   si (n< =1):
      res := n
   otras:
      res := fib(n-1) + fib(n-2)
   fsi
fin

Según la posición de la llamada a la misma función en un algoritmo recursivo podemos distinguir entre recursividad no final y final, a ésta última nos referimos cuando no hay que realizar más procesamiento después de la llamada recursiva.

Ahora veremos como conseguir un algoritmo recursivo final que nos devuelva el valor de la n-ésimo termino de la sucesión de Fibonacci mediante el uso de acumuladores.

func fibFinal (n:entero) dev (res:entero)
alg
   res := 0
   si (n < 2):
      res := 1
   otras:
      res := fibFinalAux(n,1,0,1)
   fsi
fin

func fibFinalAux (n,i,f0,f1:entero) dev (res:entero)
alg
   res := 0
   si (i = n):
      res := f1
   otras:
      res := fibFinalAux(n,i+1,f1,f0+f1)
   fsi
fin

Lo que hemos hecho ha sido utilizar 2 acumuladores, f0 que almacena en todo momento el valor de fib(n-2) y f1 que almacena el valor de fib(n-1).

Por último, debemos saber que cualquier algoritmo recursivo final puede transformarse en un algoritmo iterativo con un bucle. Si el algoritmo fuese no final tendríamos que usar 2 bucles.

Vamos a ver como pasamos de un algoritmo recursivo final (anterior) a uno iterativo.

func fibIter (n:entero) dev (res:entero)
var
   i,f0,f1,faux: entero
alg
   i := 1
   f0 := 0
   f1 := 1
   faux := 0
   res := 0

   si (n < 2):
      res := 1
   otras:
      mientras (i < n)
         i := i+1
         faux := f0
         f0 := f1
         f1 := faux + f1
      fmientras
      res := f1
   fsi
fin

He hecho la traza de los algoritmos y todos cumplen con su labor. He estado buscando un poco en internet para ver si mi solución era la más eficiente y no he encontrado ninguna para los 2 últimos algoritmos asi que si veis alguna mejora debeis comentadmela )

Si os han mandado estos pequeños ejercicios para una práctica pensadlos un poquito y no los copieis porque sino no sirve de nada y yo no me fiaría de un algoritmo de alguien que no conozco.

:wq

2 Responses to “Fibonacci”

  1. Susana Gómez Says:

    Ayer fui a ver la peli “Los Crímenes de Oxford” en la cual, hacen mención a esta serie algorítmica. Si no llega a ser por tí nunca hubiera sabido a qué se referían.
    (Antes de tu “masterclass” pensaba que “Fibonacci” era el “capo di mafia” de la 1ª temporada de la serie americana de Prison Break. ;p


  2. Leonardo de Pisa (Fibonacci) se fijó en el siglo XII en la forma en que se reproducían los conejos y definió la sucesión que lleva su apodo.

    Jejeje, todavía recuerdo un examen de Introducción a la Matemática Discreta donde un problema se introducía con 2 folios extraídos de un libro donde un maestro impresionaba a su discípulo con las maravillosas propiedades de los “Bonatchis” (números de Fibonacci).

    Si alguien sabe de qué libro se trata me encantaría releer esa parte.

    Editado: El libro en cuestión era: “El diablo de los números” de Hans Magnus Enzensberger con ISBN 8478443746


Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s

A %d blogueros les gusta esto: