Programme des nombres de Fibonacci

par Scriptol.org

Le mathématicien  Leonardo Fibonacci à posé le problème suivant dans son traité Liber Abaci:
"Combien de paires de lapins auront été produites en une année, en partant d'une seule paire, si chaque mois, chaque paire procrée une nouvelle paire qui deviendra capable de se reproduire à partir du mois suivant?"
La réponse est donnée ci-dessous par un algorithme dans les langages de programmation les plus populaires et les nouveaux langages...
 
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

Récursif 
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;
Itératif 
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

Récursif 
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)
%>
Itératif 
<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("%d\n", 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

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

printf("%d\n", fib(10));
Itératif 
int fib(int n) 
{
  int first = 0, second = 1;

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

C++

Récursif 
int fib(int n) 
{
  if (n < 2)
    return n;
  else
    return fib(n-1) + fib(n-2);
}
cout << fib(10) << endl;
Itératif 
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)

Récursif 
using System;

class App 
{

  public static int fibo(int n) 
  {
    return (n < 2) ? 1 : fibo(n-2) + fibo(n-1);
  }
  public static int Main(String[] args) 
  {
    int limit;
    int f;
    limit = System.Convert.ToInt32(args[0]);
    if(limit < 1) limit = 1;
    f = fibo(limit);
    Console.WriteLine(f.ToString()+"\n");
    return(0);
 }
}
Itératif 
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

Récursif 
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
Itératif 
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("~w\n", [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

\ lit NUM à partir du dernier argument en ligne de commande
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
Une version très courte: 
\ 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 Routine F(I) qui calcule le  I ième nombre de Fibonacci
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) );
    }
}

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[1])) 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]:=1; 
  i:=2; 
  WHILE i <= n DO 
    Fibs[i]:= Fibs[i-2] + Fibs[i-1]; 
    i:=i+1; 
  END; 
  i:=0; 
  WHILE i <= n DO 
    Write(Fibs[i]); 
    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 "%d\n" (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
        [A] = {Application.getArgs plain}
        {System.printInfo {Fib {String.toInt A}}}
    end
    {Application.exit 0}
end

Pascal

Récursif 
program fibo;
uses SysUtils;

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

var 
    NUM : integer;
    f : longint;

begin
    if ParamCount = 0 then
        NUM := 1
    else
        NUM := StrToInt(ParamStr(1));
        
    if NUM < 1 then NUM := 1;
    f := fib(NUM);
    WriteLn( IntToStr(f) );
end.

Perl

Récursif utilisant bigint 
#! /usr/bin/perl
use bigint;

my ($a, $b) = (0, 1);
for (;;) 
{
    print "$a\n";
    ($a, $b) = ($b, $a+$b);
}
Récursif 
sub fibo;
sub fibo {$_ [0] < 2 ? $_ [0] : fibo ($_ [0] - 1) + fibo ($_ [0] - 2)}
Itératif 
sub fibo
{
    my ($n, $a, $b) = (shift, 0, 1);
    ($a, $b) = ($b, $a + $b) while $n-- > 0;
    $a;
}

PHP

Récursif 
<?php
function fibo($n)
{
    return(($n < 2) ? 1 : fibo($n - 2) + fibo($n - 1));
}
$n = ($argc == 2) ? $argv[1] : 1;
$r = fibo($n);
print "$r\n";
?>
Itératif 
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

Récursif 
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

Récursif 
import sys

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

def main():
    limit = int(sys.argv[1])
    print fib(limit)
main()
Avec générateur 
def fib():
    a, b = 0, 1
    while True:
        yield a
        a, b = b, a + b

Rebol 

Fib: func [N] 
[
  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

Récursif 
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)
Itératif 
 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

Récursif 
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));
};
Itératif 
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

Récursif 
(define fibo
 (lambda (x)
   (if (< x 2)
     x
     (+ (fibo (- x 1)) (fibo (- x 2))))))
Itératif 
(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

Récursif 
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
Itératif 
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: [1]
    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]

Voir aussi