Fibonacci itératif et récursif

Soyez le premier à donner votre avis sur cette source.

Vue 24 735 fois - Téléchargée 306 fois

Télécharger le projet
Commenter

Description

Ce petit bout de script permet de calculer de différentes façons les termes de la suite de fibonacci.
De plus pour chaque méthodes on a accès au calcul direct et au générateur.
La complexités respective sont O(2^n) pour la méthode récursive et O(n) pour la méthode itérative

Source / Exemple : 


#iterative implementation
#complexity O(n)
def fibo_it(i):
	a,b,cpt=0,1,0
	while cpt <= i:
		if cpt < 2 :
			c = cpt
		else :	
			c=a+b	
			a=b
			b=c
		cpt+=1
	return c

#iterative implementation of generator
def fibogen_it(i):
	a,b,cpt=0,1,0
	while cpt <= i:
		if cpt < 2 :
			c = cpt
		else :	
			c=a+b	
			a=b
			b=c
		cpt+=1
		yield c

#simple recursive implementation
#complexity O(2^n)
def fibo_rec(i):
	if i < 2 :
		return i
	return fibo_rec(i-1)+fibo_rec(i-2)

#recursive implementation of generator
def fibogen_rec(i):
	for j in range(i) :
		yield fibo_rec(j)
Télécharger le projet

Codes Sources

A voir également

Ajouter un commentaire

Commentaires

Signaler
coucou747
Messages postés
12303
Date d'inscription
mardi 10 février 2004
Statut
Modérateur
Dernière intervention
30 juillet 2012
 30
ta fonction recursive est de complexite 2 ^ n et ca c'est mal...

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
Signaler
Renfield
Messages postés
17286
Date d'inscription
mercredi 2 janvier 2002
Statut
Modérateur
Dernière intervention
23 décembre 2019
 60
En C je ferai:

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;
}
Signaler
Renfield
Messages postés
17286
Date d'inscription
mercredi 2 janvier 2002
Statut
Modérateur
Dernière intervention
23 décembre 2019
 60
le même, en ASM (pour VS)





__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
}
}
Signaler
djackows
Messages postés
1
Date d'inscription
mardi 5 février 2008
Statut
Membre
Dernière intervention
8 février 2008
L'idée du code récursif était d'être compacte.
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 !
Signaler
BruNews
Messages postés
21042
Date d'inscription
jeudi 23 janvier 2003
Statut
Modérateur
Dernière intervention
21 août 2019
 16
à la demande de Renfield:

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
}
}
Afficher les 8 commentaires
S'inscrire maintenant

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.