Implementación de algoritmos/Matemáticas/Números de Fibonacci

Fibonacci en la programación

No se recomienda desarrollar un algoritmo recursivo debido a que el coste es mayor y en casos grandes se produce desbordamiento de pila.

En C

int main()
{
   int n, first = 0, second = 1, next, c;
 
   printf("Enter the number of terms\n");
   scanf("%d",&n);
 
   printf("First %d terms of Fibonacci series are :-\n",n);
 
   for ( c = 0 ; c < n ; c++ )
   {
      if ( c <= 1 )
         next = c;
      else
      {
         next = first + second;
         first = second;
         second = next;
      }
      printf("%d\n",next);
   }
 
   return 0;
}

Versión recursiva

unsigned int fib(unsigned int n){
  if (n < 2)
    return n;
  else
    return fib(n - 1) + fib(n - 2);
}

Usando fórmula

float fib(unsigned int n){
  float fi = (1 + sqrt(5))/2;
  return (pow(fi,(float)n) - pow(-fi,-(float)n))/sqrt(5);
}

Versión iterativa

unsigned int fib(unsigned int n){
  unsigned int i = 1, j = 0, k, t;
  for (k = 1; k <= n; k++){
    t = i + j;
    i = j;
    j = t;
  }
  return j;
}

Versión Divide y Vencerás

unsigned int fib(unsigned int n){
  unsigned int i = n - 1, a = 1, b = 0, c = 0, d = 1, t;
  if (n <= 0)
    return 0;
  while (i > 0){
    if (i % 2 == 1){
      t = d*(b + a) + c*b;
      a = d*b + c*a;
      b = t;
    }
    t = d*(2*c + d);
    c = c*c + d*d;
    d = t;
    i = i / 2;
  }
  return a + b;
}

En C++

int main()
{
   int n, primero = 0, segundo = 1, siguiente;
 
   cout << "Introduzca la cantidad de valores que desea en la sucesión"
   cin >> n;
 
   cout << "Sucesión de Fibonacci con:" << n << "valores" << endl;
 
   for (int i = 0; i < n; i++)
   {
      if (i <= 1)
         siguiente = i;
      else
      {
         siguiente = primero + segundo;
         primero = segundo;
         segundo = siguiente;
      }
      cout << siguiente << endl;
   }
 
   return 0;
}

En TCL

 #!/usr/bin/tclsh
 proc fibo {num} {
 switch $num {
   0 { return 0}
   1 { return 1}
   2 { return 1}
   default { return [expr [fibo [expr $num - 1]] + [fibo [expr $num -2]]] }  
 }
 }
 if { $argc <1 } {
         puts stderr "ERROR: Tienes que especificar un numero"
 } else {
         puts stdout "Fibonacci [lindex $argv 0] = [fibo [lindex $argv 0]]"
 }

Y para llamarlo

 ./fibonacci.tcl 10
 Fibonacci 10 = 55

En Pascal

 function fibonacci(numero:Integer):LongInt;
 begin
   fibonacci:=0;
   if numero > 0 then
   begin
     if numero = 1 then
       fibonacci:=1;
     else
       fibonacci:=fibonacci(numero-1) + fibonnacci(numero-2);
   end;
 end;

En Python

Versión recursiva

def fib(n):
    if n < 2:
        return n
    else:
        return fib(n - 1) + fib(n - 2)

Usando fórmula

def fib(n):
    fi = (1 + sqrt(5))/2
    return (fi**n - (-fi)**-n)/sqrt(5)

Versión iterativa

def fib(n):
    i,j = 1,0
    for k in range(1,n + 1):
        i,j = j, i + j
    return j

Versión Divide y Vencerás

def fib(n):
    if n <= 0:
        return 0
    i = n - 1
    a,b = 1,0
    c,d = 0,1
    while i > 0:
        if i % 2 == 1:
            a,b = d*b + c*a, d*(b + a) + c*b
        c,d = c**2 + d**2, d*(2*c + d)
        i = i / 2
    return a + b

En Máxima

Versión recursiva

fib(n):=
    if n < 2 then
        n
    else
        fib(n - 1) + fib(n - 2)
$

Usando fórmula

fib(n):=(%phi^n-(-%phi)^-n)/sqrt(5);

En Maxima (versión iterativa)

fib(n) := block(
    [i,j,k],
    [i,j] : [1,0],
    for k from 1 thru n do
        [i,j] : [j,i + j],
    return(j)
)$

Versión Divide y Vencerás

fib(n) := block(
    [i,F,A],
    if n <= 0 then
        return(0),
    i : n - 1,
    F : matrix([1,0],[0,1]),
    A : matrix([0,1],[1,1]),
    while i > 0 do block(
        if oddp(i) then
            F : F.A,
        A : A^^2,
        i : quotient(i,2)
    ),
    return(F[2,2])
)$

En Fortran 2003

PROGRAM FIBONACCI
IMPLICIT NONE
INTEGER, PARAMETER :: N = 10  ! Número de elemento deseados en la secuencia de Fibonacci
REAL, PARAMETER :: A = ((1+SQRT(5.))/2) ! Proporción áurea
REAL, DIMENSION (1:N) :: FIB = [(NINT((A**I - (1-A)**I)/SQRT(5.)), I=1,N)]
INTEGER :: I

WRITE (*,"A,I3,A") "SECUENCIA DE FIBONACCI CON",N," ELEMENTOS"
DO I = 1, N
  WRITE (*,*) FIB(I)
END DO

PAUSE

END PROGRAM FIBONACCI