Fibonacci

[Rockleader]

Je galère à produire un algorithme permettant de calculer la suite de Fibonacci.


On est bien daccord, cette suite se définit par la relation

F_n+2 = F_n + F_n+1


???



Si je veux calculer les n premier termes de la suite.

Je vais devoir faire une boucle qui va répéter les opération tant que mon compteur ne sera pas égal au nombre voulu...


Mais mon problème c'est l'opération en elle même.

la suite devrait faire quelque chose du genre

somVal = somVal (la valeur précédente puisque c'est dans une boucle, ou bien la valeur pré enregistrer au départ) + ... ?


Et là je ne vois pas comment mettre un second terme qui me permettra de calculer à chaque fois le terme suivant.



La solution est surement toute bête, mais j'arrive pas à conceptualiser tout ça...

[Dlzlogic]

Bonjour,
A mon avis, il faut connaitre F_0 et F_1.
A mon avis, l'exercice est fait pour comprendre qu'il faut quelque fois dissocier le compteur de boucle de la valeur à utiliser au coup suivant.

[fatal_error]

peux-tu calculer F5 (sans la machine, juste avec ton stylo)?

[Rockleader]

peux-tu calculer F5 (sans la machine, juste avec ton stylo)?

F0 = 0
F1 = 1



Donc

F2 = 1
F3 = 2
F4 = 3
F5 = 5

[fatal_error]

ok.

supposons que tu calcules u_(n+1)=2u_n+3

tant que i unplus1=2*un+3
//on update un...
un=unplus1
fintantque

pour fibonacci, c'est la même chose, sauf que tu as unplus2, unplus1 et un...

essaies de cogiter un peu, c'est assez similaire

[Rockleader]

ok.blablabla

Hum ben

F2 = F0 + F1
F3 = F1+F2
F4= F2+F3
F5= F3+F4

[Rockleader]

ok.

supposons que tu calcules u_(n+1)=2u_n+3

tant que i<nmax
unplus1=2*un+3
//on update un...
un=unplus1
fintantque

pour fibonacci, c'est la même chose, sauf que tu as unplus2, unplus1 et un...

essaies de cogiter un peu, c'est assez similaire

Dans ton exemple ce ne serait pas Un = 2U(n+2) plutôt ?


Pour Fibonacci on aurait

Tant que i < n
U_n+2 = U_n + U_n+1

Voilà, ça c'est ce qu'il faut faire pour trouver les termes de la suite...mais je vois pas comment faire dans le programme pour entrer U_n et U_n+1 qui varient...si encore je pouvais apercevoir un point commun dans leur variation, mais là je n'en vois aucun...

[Dlzlogic]

Relisez ma réponse précédente :

A mon avis, l'exercice est fait pour comprendre qu'il faut quelque fois dissocier le compteur de boucle de la valeur à utiliser au coup suivant.

[fatal_error]

Dans ton exemple ce ne serait pas Un = 2U(n+2) plutôt ?

non.



Pour Fibonacci on aurait
Tant que i < n
U_n+2 = U_n + U_n+1
cest ecrit...

unplus2, unplus1 et un

Voilà, ça c'est ce qu'il faut faire pour trouver les termes de la suite...

//on update un...
un=unplus1

[Rockleader]

Je suis désolé, mais j'ai beau me creuser les méninge je ne vois pas...je comprends pas non plus pourquoi tu fais exprès d'écrire unplus2 par exemple, c'est pas anodin mais...je ne vois pas...

A mon avis, l'exercice est fait pour comprendre qu'il faut quelque fois dissocier le compteur de boucle de la valeur à utiliser au coup suivant.

J'avais bien vu. Et je pense que j'ai bien compris cela. Toutefois je ne vois toujours pas comment réaliser cet algorithme sur machine.

[Dlzlogic]

Un fois qu'il est écrit sur papier, le traduire en langage quelconque, c'est facile.
0n initialise les deux premiers termes
A0=0;
A1=1;
1- on fait une boucle de 1 à n;
2- on calcule le terme suivant (à gauche du signe '=';
3- on remplace les 2 terme à droite du signe égal par leur nouvelle valeur;
4- fin de la boucle;

Si j'en dis plus, je me fait virer ... :we:

[Rockleader]

Hum, je crois que j'ai compris ce qui manquait à ma boucle enfin ==)


En gros on a

A0 = 0
A1 = 1
K = 1
n entier

Tant que k < n entier entré par l'utilisateur

A = A0 + A1
A0 = A - A1
A1 = A - A0


C'est bien ça ? J'avais pas pensé que je pouvais changer l'égalité pour obtenir également les nouvelles valeurs de n-1 et n-2 dans la boucle !

[fatal_error]

A = A0 + A1
A0 = A - A1
A1 = A - A0

tu décris rien comme ca...
vu que A=A0+A1, apres tu rempalces
A0=A0+A1-A1, A0 va rester inchangé, c'est absolument inutile.

Tu as juste à écrire simplement
A=A0+A1
A1=A
A0=A1

c'est exactement la même chose que lorsque tu as que deux variables
A = 2A0+3
A0 = A
ou si tu préfères...
newValue = 2*oldValue + 3
oldValue = newValue

sauf que là pour fibonacci tu as trois variables (dont deux à garder en mémoire au lieu d'une)

[Dlzlogic]

Essayez de faire avec un crayon ce que vous avez écrit et vous me direz si c'est bon.
Un petit truc pour vous aidez, créez un tableau (une dizaine de valeurs) où vous écrirez les différents termes de la suite.

[Rockleader]

Bien sur je suis bête :mur:


J'ai compris merci !

[fatal_error]

sauras-tu calculer le nieme terme de la suite suivante?
u0=0
u1=1
u2=2
...
u7=7

u_(n+7) = u_n+u_(n+1)+...+u_(n+6)

et un peut plus compliqué,
on définit la suite u_n par un vecteur de la forme
u_(n+a)=[n0, n1, n2, ..., n(a-1)]
où ni, un coefficient correspond au coefficient devant u_(n+i),

exemple:
v=[1,2,-3,7]
signifie
u_(n+4)=u_n +2u_(n+1) - 3u_(n+2) + 7u_(n+3)

sauras-tu calculer le nieme terme de la suite u_n si on te donne le vecteur de coefficients?

[Rockleader]

La première je pense que oui, en revanche la seconde j'ai pas vraiment compris =)