fonction récursive un peu lente

Version imprimable

Voir 40 message(s) de cette discussion en une page

27/11/2008, 00h15
Maxence HUBICHE

Citation:

Envoyé par shaku

si si 2 fonctions , une récursive , et une autre itérative , mais chacune sur la même suite , c'est bien ce que j'ai réalisé ?

Ben... non !
Il n'y a qu'une seule fonction là !
qui est ET récursive ET itérative... ce qui veut dire n'importe quoi, comme l'a précisé PGZ.

Citation:

Envoyé par pgz

PS : désolé Maxence. Je n'avais pas vu.

Penses-tu !
Pas de ça entre nous :D
27/11/2008, 00h17
pgz

Eh bien non. Tu as fais la récursive (ie : Fibo applelle Fibo) mais pas l'itérative (ie : Fibo n'appelle plus Fibo et se débrouille seule ).

Tu saisis?

PS : et j'ai recommencé, mais sans le faire exprès/:oops:
27/11/2008, 00h17
shaku

je crois que vous etes embrouillé car sur le forum j'ai mis le meme nom pour 2 fonctions différentes , mais vous pouvez les appelez fibonacci pour mon 1er code et fibonacci2 pour le second , j'ai bien 2 fonctions différentes , une récursive et une itérative , mais qui traitent du meme sujet :)

non non...
Dans ton dernier code, il y a une partie récursive :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
Function fibonacci(ByVal n As Long) As Long
Dim i As Long
Dim X As Long
Dim Y As Long
Dim fib As Long
If n = 0 Then
    fibonacci = 0
ElseIf n = 1 Then
    fibonacci = 1
Else
    X = fibonacci(n - 1)
    Y = fibonacci(n - 2)

et une partie itérative

Code:

1
2
3
4
5
6
7
 
For i = 2 To n
    fib = X + Y
Next i
    fibonacci = fib
End If
End Function

Voilà qui est démontré !

27/11/2008, 00h23
shaku

ok , donc dans mon 1er code j'ai fait la fonction recursive .

je dois écrire la meme fonction mais cette fois ci de manière itérative , je l'ai fait dans mon second code mais mon second code est faux je dois le changer pour qu'il soit purement itératif c'est ça ?
27/11/2008, 00h25
pgz
Cette fois je t'ai attendu, Maxence.

Non, on ne se mélange pas les pinceaux :

Citation:

Je te répète ce que je pense : la première est récursive, propre et peu performante. La deuxième est récursive, pas très propre et lente.

La partie itérative
Code:

1 2 3 For i = 2 To n fib = X + Y Next i
ne sert qu'à dire (n-2) fois

Code:

fib = X + Y

une façon comme une autre de passer du temps...

Citation:

ok , donc dans mon 1er code j'ai fait la fonction recursive .

je dois écrire la meme fonction mais cette fois ci de manière itérative , je l'ai fait dans mon second code mais mon second code est faux je dois le changer pour qu'il soit purement itératif c'est ça ?

OUI! Bravo!
27/11/2008, 00h28
Maxence HUBICHE

moi aussi, je t'ai attendu !

Citation:

OUI! Bravo!

TOUT PAREIL !!!
:lol:
27/11/2008, 00h35
shaku

mais faudrait carrément trouver une autre relation entre les nombres qui donne le meme résultat que la def récursive , c'est plus un code informatique mais un probleme de maths là non ? car pour calculer la valeur d'une case n je dois obligatoirement me servir des valeurs des cases n-1 et n-2 ...
27/11/2008, 00h39
pgz

C'est juste. Alors calcule F(2), puis F(3), ... jusqu'à F(n).

Pour calculer une suite, en récursivité on part de n. En itératif on part de 0 ou 1.

Mais la relation à exploiter est la même. Pas d'invention mathématique pour y arriver.
27/11/2008, 00h45
shaku

ça revient au meme , pour i = 1 j'ai comme valeur 1 , pour i = 2 j'ai comme valeur 1 , pour i = 3 j'ai comme valeur 2 , pour i = 4 j'ai comme valeur 3 , pour i = 5 j'ai comme valeur 5 , pour i = 6 j'ai comme valeur 8...

à part une récursivité je vois pas comment faire :)

Salut,
au risque de casser votre trip, voici un code non récursif, simple et très rapide :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 
Function fibonacci(ByVal n As Long) As Long
Dim y(3) As Long
For i = 0 To n
Select Case i
  Case 0
      y(0) = 0
      fibonacci = 0
  Case 1
      y(1) = 1
      y(0) = 0
      fibonacci = 1
  Case Else
      fibonacci = y(1) + y(0)
      y(0) = y(1)
      y(1) = fibonacci
End Select
Next
End Function

on obtient cependant un dépassement de capacité vers 50.

27/11/2008, 00h53
Maxence HUBICHE

Ben... c'est pas sympa !
il voulait trouver tout seul :(
27/11/2008, 00h54
shaku

j'ai pas lu son message donc on peut continuer notre discussion je zappe tous les codes tout fait :)
27/11/2008, 00h55
Godzestla

Je ne connaissait pas du tout et je me suis cassé la tête dessus.

Tu veux que j'efface ? Je peux.
27/11/2008, 00h56
Maxence HUBICHE

Le dépassement de capacité vers 50 est normal !
Tu dépasse la capacité de stockage du Long :)
Laisse ton code, ca pourra servir à d'autres :)
27/11/2008, 00h56
Godzestla

Sorry,
c'était pour aider et prouver que c'était possible.

Bon trip.

Truc..... inverser la méthode......;)
27/11/2008, 00h58
shaku

bon qui peut m'aider là sur cette boucle for , je pars de ce message :

ça revient au meme , pour i = 1 j'ai comme valeur 1 , pour i = 2 j'ai comme valeur 1 , pour i = 3 j'ai comme valeur 2 , pour i = 4 j'ai comme valeur 3 , pour i = 5 j'ai comme valeur 5 , pour i = 6 j'ai comme valeur 8...

à part une récursivité je vois pas comment faire
27/11/2008, 01h00
Godzestla

La solution passe par :

Citation:

Truc..... inverser la méthode......

Donc de 0 à n au lieu de n à 0.

tu fais a la main et tu comprends... c'est ce que j'ai fait.

Bonne chance.
27/11/2008, 01h02
shaku

inverser la méthode c'est juste inverser la récursivité ça m'aide pas...ça reste de la récursion
27/11/2008, 01h03
Maxence HUBICHE

En gros, pour une fibo(n)
Tu vas avoir besoin de 3 variables...
x, y et z
et tu dois boucler sur ces trois variables (avec les traitments qui vont bien : addition et translation de données) n-1 fois

Voir 40 message(s) de cette discussion en une page