Source : Ahmed Fessi

Tâche :Ecrire une fonction qui prend en argument un entier positif n et renvoie le nème terme de la suite de Fibonacci défini par

• F(0)=1
• F(1)=1
• F(n)=F(n-1)+F(n-2)

Exemple :

• Entrée : n=5
• Sortie : F(5)=8

Correction

Idée : on  calcule en utilisant la formule de récurrence de proche en proche : On connait F(0) et F(1) et on cherche F(n) : il suffit alors de calculer F(2), F(3) .... F(n) avec la formule pour avoir le résultat :

Autrement dit :

Il suffit de calculer simultanément deux valeurs consécutives de la suite, c'est-à-dire en commençant avec les deux premières valeurs 0 et 1, et en remplaçant répétitivement le premier nombre par le second, et le second nombre par la somme des deux.

Pascal : Par Ahmed Fessi

Voici la fonction écrite en Pascal 

 function fibonacci (n : integer) : integer;
var
  u:  integer;   (* contient u(n-2) *)
  v:  integer;   (* contient u(n-1) *)
  w:  integer;   (* contient u(n)    *)
  i: integer;
begin
  (* initialisation *)
  if (n=0) or (n=1) then fibonacci:=1
else
begin
  u:=1; v:=1;    (* u(0) et u(1) *)
   (* calcul des termes *)
  for i:=2 to n do
     begin
       w := u + v;   (* calcul de u(n) par recurrence *)
       u := v;       (* passage au rang n+1*)
       v := w;
     end;
fibonacci:=w;
end;
end;

 En Java ou C :

int F(int n) {
  int a;
  int b;
  int c;
  int i;
 
  a = 0;
  b = 1;
 
  if (n < 1) {
    return n;
  } else {
    i = 1;
    while (i < n) {
      c = a + b;
      a = b;
      b = c;
      i = i + 1;
    }
  }
  return c;
}