Программа чисел Fibonacci

по .fr

Математик  Леонардо Фибославчи в своем трактате «Liber Abaci» поставил следующую проблему:
« Сколько пар кроликов будет произведено за год, начиная с одной пары, если каждый месяц каждая пара будет создавать новую пару, которая сможет размножаться со следующего месяца?»
Ответ дается ниже алгоритмом в самых популярных языках программирования и новых языках...

---

Ada      Algol Asp Awk Basic Boo C C C C             OCaml        Oz Pascal Perl PHP Prolog Python Rexx Ruby Rust Scala Scala Scalltol   Smalltalk Swift  Tcl TypeScript   WebAssembly             

---

Ада

Рекурсивный

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;

Итеративный

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;

Алгол 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)

Асп

Рекурсивный

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

Итеративный

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

Бейсик

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

C

Рекурсивный

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

printf("%d\n", fib(10));

Итеративный

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

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

C++

Рекурсивный

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

Итеративный

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

# Рекурсивный

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

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 .fr. Dernière mise à jour 3 janvier 2014.