A propos de la suite de Fibonacci

Salut,
Un de mes amis a demandé la resolution du problème suivant:

un bachelier a écrit:1. Ecrire un programme en Pascal qui calcule et affiche les N premiers termes de la suite de Fibonacci, définie par la relation suivante :
Un+2 = Un+1 + Un ; U0=1 et U1=2
2. Ecrire une analyse, un algorithme et un programme en Pascal qui saisit un entier X et détermine s’il peut être un terme de la suite de Fibonacci, c’est-à-dire, il existe un entier naturel n tel que Un = X puis afficher n.
Exemple :
X=5, la réponse est OUI, car U3=5

Pour les intéressés, essayer de cogiter un peu...

informiX

salut
bon voila ce que je propose comme solution à la premiere partie de cet exercice:

program suite;
uses wincrt;
type=array[0..100]of integer;
var
i,n:integer;
t:tab;
begin
repeat
write('saisir un entier ');
read(n);
until n>=0;
write(1,' ',2,' ');
for i:= 0 to n-2 do
begin
t[i+2]:=t[i+1]+t[i];
write(' ',t[i+2],' ');
end;
end.
a+

Salut,
Merci infiniment Nadou. J'ai compilé avec succès la solution que t'a proposée. Elle répond à la question. Mais, moi et mes amis, on est entrain de penser à une solution sans l'utilisation de TABLEAU . Parceque le tableau est un peu génant dans le mesure où il impose une taille maximale, càd un 'n' maximal pour la suite de fibonacci.
Restons en conctact.

informiX

Salut,

Effectivement, la solution de Nadou (avec tableau) est correcte. Toutefois, l'utilisation des tableaux pour calculer les termes d'une suite n'est pas conseillée pour plusieurs raisons, telles que la limitation à la taille du tableau. Par exemple, si on déclare un tableau T de taille 100, on ne peut pas calculer U(101); U(102) etc...

B.Nabil a écrit:Une meilleure solution est d'utiliser une structure itérative (boucle) pour calculer Un avec "aucune limite informatique" sur n.

Cette solution est prometteuse. Vous pouver l'utiliser pour répondre à la 2ème question de l'exercice proposé.

B.Nabil

Salut à tous,
Concernant la première question

Calcul du nième terme de la suite de Fibonacci, définie par U0=1, U1=2 et U(n+2)=U(n+1)+U(n) et ce, sans l'utilisation d'un Tableau,

on propose la solution suivante:

B.Nabil a écrit:On stock U(n) dans la variable Ua.
On stock U(n+1) dans la variable Ub.
On stock U(n+2) dans la variable Uc.
A chaque itération, U(n) prend la valeur de U(n+1) et U(n+1) prend la valeur de U(n+2).
USES wincrt;
VARn,i,Ua,Ub,Uc: integer;
BEGIN
{Saisie de l'indice}
REPEAT
write('Donner un indice n = ');
read(n);
UNTIL (n>=0);
{Calcul de U(n), n=0,1,...}
Ua := 1;
Ub := 2;
IF (n = 0) THEN write('U0 = ',Ua);
IF (n = 1) THEN write('U1 = ',Ub);
IF (n > 1) THEN
BEGIN
i := 1;
REPEAT
Uc := Ua + Ub;
Ua := Ub;
Ub := Uc
i := i + 1;
UINTIL (i >= n);
write('U',n,' = ',Uc);
END;
END.

Je vous laisse le soin de vérifier le programme (le compiler au moins) et de vous inspirer pour répondre à la 2è question de l'exercice.

B.Nabil
[corrigé]

Algorithme récursif waleed

L'implémentation récursive waleed qui suit la définition de la suite de Fibonacci est immédiate. En C, cela donne :

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

Ce n'est cependant pas une façon judicieuse de calculer la suite de Fibonacci, car on calcule de nombreuses fois les mêmes valeurs (à moins d'employer une technique de mémoization). Le temps de calcul s'avère exponentiel.

Version récursive terminale:


int fibo(int nb1, int nb2, int n){
if(n==0) return 0;
if(n<2) return nb2;
return fibo(nb2,nb1+nb2,n-1);
}


Algorithme linéaire


Un moyen bien plus efficace de calculer la suite de Fibonacci consiste à 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.

En Java ou en C, cela donne :


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


De manière équivalente, on peut écrire une fonction récursive terminale :


int fibo(int nb1, int nb2, int n){
if(n==0) return 0;
if(n<2) return nb2;
return fibo(nb2,nb1+nb2,n-1);
}



En PHP :



function fibonacci($n) {
$a = 0;
$b = 1;
$c =1;
if($n == 0 || $n == 1) {
return $n;
}
else {
for($i = 1; $i < $n; $i++) {
$c = $a + $b;
$a = $b;
$b = $c;
}
return $c;
}
}


Ou bien en Scheme, sans boucle :


; Usage : (fibo n 1 1)
(define (fibo n u v)
(if (= n 0)
u
(if (= n 1)
v
(fibo (- n 1) v (+ u v)))))


Le temps de calcul est à chaque fois proportionnel à n et l'espace mémoire occupé constant.




a+++++++++++++++

Salut,

Pour plus d'information sur les références utilisées dans cette réponse donnée par pirate, consulter le lien
http://fr.wikipedia.org/wiki/Suite_de_Fibonacci

B.NabiL

salu pour tous le monde


admin a ecrir sa

Salut,

Pour plus d'information sur les références utilisées dans cette réponse donnée par pirate, consulter le lien
http://fr.wikipedia.org/wiki/Suite_de_Fibonacci


pk sa tu fait quoi

Salut pirate,
il faut toujours donner sa propore réponse puis, si c'est possible, on cite des références auxquelles on peut se référer pour avoir l'information complète. C'est une bonne habitude que je conseille tout les membres du forum d'avoir.

B.NabiL