Fibonnaci à complexité logaritmique
Résolu
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
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
Configuration: Windows XP Firefox 2.0.0.12
6 réponses
-
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: -
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 -
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. -
oui avec le lien ça marche , je vous remerciez Kzanadeus
-
Bonjour
As-tu lu TON premier post ? La réponse esr dedans ! -
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.
