Sucesión Fibonacci

El ejercicio de Fibonacci pregunta cuántas parejas de conejos habrá en una granja luego de "n" meses, si se coloca inicialmente una sola pareja y se parte de las siguientes premisas:

1. Los conejos alcanzan la madurez sexual a la edad de un mes.
2. En cuanto alcanzan la madurez sexual los conejos se aparean y siempre resulta preñada la hembra.
3. El periodo de gestación de los conejos es de un mes.
4. Los conejos no mueren.
5. La hembra siempre da a luz una pareja de conejos de sexos opuestos.
6. Los conejos tienen una moral y un instinto de variedad genética muy relajados y se aparean entre parientes.

El proceso de crecimiento de la población de conejos es mejor descrito con la siguiente ilustración.



Como se puede observar el número de parejas de conejos por mes está determinado por la sucesión de Fibonacci.

En matemáticas, la sucesión de Fibonacci es la siguiente sucesión infinita de números naturales:

0,1,1,2,3,5,8,13,21,34,55,89,144

La sucesión inicia con 0 y 1, y a partir de ahí cada elemento es la suma de los dos anteriores.

A cada elemento de esta sucesión se le llama número de Fibonacci. Esta sucesión fue descrita en Europa por Leonardo de Pisa, matemático italiano del siglo XIII también conocido como Fibonacci. Tiene numerosas aplicaciones en ciencias de la computación, matemáticas y teoría de juegos.


La respuesta se da a continuación por los algoritmos en los lenguajes de programación más populares y nuevos.


Ada Asp Awk Basic Boo C C++ C# Caml Cobol Eiffel Erlang F# Forth Fortran Haskell Java JavaScript Lisp Lua Oberon OCaml Oz Pascal Perl PHP Prolog Python Rebol Rexx Ruby Scala Scheme Scriptol Smalltalk Tcl

{************ Ada ***********}
Recursive

function fib(n : integer) return integer is
begin
if n < 2 then
return n;
else
return fib(n-1) + fib(n-2);
end if;
end fib;

Iterative

function fib(n : integer) return integer is
first : integer := 0;
second : integer := 1;
tmp : integer;
begin
for i in 1..n loop
tmp := first + second;
first := second;
second := tmp;
end loop;
return first;
end fib;


{*********** Asp ************}
Recursive

function fibo(byval i)
if (i = 0 or i = 1) then
fibo = i
else
fibo = fibo(i - 1) + fibo(i - 2)
end If
end function


<% for num = 1 to n
= fibo(num)
%>

Iterative

<table>
<%
dim a = 1
dim b = 1
dim num
dim d
for num = 1 to 12
d = a + b
a = b - 1
b = d
response.Write("<tr><td> " & num & "</td><td>" & a & "</td></tr>"
next
%>
</table>


{************ Awk *********}

function fib(n)
{
if(n < 2) return(1);
return(fib(n-2) + fib(n-1));
}
BEGIN
{
printf("%dn", fib(10));
exit;
}


{************ Basic**********}

x = 1
y = 1
n = 100
FOR x = 1 to n
z = x + y
x = y
y = z
PRINT z + 1
NEXT x


{********** Boo*********}

def fibo():
a, b = 0, 1
while true:
yield b
a, b = b, a+b

for i as int, element in zip(range(x), fibo()):
print("${i + 1}: ${element}"


{ ********** C ***********
Recursive

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

printf("%dn", fib(10));

Iterative

int fib(int n)
{
int first = 0, second = 1;

int tmp;
while (n--)
{
tmp = first+second;
first = second;
second = tmp;
}
return first;
}

*********** C++ ***********
Recursive

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

Iterative

int fibonacci(int n)
{
int u = 0;
int v = 1;
int i, t;

for(i = 2; i <= n; i++)
{
t = u + v;
u = v;
v = t;
}
return v;
}


{*********** C# (C Sharp) **************}
Recursive

using System;

class App
{

public static int fibo(int n)
{
return (n


Iterative

public class Fibonacci
{
public static void Main()
{
int oldnum = 1;
int currnum = 1;

int nextNumber;

System.Console.Write(currnum + " ";

while (currnum < 50)
{
System.Console.Write(currnum + " ";

nextNumber = currnum + oldnum;

oldnum = currnum;
currnum = nextNumber;
}
}
}


{************ Cobol **************}

IDENTIFICATION DIVISION.
PROGRAM-ID. FIBONACCI.

ENVIRONMENT DIVISION.
DATA DIVISION.

WORKING-STORAGE SECTION.
77 N PIC 9(18).
77 N1 PIC Z(18).
77 M PIC 9(18) VALUE 1.
77 O PIC 9(18).
77 I PIC 9(4) VALUE 1.
77 Q PIC X.

PROCEDURE DIVISION.
PARA-A.
DISPLAY ( 1 , 1 ) ERASE.
DISPLAY ( 2 , 1 ) "FIBONACCI NUMBERS FROM 1 TO 100 ARE:".
MOVE 0 TO N.
DISPLAY " ".
DISPLAY 0.
DISPLAY 1.
MOVE 0 TO O.

PARA-B.
COMPUTE N = O + M.
MOVE N TO N1.
MOVE M TO O.
MOVE N TO M.
DISPLAY N1.
ADD 1 TO I.
IF I = 21
DISPLAY "PRESS TAB KEY TO VIEW NEXT PAGE."
ACCEPT Q.
IF I = 41
DISPLAY "PRESS TAB KEY TO VIEW NEXT PAGE."
ACCEPT Q.
IF I = 61
DISPLAY "PRESS TAB KEY TO VIEW NEXT PAGE."
ACCEPT Q.
IF I = 81
DISPLAY "PRESS TAB KEY TO VIEW NEXT PAGE."
ACCEPT Q
IF I = 99
GO TO STOP-PARA
ELSE
GO TO PARA-B.
STOP-PARA.
DISPLAY " ".
STOP RUN.


{********* Eiffel************}
Recursive

class FIBONACCI
feature
fib (k: INTEGER): INTEGER is
-- Fibonnaci numbers
require
pre_fib: k >= 0 do
if k = 0 then
Result := 0
else
if k = 1 then
Result := 1
else
Result := fib (k-2) + fib (k-1) end
end;
-- fib


Iterative

fibiter (k: INTEGER): INTEGER is
-- Fibonacci
require
pre_fib: k > 0
local
j, p, c, n: INTEGER
do from
p := 0;
c := 1;
j := 1
until
j = k
loop
n := p + c;
p := c;
c := n;
j := j + 1
end;
Result := c
end;
-- fib1


{***************** Erlang ***************

-module(fibo).
-export([main/1]).

main() -> main(['1']).
main([Arg]) ->
Num = list_to_integer(atom_to_list(Arg)),
io:fwrite("~wn", [fib(Num)]),
halt(0).

fib(N) when N < 2 -> 1;
fib(N) -> fib(N-2) + fib(N-1).


{*************** F# (F Sharp)*****************}

let rec fibonacci x =
match x with
0 -> 1
| 1 -> 1
| n -> fibonacci(x - 1) + fibonacci(x - 2);;

fibonacci 10;;


{********** Forth************}

read NUM from last command line argument
0. argc @ 1- arg >number 2drop drop constant NUM

compute fibonacci numbers
: fib Récursif
dup 2 <
if
drop 1
else
dup
2 - fib
swap
1 - fib
+
then ;

NUM fib 1 u.r cr

bye

A very short version:

Nombres de Fibonacci par Bill Spight
: FIBO ( n -- n1 n0) n >= 0, n0 = Fibo(n), n1 = Fibo(n-1)
DUP 0= IF 1 SWAP ELSE 1- RECURSE TUCK + ENDIF ;


{********* Fortran****************}

PROGRAM F2A
I=35; K=I
CALL F(I)
PRINT *,K,'th Fibonacci number is',I
STOP
END PROGRAM
C
C Subroutine F(I) calculates the I'th Fibonacci number

C
SUBROUTINE F(I)
DIMENSION A(I+1)
A(1)=1; A(2)=1
DO1J=3,I+1
A(J)=A(J-1)+A(J-2)
1 CONTINUE
I=A(I+1)
RETURN
END SUBROUTINE



{*********** Haskell*************}

module Main where
import System.Environment

fibo = 1 : 1 : zipWith (+) fibo (tail fibo)

main = do
args <- getArgs
print (fibo !! (read(args!!0)-1))


{***************** Java**************}

public class fibo
{
public static void main(String args[])
{
int N = Integer.parseInt(args[0]);
System.out.println(fib(N));
}
public static int fib(int n)
{
if (n < 2) return(1);
return( fib(n-2) + fib(n-1) );
}
}

Source code
{********** JavaScript****************}

function fibo(n)
{
if (n < 2) return 1;
return fibo(n-2) + fibo(n-1);
}

for(var i = 1; i < x ; i++)
{
document.write(i, " = ", fibo(i), "<br>";
}

{********Lisp*********}

(defun fibonacci (x)
"
Calcule le nombre de fibonacci pour x
"
(if (<= x 2)
1
(+ (fibonacci (- x 2))(fibonacci (1- x)))))

(loop for i from 1 to x do
(print (fibonacci i)))


{*********** Lua **********}

function fib(n)
if (n < 2) then return(1) end
return( fib(n-2) + fib(n-1) )
end
N = tonumber((arg and arg)) or 1
write(fib(N), "n"


{***********Oberon************}

MODULE fibonacci;
(* n premiers nombres de Fibonacci *)
CONST n=151;
VAR Fibs:
ARRAY n+1 OF INTEGER;
i,j : INTEGER;
BEGIN
j:=0;
Fibs[0]:=0;
Fibs:=1;
i:=2;
WHILE i <= n DO
Fibs:= Fibs[i-2] + Fibs[i-1];
i:=i+1;
END;
i:=0;
WHILE i <= n DO
Write(Fibs);
i:=i+1;
END;
END fibonacci.


{***********Ocaml************}

let rec fib n =
if n < 2 then 1
else fib (n - 2) + fib (n - 1)

let _ =
let n =
try int_of_string Sys.argv.(1)
with Invalid_argument _ -> 1 in
Printf.printf "%dn" (fib n)



{*********** Oz**************}

functor
import System Application
define
fun {Fib N}
case N
of 0 then 1
[] 1 then 1
else {Fib N-2} + {Fib N-1} end
end
in
local A in
= {Application.getArgs plain}
{System.printInfo {Fib {String.toInt A}}}
end
{Application.exit 0}
end


{********* Pascal***********}
Recursive

program fibo;
var
result : longint;
num,i, error: integer;
strnum: string;

function fib(n : integer) : longint;
begin
if n <= 2 then fib := 1
else fib := fib(n-2) + fib(n-1);
end;

begin
if ParamCount = 0 then
begin
writeln('Enter integer:');
readln(strnum);
val(strnum,num,error);
end else
begin
val (ParamStr(1), num, error);
end;
for i := 1 to num do
begin
result:= fib(i);
writeln(i, ' : ', result);
end;

end.

Source code
{********** Perl**************}

Iterative using bigint

#! /usr/bin/perl
use bigint;

my ($a, $b) = (0, 1);
for (;
{
print "$an";
($a, $b) = ($b, $a+$b);
}

Recursive

sub fibo;
sub fibo {$_ [0] < 2 ? $_ [0] : fibo ($_ [0] - 1) + fibo ($_ [0] - 2)}

Iterative

sub fibo
{
my ($n, $a, $b) = (shift, 0, 1);
($a, $b) = ($b, $a + $b) while $n-- > 0;
$a;
}


{************ PHP*************}
Recursive

<?php
function fibo($n)
{
return(($n

Iterative

function fibonacci($length)
{
for( $l = array(1,1), $i = 2, $x = 0; $i < $length; $i++ )
{
$l[] = $l[$x++] + $l[$x];
}
return $l;
}

for{ $x=0; $x< $fibmax; $x++) echo "fib(" , $x , " ", fibonacci($x), "n"


{******* Prolog*********}
Recursive

fibo(N, 1) :-, N<2, !.
fibo(N, R) :-
N1 is N-1, N2 is N-2,
fibo(N1, R1),fibo(N2, R2),
R is R1 + R2.


{******** Python********}
Recursive

import sys

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

def main():
limit = int(sys.argv)
print fib(limit)
main()

With generator

def fib():
a, b = 0, 1
while True:
yield a
a, b = b, a + b


{******* Rebol*********}

Fib: func
[
return either N < 2 [ 1 ] [ (Fib N - 2) + (Fib N - 1) ]
]

NUM: to-integer to-string system/script/args
NUM: either NUM < 1 [ 1 ] [ NUM ]
R: Fib NUM
write %output.rebol rejoin [ R ]


{********* Rexx*********}

parse arg n
If n < 1 Then Do
n = 1
End

R = fib(N)

say R
exit

fib:
PROCEDURE
PARSE ARG N
IF N<2 THEN RETURN 1
RETURN fib(N-2) + fib(N-1)


{********** Ruby*********}
Recursive

parse arg n
If n < 1 Then Do
n = 1
End

R = fib(N)

say R
exit

fib:
PROCEDURE
PARSE ARG N
IF N<2 THEN RETURN 1
RETURN fib(N-2) + fib(N-1)

Iterative

def fib(num)
i, j = 0, 1
while i <= num
yield i
i, j = j, i + j
end
end

fib(10) {|i| puts i}


{********** Scala*********}
Recursive

object Fibonacci with Application
{

def fibo(n: Int): Int =
if (n < 2) 1
else fibo(n - 1) + fibo(n - 2);

Console.println("fib("+ x +" = " + fib(x));
};

Iterative

object Fibonacci with Application
{
def fibo(n: Int): Int =
if (n < 2) 1
else
{
def iter(x: Int, prev: Int, result: Int): Int =
if (x > n) result
else iter(x + 1, result, prev + result);
iter(3, 1, 2)
};
Console.println("fib("+ x +" = " + fib(x));
};


{********* Scheme*********}
Recursive

(define fibo
(lambda (x)
(if (< x 2)
x
(+ (fibo (- x 1)) (fibo (- x 2))))))

Iterative

(define (fibo x)
(define (fibo-iter x a b)
(if (= x 0)
a
(fibo-iter (- x 1) b (+ a b))))
(fibo-iter x 0 1))

Display

(define (fibo-run a b)
(display a)
(newline)
(fibo-run b (+ a b)))

(define fibo-run-all (fibo-run 0 1)))


{********** Scriptol********}
Recursive

constant int fmax = 16
int z

` Récursif Fibonacci function

int fib(int n)
if n <= 1
z = n
else
z = fib(n - 1) + fib(n - 2)
/if
return z

for int i in 0..fmax ` loop in a range
print "fib($i)= " , fib(i)
/for

Iterative

int fibonacci(int n)
int u = 0
int v = 1
int t

for int i in 2 .. n
t = u + v
u = v
v = t
/for
return v

for int x in 1..fibmax echo "fib(" , x , " ", fibonacci(x), "n"

{********** Smalltalk **********}

^self <= 2
ifTrue:
ifFalse: [(self - 1) fibonacci + (self - 2) fibonacci]

{******** Tcl*********}

proc fib {n} {
if {$n < 2} {
return 1
} else {
return [expr {[fib [expr {$n-2}]] + [fib [expr {$n-1}]]}]
}
}

set N [lindex $argv 0]
if {$N < 1} { set N 1 }
puts [fib $N]


Scriptol.com, interactiva.matem.unam.mx

Nos Vemos un Abrazo