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  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   Tcl   TypeScript


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(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

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#

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]

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)
}

Voir aussi


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