fibonnaci à complexité logaritmique Résolu/Fermé

Question

Bonjour,
je veut savoir un algorithme de calcul d'une suite de Fibonacci mais àa complexité logarithmique ( O(log(n)) et la méthode consiste à le suivant : (parexemple je veut calculer F(62) ) alors : je calcul 

-------------- 1er itération ------------------>2em itération-------------> 3em itération-----------> dernière itération 
F(31)F(30)------------------> F(15)F(14)------------------>F(7)F(6)---------------------->F(3)F(2)--------------------> F(1)F(0)


et voila à  chaque itération  en divise par 2 et on diminue 1  jusqu'a F(1) et F(0)
 et merci d'avance

kzanadeus · Answer

salut, cela me parait trop simple pour tout avoir compris mais s'est-on jamais.

int function fibo(int num)
{
if(num == 0)return 0;
if(num == 1 || num == 2)return 1;
return(fibo(num/2) + fibo((num/2)-1);
}

On dirait que c'est ce que tu veux faire mais il me semblait que la théorie était plutôt soit F la fonction de fibonacci :
Fx = Fx-1 + Fx-2
avec F0 = 0, F1 = 1 et F2 = 1.

Mais bon. J'espère que cela à pu t'aider un peu.

Cordialement Kzanadeus.

kzanadeus · Answer

RE !!!

Je viens de comprendre ou le bas blesse....

C'est un algorithme à compléxité logarithmique que tu recherche et ainsi non pas une méthode récursive terminale.

Cadeau pour toi : GOOGLE + WIKIPEDIA = https://fr.wikipedia.org/wiki/Suite_de_Fibonacci#Algorithme_logarithmique

Cordialement Kzanadeus.

b_khallou · Answer

oui avec le lien ça marche , je vous remerciez Kzanadeus

b_khallou · Answer

slt  Kzanadeus , je veut savoir est ce que cette solution à  complexité logarithmique? 
F:=proc(n) option remember;
 local m;
 if n=0 then 0
 elif n=1 then 1
 else
   m:=iquo(n,2): 
   if n mod 2 = 0 then F(m)^2+2*F(m-1)*F(m)
   else F(m)^2+F(m+1)^2 fi:
 fi:
 end:

le père · Answer

Bonjour

As-tu lu TON premier post ? La réponse esr dedans !

bachra · Answer

Bonjour, 
je veut savoir un algorithme de calcul d'une suite de Fibonacci mais àa complexité logarithmique ( O(log(n)) et la méthode consiste à le suivant : (parexemple je veut calculer F(62) ) alors : je calcul 

-------------- 1er itération ------------------>2em itération-------------> 3em itération-----------> dernière itération 
F(31)F(30)------------------> F(15)F(14)------------------>F(7)F(6)---------------------->F(3)F(2)----------------­----> F(1)F(0) 


et voila à chaque itération en divise par 2 et on diminue 1 jusqu'a F(1) et F(0) 
et merci d'avance

Fibonnaci à complexité logaritmique

6 réponses

Discussions similaires