Programme des nombres de Fibonacci

par Scriptol.fr

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   Algol   Asp   Awk   Basic   Boo   C   C++   C#   Caml   Cobol   CoffeeScript   Dart   Eiffel   Erlang   F#   Forth   Fortran  Go  Haskell   Java   Julia   JavaScript   Lisp   Lua   Oberon   Objective C   OCaml   Oz   Pascal   Perl  PHP   Prolog   Python  Rebol   Rexx   Ruby   Rust   Scala   Scheme   Scriptol   Smalltalk   Swift   Tcl   TypeScript   WebAssembly

---

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;

Algol 68

PROC print fib = (INT n) VOID :
    BEGIN
        INT a := 0;
        INT b := 1;
        FOR i TO n DO
            print((whole(i, 0), " => ", whole(b, 0), new line));
            INT c = a + b;
            a := b;
            b := c
        OD
    END;

print fib(10)

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(n);
 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

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#

Récursif

using System;

class App 
{

  public static int fibo(int n) 
  {
    return (n < 2) ? n : 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.

CoffeeScript

fibo = (n) -> 
   if n is 0 or n is 1 return n
   fibo(n-1)+ fibo(n-2)

for i in [1..16]
    console.log fibo(i)

Dart

int fibo(int i) {
  if (i < 2) return i;
  return fibo(i - 2) + fibo(i - 1);
}

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", [fibo(Num)]),
    halt(0).

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

F# (F Sharp)

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

fibo 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

Go

package main
import(
 "fmt"
 "math"
)

func fibo(n int) int {
  if n < 2 {
   return n
  }
  return fibo(n-2) + fibo(n-1)
}

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(n);
      return( fib(n-2) + fib(n-1) );
    }
}

Code source

JavaScript

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

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

Julia

Récursif

fibo(n) = n < 2 ? n : fibo(n-1) + fibo(n-2)

Itératif

function fibo(n)
  x,y = (0,1)
  for i = 1:n
    x,y = (y, x+y)
  end
  return x
end


for n=1:10 
  println(fibo(n))
end

Lisp

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

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

Lua

function fibo(n)
   if (n < 2) then return(1) end
   return( fibo(n-2) + fibo(n-1) ) 
end  
N = tonumber((arg and arg[1])) or 1 
write(fibo(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.  

Objective C

int i, a = 1, b = 0;
int top = 50;

for(i = 2; i < top; i++) {
  fibo = a + b;
  a = b;
  b = fibo;
  printf("fibo(%d) %d\n", i, fibo);
}

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;     
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.

Code source

Perl

Itératif 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 - 1) + fibo($n - 2));
}
$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  [ n ] [ (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 return n
    return fib(n-2) + fib(n-1)

Ruby

Récursif

def fibo(n)
  return n if n <= 1
  return fibo(n-1) + fibo(n-2)
end

puts fibo(16)

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}

Rust

fn fibo(n: int) -> int {
  if (n <= 1) {
    ret n;
  } 
  else {
    ret fibo(n - 1) + fibo(n - 2);
  }
}

print(fmt!("%d ", fibo(10)));

Scala

Récursif

object Fibonacci with Application 
{

  def fibo(n: Int): Int =
    if (n < 2) n
    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

# Fonction de Fibonacci récursive

constant int fmax = 16

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

for int i in 1..fmax          // boucle sur un intervalle
    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]

Swift

func fib(n: Int) -> Int {
  if n <= 1 {
    return n
  }
  return (fib(n - 1) + fib(n - 2))
}

for x in 10 {
  print(fib(x))
}

Tcl

proc fib {n} {
  if {$n < 2} {
     return $n
  } 
  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]

TypeScript

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

WebAssembly

(module
 (export "fib" (func $fib))
 (func $fib (param $n i32) (result i32)
  (if (i32.lt_s (get_local $n)(i32.const 2))
   (return (i32.const 1)
   )
  )
  (return (i32.add
    (call $fib (i32.sub (get_local $n)(i32.const 2)))
    (call $fib (i32.sub (get_local $n)(i32.const 1)))
   )
  )
 )
)

Voir aussi

• Le programme "Salut le Monde' dans tous les langages de programmation.
• Le crible d'Eratosthènes en tout langage de programmation.
• Histoire et évolution des langages informatique.

© 2006-2020 Scriptol.fr. Dernière mise à jour 3 janvier 2014.