1. Accueil
  2. Python
  3. Sources Python
  4. Sources Math & Algorithmes
  5. Fibonacci itératif et récursif

Fibonacci itératif et récursif

Soyez le premier à donner votre avis sur cette source.

Vue 36 867 fois - Téléchargée 424 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
coucou747
Messages postés
12303
Date d'inscription
mardi 10 février 2004
Statut
Membre
Dernière intervention
30 juillet 2012
 41
8 févr. 2008 à 19:39
caml et python offrent de nombreux modes d'executions... python est compile en bytecode avant d'etre interprete, il peut etre compile en bytecode java aussi.
ocaml peut-etre interprete ou compile en bytecode ou en binaire classique.
BruNews
Messages postés
21041
Date d'inscription
jeudi 23 janvier 2003
Statut
Modérateur
Dernière intervention
21 août 2019
 27
8 févr. 2008 à 19:31
autant à faire que du caml... vu qu'on connait python aussi bien que toi.

Sérieux, tu as déjà vu une lib maths en interprété profond ?
coucou747
Messages postés
12303
Date d'inscription
mardi 10 février 2004
Statut
Membre
Dernière intervention
30 juillet 2012
 41
8 févr. 2008 à 19:21
mais lol...
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
BruNews
Messages postés
21041
Date d'inscription
jeudi 23 janvier 2003
Statut
Modérateur
Dernière intervention
21 août 2019
 27
8 févr. 2008 à 18:49
à 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
}
}
djackows
Messages postés
1
Date d'inscription
mardi 5 février 2008
Statut
Membre
Dernière intervention
8 février 2008
8 févr. 2008 à 17:18
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 !
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.