[ Debutant ] Fonction permettant calculer une valeur d'un nombre de Fibonacci
11 réponses
Tim
Bonjour,
Je suis un débutant en C++. J'ai besoin d'aide car je ne comprends pas
le fonctionnement d'une fonction qui sert à déterminer la valeur d'un
nombre de Fibonacci à l'aide d'une itération. J'ai comrpis comment faire
la même chose à l'aide de la récursivité.
Voici le code source du programme, j'aimerais que quelqu'un qui comprend
la fonction "int fib(int n)" m'explique le fonctionnement de cette
fonction :
// Déterminer la valeur du nième nombre
// à l'aide d'une itération
#include <iostream>
int fib(int position);
int main()
{
using namespace std;
int reponse, position;
cout << "Entrez le rang a trouver : ";
cin >> position;
cout << "\n";
reponse = fib(position);
cout << reponse << " est le ";
cout << position << "e nombre dans la suite.\n";
return 0;
}
int fib(int n)
{
int moinsDeux=1, moinsUn=1, reponse=2;
En fait, quand j'essaiais de faire la fonction manuellement ( sur du papier je veux dire ) je fesais à chaque fois - 3 ... mais maintenant j'ai comprit. Merci beaucoup Pierre et à tous ceux qui ont répondu à ce post. Mais j'ai encore une petite question, pq est-ce qu'on doit faire " - 3 " au début de la boucle
? Reprenons votre code initial, bien qu'il ne soit pas le plus facile à expliquer :
int fib(int n) { int moinsDeux=1, moinsUn=1, reponse=2;
De ce qui précède, il faut qu'il soit bien clair que : for(n -= 3; n; n--){//Code} [Je rappelle que n n'est pas utilisé dans //Code] est strictement équivalent à : (faire (n - 3) fois){//Code} [Nous avons donc un simple compteur] Votre question est donc : pourquoi (n - 3) fois ? Rappel de la définition de la suite : fib(1) = 1; fib(2) = 1; ensuite : fib(n) = fib(n-1) + fib(n-2) ce qui correspond au : reponse = moinsUn + moinsDeux; Pour n = 1 et n = 2 (soit n < 3), ça renvoie 1 immédiatement. Pour n = 3 : la boucle est exécuté 0 fois, ça renvoie donc 2.
Pour n = 4 : la boucle est exécuté (4-3) = 1 fois, ça renvoie (2+1) = 3. A la fin de cette première boucle, reponse = 3, moinsUn = 2 et MoinsDeux > 1.
Pour n = 5 : la boucle est exécuté (5-3) = 2 fois. Lors de cette seconde boucle, MoinsDeux devient 2, MoinsUn devient 3, et donc reponse devient 5. Etc ...
En fait, l'affiramation "la boucle doit être effectuée n-3 fois" est vraie pour 3, 4 et 5. Mais si elle est vraie pour un N quelquonque, alors pour N+1 il faudra bien faire une boucle de plus, donc l'affiramation est vraie pour N+1. Donc, en partant de N = 5, de fil en aiguille, vous arrivez au N que vous voulez. C'est clair ? Peut-être pas ... C'est une preuve par récurrence.
Pierre
C'est bien n - 3 fois qu'il faudra effectuer la boucle.
En fait, quand j'essaiais de
faire la fonction manuellement ( sur du papier je veux dire ) je fesais
à chaque fois - 3 ... mais maintenant j'ai comprit. Merci beaucoup
Pierre et à tous ceux qui ont répondu à ce post. Mais j'ai encore une
petite question, pq est-ce qu'on doit faire " - 3 " au début de la boucle
?
Reprenons votre code initial, bien qu'il ne soit pas le plus facile à
expliquer :
int fib(int n)
{
int moinsDeux=1, moinsUn=1, reponse=2;
De ce qui précède, il faut qu'il soit bien clair que :
for(n -= 3; n; n--){//Code}
[Je rappelle que n n'est pas utilisé dans //Code]
est strictement équivalent à :
(faire (n - 3) fois){//Code}
[Nous avons donc un simple compteur]
Votre question est donc : pourquoi (n - 3) fois ?
Rappel de la définition de la suite :
fib(1) = 1;
fib(2) = 1;
ensuite :
fib(n) = fib(n-1) + fib(n-2)
ce qui correspond au :
reponse = moinsUn + moinsDeux;
Pour n = 1 et n = 2 (soit n < 3), ça renvoie 1 immédiatement.
Pour n = 3 : la boucle est exécuté 0 fois, ça renvoie donc 2.
Pour n = 4 : la boucle est exécuté (4-3) = 1 fois, ça renvoie (2+1) = 3.
A la fin de cette première boucle, reponse = 3, moinsUn = 2 et MoinsDeux > 1.
Pour n = 5 : la boucle est exécuté (5-3) = 2 fois. Lors de cette seconde
boucle, MoinsDeux devient 2, MoinsUn devient 3, et donc reponse devient 5.
Etc ...
En fait, l'affiramation "la boucle doit être effectuée n-3 fois" est vraie
pour 3, 4 et 5.
Mais si elle est vraie pour un N quelquonque, alors pour N+1 il faudra bien
faire une boucle de plus, donc l'affiramation est vraie pour N+1. Donc, en
partant de N = 5, de fil en aiguille, vous arrivez au N que vous voulez.
C'est clair ? Peut-être pas ... C'est une preuve par récurrence.
Pierre
C'est bien n - 3 fois qu'il faudra effectuer la boucle.
En fait, quand j'essaiais de faire la fonction manuellement ( sur du papier je veux dire ) je fesais à chaque fois - 3 ... mais maintenant j'ai comprit. Merci beaucoup Pierre et à tous ceux qui ont répondu à ce post. Mais j'ai encore une petite question, pq est-ce qu'on doit faire " - 3 " au début de la boucle
? Reprenons votre code initial, bien qu'il ne soit pas le plus facile à expliquer :
int fib(int n) { int moinsDeux=1, moinsUn=1, reponse=2;
De ce qui précède, il faut qu'il soit bien clair que : for(n -= 3; n; n--){//Code} [Je rappelle que n n'est pas utilisé dans //Code] est strictement équivalent à : (faire (n - 3) fois){//Code} [Nous avons donc un simple compteur] Votre question est donc : pourquoi (n - 3) fois ? Rappel de la définition de la suite : fib(1) = 1; fib(2) = 1; ensuite : fib(n) = fib(n-1) + fib(n-2) ce qui correspond au : reponse = moinsUn + moinsDeux; Pour n = 1 et n = 2 (soit n < 3), ça renvoie 1 immédiatement. Pour n = 3 : la boucle est exécuté 0 fois, ça renvoie donc 2.
Pour n = 4 : la boucle est exécuté (4-3) = 1 fois, ça renvoie (2+1) = 3. A la fin de cette première boucle, reponse = 3, moinsUn = 2 et MoinsDeux > 1.
Pour n = 5 : la boucle est exécuté (5-3) = 2 fois. Lors de cette seconde boucle, MoinsDeux devient 2, MoinsUn devient 3, et donc reponse devient 5. Etc ...
En fait, l'affiramation "la boucle doit être effectuée n-3 fois" est vraie pour 3, 4 et 5. Mais si elle est vraie pour un N quelquonque, alors pour N+1 il faudra bien faire une boucle de plus, donc l'affiramation est vraie pour N+1. Donc, en partant de N = 5, de fil en aiguille, vous arrivez au N que vous voulez. C'est clair ? Peut-être pas ... C'est une preuve par récurrence.
Pierre
C'est bien n - 3 fois qu'il faudra effectuer la boucle.
