FIBONACCI ITÉRATIF ET RÉCURSIF
coucou747
Messages postés
12303
Date d'inscription
mardi 10 février 2004
Statut
Membre
Dernière intervention
30 juillet 2012
-
8 févr. 2008 à 13:38
coucou747 Messages postés 12303 Date d'inscription mardi 10 février 2004 Statut Membre Dernière intervention 30 juillet 2012 - 8 févr. 2008 à 19:39
coucou747 Messages postés 12303 Date d'inscription mardi 10 février 2004 Statut Membre Dernière intervention 30 juillet 2012 - 8 févr. 2008 à 19:39
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/45640-fibonacci-iteratif-et-recursif
https://codes-sources.commentcamarche.net/source/45640-fibonacci-iteratif-et-recursif
8 févr. 2008 à 19:39
ocaml peut-etre interprete ou compile en bytecode ou en binaire classique.
8 févr. 2008 à 19:31
Sérieux, tu as déjà vu une lib maths en interprété profond ?
8 févr. 2008 à 19:21
pour des maths, on en a quoi a faire du C ou de l'asm ?
le C, ca peut se comprendre pour la vitesse, mais pour cette fonction, osef en fait, vu qu'on depasse la taille d'un int tres vite, une complexite O(n) et pas O(2^n) suffit, on est pas oblige de chercher le mili-cycle ni le O(1)... (il parait qu'une solution en O(1) existe)
mon code caml est recursif et compacte...let fibo n let rec a function | (f0, f1, 1) -> f1 | (f0, f1, n) -> a( f1, f1+f0, n-1 ) in a (1, 1, n);;
une ligne...
il est de complexite O(n), et est relativement rapide
en python, je ne saurais pas le recoder, desole
8 févr. 2008 à 18:49
Avant tout, on optimise l'algo en C qui a l'avantage de s'écrire comme on respire. L'ASM coulera de source ensuite et sera d'ailleurs inutile sur un algo aussi simple, le compilo sortira direct un ASM optimal si on lui a bien expliqué en C ce qu'on veut.
Suffit pour Fibo de placer la valeur de sortie en 1er et on aura au maxi qu'1 seul saut de code vers la sortie unique vu que EAX deja mis.
DWORD __fastcall FibonacciC(DWORD Rank)
{
DWORD vret 0, n2 0;
if(Rank == 0) goto fiboEXIT;
vret = 1;
if(Rank <= 2) goto fiboEXIT;
n2 = 1;
if((Rank -3) 0) goto goRET;
if(Rank & 1) {
vret = 2;
if(--Rank == 0) goto goRET;
}
do {
n2 += vret;
vret += n2;
} while(Rank -= 2);
goRET: vret += n2;
fiboEXIT: return vret;
}
__declspec(naked) DWORD __fastcall FibonacciASM(DWORD Rank)
{ // ECX = Rank
__asm {
xor eax, eax
test ecx, ecx
je short fiboEXIT
mov eax, 1
cmp ecx, 2
jbe short fiboEXIT
sub ecx, 3
mov edx, eax
je short goRET
test cl, al
je short goDO
sub ecx, edx
lea eax, [edx+1]
je short goRET
goDO:
add edx, eax
add eax, edx
sub ecx, 2
jne short goDO
goRET:
add eax, edx
fiboEXIT:
ret 0
}
}
8 févr. 2008 à 17:18
Bien sur la complexité d'un tel code est horrible !
Je vais éditer pour indiquer la complexité des méthodes, mais tu remarqueras que la fonction itérative est déjà en O(n).
En fait j'ai ajouter ce code car j'étais surpris qu'il ne soit pas sur Codes-Sources ! Il faut faire vivre python c'est tellement joli !
8 févr. 2008 à 16:11
__declspec(naked) long __fastcall Fibonacci(long Rank)
{
__asm {
test ecx, ecx
jz ZERO
cmp ecx, 2
jle LETWO
mov edx, 1
sub ecx, 3
test ecx, 1
jz PAIR
mov eax, 2
dec ecx
jmp CALCUL
PAIR:
mov eax, 1
CALCUL:
add edx, eax
add eax, edx
sub ecx, 2
jnz CALCUL
END:
add eax, edx
ret
ZERO:
xor eax, eax
ret
LETWO:
mov eax, 1
ret
}
}
8 févr. 2008 à 15:40
long Fibonacci(long Rank)
{
long n1,n2;
if (Rank==0)
return 0;
if (Rank<=2)
return 1;
Rank-=3;
if (Rank & 1) {
n1 = 2;
n2 = 1;
Rank--;
}
else
n1 n2 1;
while(Rank) {
n2 = n1 + n2;
n1 = n1 + n2;
Rank-=2;
}
return n1+n2;
}
8 févr. 2008 à 13:38
en caml, tu peux le faire en recursif, en complexite n :
let fibo n let rec a function | (f0, f1, 1) -> f1 | (f0,
f1, n) -> a( f1, f1+f0, n-1 ) in a (1, 1, n);;
l'idee, c'est de balader un couple de valeurs et pas une valeur