FIBONACCI EN O( N )
MetalDwarf
Messages postés
241
Date d'inscription
mardi 29 octobre 2002
Statut
Membre
Dernière intervention
23 janvier 2006
-
24 juil. 2004 à 11:28
MetalDwarf Messages postés 241 Date d'inscription mardi 29 octobre 2002 Statut Membre Dernière intervention 23 janvier 2006 - 27 juil. 2004 à 22:10
MetalDwarf Messages postés 241 Date d'inscription mardi 29 octobre 2002 Statut Membre Dernière intervention 23 janvier 2006 - 27 juil. 2004 à 22:10
Cette discussion concerne un article du site. Pour la consulter dans son contexte d'origine, cliquez sur le lien ci-dessous.
https://codes-sources.commentcamarche.net/source/24822-fibonacci-en-o-n
https://codes-sources.commentcamarche.net/source/24822-fibonacci-en-o-n
27 juil. 2004 à 22:10
Non ce programme n est pas en O(k) (d ailleurs O(k) ca se dit pas, on dit O(1) en general).
Tu crois qu une matrice ca s eleve a la puissance n comme ca?? Et non c est de la que vient la complexite. Et justement le complexite de ce programme est en O(log2(n)), et ca j en suis sur je devais le demontrer en DS d info cette annee!!
27 juil. 2004 à 14:43
J'adore les math, mais pour moi, ce petit programme n'était qu'un exercice de maitrise du C (enfin, celui en tibasic, je sais pas pourquois je l'ai fait...)
je cherches en ce moment a faire du AES alors je sais c'est plus compliqué, mais en me temps on fait qqch d'un peu plus concret...
Cependant très bonne solution, mais faut y ajouter une fonction de gestion de grands nombres... (ce que je suis entrain de faire pour le rsa)
27 juil. 2004 à 14:35
27 juil. 2004 à 14:10
faut que je me recicle en bac es...
Ta solution est surement plus rapide si tu cherche un grand nombre, mais si tu cherche toute la suite, que tu veux l'enregistrer dans un fichier ?
Ce que j'ai dit marche ?
Sur ma calculatrice j'ai fais ce joli petit programme, et j'obtient
1 + f(n-1) / f(n) environ = a (1+ sqrt(5) ) / 2;
voila voila...
27 juil. 2004 à 10:59
Un=1/sqrt(5) * [p0^n - p1^n]
avec p0 et p1 les deux nombres en or :
p0=(1+sqrt(5))/2
p1=(1-sqrt(5))/2
DEMONSTRATION DE LA FORMULE :
on suppose que Un est de la forme x^n (c'est exponentielle, donc ...) alors Un+2 = Un+1 + Un
Donc : x^(n+2) - x^(n+1) - x^n = 0 <=> x^n * [x²-x-1] = 0
On suppose que x est non nul, donc x²-x-1=0
donc x=p0 ou x=p1 (nombres definis plus haut, les deux nombres en or).
De plus on peut rajouter un constant k devant x^n : Un = k.x^n
La demonstration est la meme. Mais on a aussi : U0=0 et U1=1, c'est deux conditions nous obligent a ecrire : Un = k0.p0^n + k1.p1^n (qui est solution de Un+2 = Un+1 + Un, voir demonstration plus haut), il suffit donc de determiner k0 et k1 selon les deux valeurs initiales de U0 et U1.
U0 0 k0 + k1 donc k1 = -k0
U1 1 k0.p0 + k1.p1 donc k0(p0-p1)=1 donc k0=1/(p0-p1)
Or p0-p1=sqrt(5) , faite le calcul vous meme ...
D'ou la formule :
Un=1/sqrt(5) * [p0^n - p1^n]
ou sinon :
Un=1/sqrt(5) * [((1+sqrt(5))/2)^n - ((1-sqrt(5))/2)^n]
1
26 juil. 2004 à 20:04
#include <stdio.h>
int main(void)
{
int unsigned long a,b,c,i=1;
a=0;
b=1;
while(1){
i++
c=a+b;
printf("f(%i)=%d\n",i,c);
a=b;
b=c:
}
}
26 juil. 2004 à 20:01
si je comptrends bien ,ceci devrais fonctionner pour calculer cette suite ?
#include <stdio.h>
int main(void)
{
int unsigned long a,b,c,i=1;
a=0;
b=1;
i++
c=a+b;
printf("f(%i)=%d\n",i,c);
a=b;
b=c:
}
26 juil. 2004 à 19:56
Sinon je voudrais intervenir au sujet de l'exponentielle rapide. L'algorithme est pas si difficile a comprendre (je l'ai implementer pour une cryptage RSA pour mon TPE de premier). Le but est d'elever un nombre (au une matrice) a une exposant entier (x^n). Si vous ecrivez l'exposant en base 2, alors on s'apersoit qu'il faut mutiplier par x le nombre si il y a un 1, et sinon dans les deux autre cas (0/1) on eleve au carre.
25 juil. 2004 à 13:32
En C/C++, peut etre que tu ne peux pas retourner de tableau a 2 dim, mais en tout cas tu peux retourner un double ptr :
int**exponentiation_rapide(int mat[2][2], int Puissance)
{
int **resultat // la matrice unite
*resultat = new int[2]
for(int i=0;i<2;i++)
resultat[i] = new int[2];
while (Puissance != 0)
{
// si Puissance est impair :
if(Puissance % 2)
resultat = mult_mat(resultat,mat);
mat = mult_mat(mat,mat);
Puissance /= 2;
}
return resultat;
}
25 juil. 2004 à 11:49
Il faut le faire comme je l'ai fait !
25 juil. 2004 à 11:07
Est ce que tu as une fonction de multiplication des matrices 2x2. Si non tu peux facilement en faire une qui aurait comme prototype :
int [2][2] mult_mat(int mat1[2][2],int mat2[2][2]);
a partir de la ton algo devient :
int [2][2] exponentiation_rapide(int mat[2][2], int Puissance)
{
int resultat[2][2] = {{1,0],{0,1}}; // la matrice unite
while (Puissance != 0)
{
// si Puissance est impair :
if(Puissance % 2)
resultat = mult_mat(resultat,mat);
mat = mult_mat(mat,mat);
Puissance /= 2;
}
return resultat;
}
Je crois que c est correct, mais je ne guarantie rien car je n ai implemente cet algorithme qu en Caml (langage au programme en math sup).
25 juil. 2004 à 00:59
Je souhaiterais simplement "changer" l'algo pour qu'il fonctionne avec les multiplication des matrices et non des nombres !
24 juil. 2004 à 21:01
on s'en sert en cryptographie rsa
24 juil. 2004 à 20:57
Tu apprendras tout ça en 1Ere S c'est au programme ( et je peux te dire que je m'en souvient... 21/20 au contrôle)
Sinon, j'ai trouvé l'exponentiation rapide en itératif :
ULONG exponentiation_rapide(int Nombre, int Puissance)
{
ULONG resultat = 1lu;
while (Puissance != 0)
{
// si Puissance est impair :
if(Puissance % 2)
resultat *= Nombre;
Nombre *= Nombre;
Puissance /= 2;
}
return resultat;
}
Le problème c'est que je n'arrive pas à l'implémenter avec les Multiplications de matrice...
MetalDwarf, tu peux m'aider ?
24 juil. 2004 à 16:55
Qqn dans ma classe avait le nombre d'or comme thème d'étude...
Donc, cette "fonction" si j'ai bien compris, donne :
f(x)=f(x-1)+f(x-2)
et évidement, x ne peut pas être infèrieur a deux car avec un seul lapin, on a rien...
Mais ceci c'est une fonction f:N->N
et ça ne va pas vers le nombre d'or...
24 juil. 2004 à 16:42
en effet elle diverge vers +oo !!
Je crois par contre que cette limite est vraie :
un+1
lim ------- = (1+Rac(5))/2
n->oo un
est correcte.
Quant a la methode presentee ici pour calculer cette suite, elle utilise les matrices (niveau 1ere annee de DEUG MIAS ou math sup)
24 juil. 2004 à 16:06
"Comment cette suite se fait elle ?"
=> Reformule ta question stp, je ne comprend pas trés bien ce qu'elle veut dire. Si tu demandes d'ou on la sort, faut voir pour la petite histoire des lapins de F.
Si tu parles de "comment calculer Un" :
Une suite est en faite une fonction adaptée pour N (donc l'application U:N->R alors qu'une fct est f:R->R ou dans le genre)
C'est a dire que (Un) est le n-ieme terme de la suite, et que n est un entier naturel (0,1,2,....)
Dans le cas de F., si on te donne U(0) 0 et U(1) 1, pour calculer
U(2) tu fais, sachant que U(n+2) = U(n) + U(n+1)
n+2 = 2 <=> n = 0
donc
U(0+2) = U(0) + U(0+1)
<=> U(2) = U(0) + U(1)
<=> U(2) = 0 + 1
<=> U(2) = 1
U(3) = U(1) + U(2)
<=> U(3) = 1 + 1
<=> U(3) = 2
U(4) = U(2) + U(3)
<=> U(4) = 1 + 2 = 3
etc.... (u(5) 5 ; u(6) 8 ; u(7) = 13....)
Mes variables, je suppose L et L_barre sont juste des lettres que j'ai prises pour remplacer ce nombre d'or dont l'ecriture dans une equation en ANSII est assez casse pieds et encore plus à lire.
L_barre est le conjugué de ce nombre. Le conjugué de a+b est a-b. donc L_barre = (1-Rac(5))/2.
Pour ma "formule", c'est mon prof de maths qui me l'a donné, sans la démontrer (enfin si, mais j'ai rien compris à ses histoires d'espaces vectoriel, linéarité,etc...)
Ah ui, L est la limite de la suite de F. C'est a dire que plus "n" devient grand, plus on prend n aussi grand que l'on veut, plus U(n) aura des valeurs proches de 1.668.... ((1+Rac(5))/2)
Voici la démo (enfin.. les fractions continues ne sont pas une démo à mon gout mais bon)
http://www.sciences-en-ligne.com/momo/chronomath/anx3/suite_fibo.html
J'epere que tu auras compris ce que je t'ai expliqué... mais sache que faire plus précis va m'etre difficile car je ne suis qu'en TS (ex-1er S :D)
cordailement
24 juil. 2004 à 15:02
Comment cette suite se fait elle ?
A quoi ça corespond ?
(1+Rac(5))/2 ça je comprends, c'est le nombre d'or, mais le reste...
Je sais pas pose clairement tes variables ou explique a quoi ça coresponds, la moi, je reste coincé... (même si ce problème n'est pas dans mes projets actuels, j'aime bien les math alors je me renseigne.)
24 juil. 2004 à 14:57
24 juil. 2004 à 14:54
24 juil. 2004 à 14:38
D'ailleurs, une manniere assez rapide le n-ieme terme de la suite de fibonacci est :
(si on part de U0 en 1er terme et non pas U1)
Un+1 = 1/Rac(5) * (L^n + L_barre^n)
ou L est la limite, donc (1+Rac(5))/2 et L_Barre le conjugué ((1-Rac(5)/2).
C'est, je pense, assez rapide (plus rapide que cet algo je pense), puisque n est naturel
24 juil. 2004 à 13:39
24 juil. 2004 à 11:51
Si tu veux que ton algo soit vraiment en O(log(n)), il faut imperativement utiliser l'algorithme d'exponentiation rapide sinon tu restes en O(n).
Il est tres simple a implementer, et il est naturellement recursif.
int exp_rap(int a, int n)
{
int tmp;
if(n=1) return 1;
if(n%2) // n impair
{
tmp = exp_rap(a,n/2);
return (tmp*tmp)*a;
}
// n pair
tmp = exp_rap(a,n/2);
return tmp*tmp;
}
Bien sur vu que tu utilises des matrices il faut remplacer * par le produit des matrices.
24 juil. 2004 à 11:44
"Il y a une méthode pour accélérer le tout de facon draconnienne (complexité en log(n) au lieu de n)
- on remarque que [[0,1][1,1]]^n a pour element en haut à gauche fibo(n)
- pour calculer a^n efficacement ,on utilise
a^(2*p)=(a*a)^p et a^(2*p+1)=a*((a*a)^p)"
Ca m'a l'air d'être plus rapide que mes boucles !
Si quelqu'un sait comment implémenter ça ;)
24 juil. 2004 à 11:28