[ Debutant ] Fonction permettant calculer une valeur d'un nombre de Fibonacci

"Tim" <timythe@freemail.ru> a écrit

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 :
<code>couic</code>

Je suppose que ce code vient d'un polycopié, d'un livre ou d'un professeur.
Si le but est de montrer le traitement non récursif d'un problème qui l'est
naturellement, le résultat n'est pas brillant.
Ce qui est peut-être peu visible, c'est que le calamiteux :
for (n -= 3; n; n--){...}
ne fait rien d'autre que de compter (n - 3) coups.
Remarquez que le n n'est pas utilisé dans la boucle, et que le fait qu'il
compte en descendant ne change rien, si ce n'est ajouter à la confusion.
Tout ce qui se passe, c'est que "reponse" est rendu égal à [moinsDeux +
moinsUn], et ce (n - 3) fois, à partir de :
reponse = 2
moinsUn = 1
moinsDeux = 1
qui sont les bonnes valeurs au rang 3.
C'est bien comme ça que nous calculons mentalement, f(3) à partir de f(1) et
f(2) et en retenant f(2) et f(3), puis f(4) à partir de f(2) et f(3) et en
retenant f(3) et f(4), etc.

Pour corriger le code et en améliorer la lisibilité :
- Utiliser le même nom dans le prototype et la définition.
- "position" est ambiguë, puisqu'il sera utilisé dans une boucle.
Choisissons "valeur", ou "rang" par exemple.
- Sauf nécessité, je préfère considérer constant ce paramètre effectif, au
moins pour que le nom garde son sens. Faire confiance au compilateur (ou
alors en changer), créer une vraie variable de boucle ne va pas dégrader
grandement les performances!
- Personnellement, je n'en fais pas une règle absolue, mais ici un seul
return suffit ici.
- Coller autant que faire se peut à la réalité : éviter de faire une boucle
à l'envers de l'intuitif.
- "n" est un int, pas un bool. Donc, le test aurait du être (n != 0). En
fait, il eut mieux valu utiliser des unsigned int, et tester (n > 0).
- n -= 3 au niveau du for(;;) est un gag.
- Ne pas confondre compacité du source et rapidité et/ou compacité du code
généré.

int fib(int valeur)
{
int reponse;
if (valeur < 3)
{
reponse = 1;
}
else
{
for (int compteur = 3, moinsUn = 1, moinsDeux = 1;
compteur <= valeur;
compteur++)
{
reponse = moinsUn + moinsDeux;//f(n) = f(n-1) + f(n-2)
// préparation pour l'éventuelle itération suivante
moinsDeux = moinsUn; //f(n-1) devient f(n-2)
moinsUn = reponse; //f(n) devient f(n-1)
}
}
return reponse;
}

Vous pouvez également ne pas aimer les multiples initialisations dans le
for(;;), et rendre le code compatible C pour pas cher :

int fib(int valeur)
{
int reponse;
if (valeur < 3)
{
reponse = 1;
}
else
{
int compteur;
int moinsUn = 1;
int moinsDeux = 1;
for (compteur = 3;
compteur <= valeur;
compteur++)
{
reponse = moinsUn + moinsDeux;/*f(n) = f(n-1) + f(n-2)*/
/*préparation pour l'itération suivante éventuelle*/
moinsDeux = moinsUn; /*f(n-1) devient f(n-2)*/
moinsUn = reponse; /*f(n) devient f(n-1)*/
}
}
return reponse;
}

Cordialement,
Pierre

"Pierre Maurette" <mmaauurreettttttee.ppiieerrrree@@ffrreeee.ffrr> writes:
|> "Tim" <timythe@freemail.ru> a écrit
|> > 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 :
|> <code>couic</code>
|> Je suppose que ce code vient d'un polycopié, d'un livre ou d'un
|> professeur. Si le but est de montrer le traitement non récursif
|> d'un problème qui l'est naturellement, le résultat n'est pas
|> brillant.

Je ne sais pas. On peut certainement faire mieux, si le but est
pédégogique, mais il faut dire que j'en ai vu bien pire aussi.

|> Ce qui est peut-être peu visible, c'est que le calamiteux :
|> for (n -= 3; n; n--){...}
|> ne fait rien d'autre que de compter (n - 3) coups.

Et qui est en fait la forme idiomatique de le faire, au moins dans le
bon vieux temps et en C.

S'il y a un problème, c'est bien le pourquoi du -= 3. Et pour la
claireté, il aurait mieux valu que la condition de la fin soit
« n > 0 », et non simplement « n ».

|> Remarquez que le n n'est pas utilisé dans la boucle, et que le
|> fait qu'il compte en descendant ne change rien, si ce n'est ajouter
|> à la confusion.

Améliorer la claireté, tu veux dire. En décomptant, c'est
claire qu'on itère pas sur un tableau -- on ne fait que compter.

En fait, j'aurais fait quelque chose de bien plus simple :

int
fib( int n ) // C'est un des rares cas où AMHA, un
{ // nom comme n est acceptable.
int prec = 1 ;
int cour = 1 ;
while ( n > 1 ) {
int tmp = cour ;
cour += prec ;
prec = tmp ;
-- n ;
}
return cour ;
}

Mais je me démande si l'utilisation d'un « tmp », bien
qu'idiomatique, n'est pas moins pédégogique qu'une variable plus
explicite. (Il y a aussi des conventions propre à moi -- dans un
algorithme itératif, par exemple, le x[i-1] s'appelle toujours prec,
pour précédant, et le x[i] cour, pour courant. Là, le nom
importe peu ; l'importance, c'est d'avoir une convention et d'y tenir.)

|> Tout ce qui se passe, c'est que "reponse" est rendu égal à [moinsDeux +
|> moinsUn], et ce (n - 3) fois, à partir de :
|> reponse = 2
|> moinsUn = 1
|> moinsDeux = 1
|> qui sont les bonnes valeurs au rang 3.

|> C'est bien comme ça que nous calculons mentalement, f(3) à
|> partir de f(1) et f(2) et en retenant f(2) et f(3), puis f(4) à
|> partir de f(2) et f(3) et en retenant f(3) et f(4), etc.

|> Pour corriger le code et en améliorer la lisibilité :
|> - Utiliser le même nom dans le prototype et la définition.

En effet, c'est une règle quasi-universelle.

|> - "position" est ambiguë, puisqu'il sera utilisé dans une boucle.
|> Choisissons "valeur", ou "rang" par exemple.

Dans le cas d'une fonction numérique, comme fib, je trouve que
« n » est très parlant. C'est en tout cas le nom que lui
donnerait n'importe quel mathématicien, je crois.

|> - Sauf nécessité, je préfère considérer constant ce
|> paramètre effectif, au moins pour que le nom garde son sens.
|> Faire confiance au compilateur (ou alors en changer), créer une
|> vraie variable de boucle ne va pas dégrader grandement les
|> performances!

Ce n'est pas une question de performance. Je ne vois pas où la
modification nuit à la lisibilité ci-dessus. En fait, si on pense
un peu de façon récursive, on se trouve bien dans une autre
invocation de la fonction, où le paramètre ait une autre valeur.

Mais je parle évidemment de ce cas-ci. Dans l'ensemble, je crois que
souvent, la modification du paramètre nuit à la lisibilité.

|> - Personnellement, je n'en fais pas une règle absolue, mais ici
|> un seul return suffit ici.

Surtout qu'il n'y a pas le moindre raison de traiter un cas spécial.

|> - Coller autant que faire se peut à la réalité : éviter
|> de faire une boucle à l'envers de l'intuitif.

L'intuitif dépend des habitudes. Moi, j'ai toujours vu des boucles de
comptage pûr qui décompte. Mais je n'ai rien contre :

for ( int i = 0 ; i < n - 2 ; i ++ )

non plus. (Dans la mesure qu'il n'y a pas de tableau en vue, c'est assez
clair que la seule chose qui puisse nous intéresser est le nombre de
fois dans la boucle.)

|> - "n" est un int, pas un bool. Donc, le test aurait du être (n ! |> 0). En fait, il eut mieux valu utiliser des unsigned int, et
|> tester |> (n > 0).

Le test doit impérativement être n > 0. Ou, comme ci-dessus, n >
1. Les conversions implicites en bool ne sont bon qu'à l'offuscation,
à certaines exceptions près (qui sont devenu si idiomatique que
faire autrement fait que le lecteur pose la question : pourquoi ?).

Quand à unsigned, il y a deux écoles. En ce qui me concerne, la
présence d'un « unsigned » signale ou qu'il y a de la
manupulation des bits (<<, >>, &, |, ^ et ~), ou que l'arithmétique
modulo est important (calcul des code d'hachage, par exemple). C'est un
point de vue assez répandu des anciens de C, pour diverses raisons
historiques (bien que Gaby semble le partager, et je ne crois pas qu'il
soit un ancien de C).

|> - n -= 3 au niveau du for(;;) est un gag.

Comme initialisation, il peut prêter à confusion. Mais en fait,
ici, le plus grand problème, c'est que c'est faux, et que la fonction
ne donne pas le bon résultat.

|> - Ne pas confondre compacité du source et rapidité et/ou
|> compacité du code généré.

Je ne crois pas que c'était le problème, étant donné que le
code en question n'était ni compact ni particulièrement rapide.

|> int fib(int valeur)
|> {
|> int reponse;
|> if (valeur < 3)
|> {
|> reponse = 1;
|> }
|> else
|> {
|> for (int compteur = 3, moinsUn = 1, moinsDeux = 1;
|> compteur <= valeur;
|> compteur++)
|> {
|> reponse = moinsUn + moinsDeux;//f(n) = f(n-1) + f(n-2)
|> // préparation pour l'éventuelle itération suivante
|> moinsDeux = moinsUn; //f(n-1) devient f(n-2)
|> moinsUn = reponse; //f(n) devient f(n-1)
|> }
|> }
|> return reponse;
|> }

Tu as oublié une règle importante : éviter les cas spéciaux.
Il n'y a aucune raison de mettre un if. Même en restant avec
l'incrémentation et les trois variables :

int
fib( int n )
{
int moinsUn = 1 ;
int moinsDeux = 1 ;
int reponse = 1 ;
for ( int compte = 1 ; compte < n ; compte ++ ) {
reponse = moinsUn + moinsDeux ;
moinsDeux = moinsUn ;
moinsUn = reponse ;
}
return reponse ;
}

|> Vous pouvez également ne pas aimer les multiples initialisations
|> dans le for(;;),

Ce n'est pas tellement des multiples initialisations, mais l'idée
qu'on déclare et initialise quelque chose qui n'a rien à voir avec
le contrôle de la boucle. Mais bien, là non plus, c'est une
question de style -- l'un et l'autre se valent.

En revanche, en C++, il est considéré assez mauvais style de
définir une variable sans l'initialiser, comme tu as fait avec
reponse.

|> et rendre le code compatible C pour pas cher :

Les deux versions que j'ai présenté ci-dessus sont toutes les deux
parfaitement légales en C.

|> int fib(int valeur)
|> {
|> int reponse;
|> if (valeur < 3)
|> {
|> reponse = 1;
|> }
|> else
|> {
|> int compteur;
|> int moinsUn = 1;
|> int moinsDeux = 1;
|> for (compteur = 3;
|> compteur <= valeur;
|> compteur++)
|> {
|> reponse = moinsUn + moinsDeux;/*f(n) = f(n-1) + f(n-2)*/
|> /*préparation pour l'itération suivante éventuelle*/
|> moinsDeux = moinsUn; /*f(n-1) devient f(n-2)*/
|> moinsUn = reponse; /*f(n) devient f(n-1)*/
|> }
|> }
|> return reponse;
|> }

J'aimerais savoir quand même une chose. D'où vient ce 3 ? Il
n'apparaît nulle part dans mes versions, et j'ai l'impression qu'il
donne de mauvais résultats.

--
James Kanze mailto:kanze@gabi-soft.fr
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
11 rue de Rambouillet, 78460 Chevreuse, France +33 1 41 89 80 93

"James Kanze" <kanze@alex.gabi-soft.fr> a écrit
[...]
D'accord avec beaucoup de tes remarques. En général, j'utilise effectivement
x, y, teta, n, p pour les fonctions nettement mathématiques.
Je ferais ma mauvaise tête seulement sur le sens de parcours de la boucle.
Il me semble que le but de l'exercice est de montrer un cas ou la solution
récursive est plus "naturelle" que la soluition itérative. J'imagine qu'ils
voient le cas contraire avec la factorielle.
fib(10) en récursif, je le vois en descendant.
fib(10) en itératif, ça monte : il faut commencer par calculer fib(3), puis
fib(4), etc. Et il me semble bien que c'est ce qui a pu perturber Tim. Si le
for() s'écrivait :
do{}((n-1)fois);
ça ne me gênerait pas. Mais comme on dit, si ma tante en avait ....

[...]

Tu as oublié une règle importante : éviter les cas spéciaux.
Il n'y a aucune raison de mettre un if. Même en restant avec
l'incrémentation et les trois variables :

int
fib( int n )
{
int moinsUn = 1 ;
int moinsDeux = 1 ;
int reponse = 1 ;
for ( int compte = 1 ; compte < n ; compte ++ ) {
reponse = moinsUn + moinsDeux ;
moinsDeux = moinsUn ;
moinsUn = reponse ;
}
return reponse ;
}
[...]

J'aimerais savoir quand même une chose. D'où vient ce 3 ? Il
n'apparaît nulle part dans mes versions, et j'ai l'impression qu'il
donne de mauvais résultats.
En fait, nous n'avons pas la même règle : j'étais allé voir un pdf qui

trainait sur mon disque (La récursivité pas à pas, par Axel
Chambily-Casadesus et Pétrut Constantine), j'ai trouvé :
f(1) = 1; f(2) = 1; f(n) = f(n-1) + f(n-2) pour n > 2
L'absence de f(0) me génait un peu, mais les résultats correspondaient à
ceux du code de Tim.
Je viens de regarder dans le "Introduction à l'algorithmique", par Thomas
Cormen, Charles Leiserson, Ronald Rivest.
Ça donne la même chose, mais plus clair :
f(0) = 0; f(1) = 1; f(n) = f(n-1) + f(n-2) pour n > 1 [donc f(2) = 1]
Pour info, fib(10) = 55.
Ça, ce sont les nombres de Fibonacci. Il est possible qu'il existe "les"
suites de Fibonacci.
Pierre

"Pierre Maurette" <mmaauurreettttttee.ppiieerrrree@@ffrreeee.ffrr> writes:

|> "James Kanze" <kanze@alex.gabi-soft.fr> a écrit
|> [...]

|> D'accord avec beaucoup de tes remarques. En général, j'utilise
|> effectivement x, y, teta, n, p pour les fonctions nettement
|> mathématiques. Je ferais ma mauvaise tête seulement sur le
|> sens de parcours de la boucle. Il me semble que le but de l'exercice
|> est de montrer un cas ou la solution récursive est plus
|> "naturelle" que la soluition itérative. J'imagine qu'ils voient
|> le cas contraire avec la factorielle.
|> fib(10) en récursif, je le vois en descendant.
|> fib(10) en itératif, ça monte : il faut commencer par calculer
|> fib(3), puis fib(4), etc. Et il me semble bien que c'est ce qui a pu
|> perturber Tim. Si le
|> do{}((n-1)fois);
|> ça ne me gênerait pas. Mais comme on dit, si ma tante en avait ....

En effet. En général, je crois que c'est surtout une question de
style. Quand et où j'ai appris le C, la forme idiomatique pour une
boucle n fois, c'était en décomptant. C'est donc la forme que
j'utilise pour les boucles n fois. Quelqu'un qui a appris dans une autre
contexte aurait peut-être une forme différente de la boucle.

|> [...]
|> > Tu as oublié une règle importante : éviter les cas
|> > spéciaux. Il n'y a aucune raison de mettre un if. Même en
|> > restant avec l'incrémentation et les trois variables :

|> > int
|> > fib( int n )
|> > {
|> > int moinsUn = 1 ;
|> > int moinsDeux = 1 ;
|> > int reponse = 1 ;
|> > for ( int compte = 1 ; compte < n ; compte ++ ) {
|> > reponse = moinsUn + moinsDeux ;
|> > moinsDeux = moinsUn ;
|> > moinsUn = reponse ;
|> > }
|> > return reponse ;
|> > }
|> [...]
|> > J'aimerais savoir quand même une chose. D'où vient ce 3 ? Il
|> > n'apparaît nulle part dans mes versions, et j'ai l'impression
|> > qu'il donne de mauvais résultats.

|> En fait, nous n'avons pas la même règle : j'étais allé
|> voir un pdf qui trainait sur mon disque (La récursivité pas
|> à pas, par Axel Chambily-Casadesus et Pétrut Constantine),
|> j'ai trouvé :
|> f(1) = 1; f(2) = 1; f(n) = f(n-1) + f(n-2) pour n > 2

La règle que j'ai toujours vue, c'est :
f(0) = 1
f(1) = 1
f(i) = f(i-1) + f(i-2)
En général, je crois que les mathématiciens commencent toujours
les séquences par f(0).

Mais je dirais que ce n'est pas là la question. Il y a une valeur
«@magique@» : 3. D'où vient-il ? Si on veut définir la
séquence à partir d'un, à la place d'à partir de zéro,
pourquoi pas -- c'est une question de cahier de charge, et non de C++.
Mais à partir d'un, ça ne donne toujours pas un 3 quelque part:-).
Au moins qu'un commentaire l'éclaire. (Et j'avoue que dans la mesure
que je commence la séquence à partir de 0, il faudrait aussi un
commentaire à ce que pourquoi ma boucle commence par 1.)

|> L'absence de f(0) me génait un peu, mais les résultats
|> correspondaient à ceux du code de Tim. Je viens de regarder dans
|> le "Introduction à l'algorithmique", par Thomas Cormen, Charles
|> Leiserson, Ronald Rivest. Ça donne la même chose, mais plus
|> clair :
|> f(0) = 0; f(1) = 1; f(n) = f(n-1) + f(n-2) pour n > 1 [donc f(2) = 1]

OK. Dans ce cas, l'algorithme serait :

int prec = 1 ;
int result = 0 ;
while ( n > 0 ) {
int tmp = result ;
result += prec ;
prec = tmp ;
-- n ;
}
return result ;

ou

int moinsUn = 1 ;
int moinsDeux = 0 ;
int reponse = 0 ;
for ( int compte = 0 ; compte < n ; compte ++ ) {
reponse = moinsUn + moinsDeux ;
moinsDeux = moinsUn ;
moinsUn = reponse ;
}
return reponse ;

Dans ce cas-là, la version à trois variables me paraît
justifiable. Mais ça ne me plaît toujours pas pleinement qu'il y a
une initialisation « magique » de prec/moinsUn.

|> Pour info, fib(10) = 55.
|> Ça, ce sont les nombres de Fibonacci. Il est possible qu'il
|> existe "les" suites de Fibonacci.

Il faudrait démander aux mathématiciens.

--
James Kanze mailto:kanze@gabi-soft.fr
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
11 rue de Rambouillet, 78460 Chevreuse, France +33 1 41 89 80 93

James Kanze <kanze@alex.gabi-soft.fr> writes:

"Pierre Maurette" <mmaauurreettttttee.ppiieerrrree@@ffrreeee.ffrr> writes:

|> Je viens de regarder dans le "Introduction à l'algorithmique",
|> par Thomas Cormen, Charles Leiserson, Ronald Rivest. Ça donne la
|> même chose, mais plus clair :

|> f(0) = 0; f(1) = 1; f(n) = f(n-1) + f(n-2) pour n > 1 [donc f(2) = 1]

OK. Dans ce cas, l'algorithme serait :

int prec = 1 ;
int result = 0 ;
while ( n > 0 ) {
int tmp = result ;
result += prec ;
prec = tmp ;
-- n ;
}
return result ;

ou

int moinsUn = 1 ;
int moinsDeux = 0 ;
int reponse = 0 ;
for ( int compte = 0 ; compte < n ; compte ++ ) {
reponse = moinsUn + moinsDeux ;
moinsDeux = moinsUn ;
moinsUn = reponse ;
}
return reponse ;

Dans ce cas-là, la version à trois variables me paraît
justifiable. Mais ça ne me plaît toujours pas pleinement qu'il y a
une initialisation « magique » de prec/moinsUn.

Mais il s'agit de l'énoncé, non ? De la même manière que la valeur
d'initialisation de result/reponse est 0, ou f(0), l'initialisation de
prec/moinsUn correspond à 1, ou f(1).

Non ?

--drkm

"drkm" <fr.comp.lang.c++@fgeorges.org> a écrit ...
[...]

Mais il s'agit de l'énoncé, non ? De la même manière que la valeur
d'initialisation de result/reponse est 0, ou f(0), l'initialisation de
prec/moinsUn correspond à 1, ou f(1).

Non ?
Si, si, vous avez tout à fait raison. En fait, c'est même plus que ça, la

question initiale proposait un code valide (disons qu'il fonctionnait) et
demandait des éclaircissements sur son fonctionnement.
Pierre

Pierre Maurette wrote:

"Tim" <timythe@freemail.ru> a écrit

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 :

<code>couic</code>
Je suppose que ce code vient d'un polycopié, d'un livre ou d'un professeur.
Si le but est de montrer le traitement non récursif d'un problème qui l'est
naturellement, le résultat n'est pas brillant.
Ce qui est peut-être peu visible, c'est que le calamiteux :
for (n -= 3; n; n--){...}
ne fait rien d'autre que de compter (n - 3) coups.
Remarquez que le n n'est pas utilisé dans la boucle, et que le fait qu'il
compte en descendant ne change rien, si ce n'est ajouter à la confusion.
Tout ce qui se passe, c'est que "reponse" est rendu égal à [moinsDeux +
moinsUn], et ce (n - 3) fois, à partir de :
reponse = 2
moinsUn = 1
moinsDeux = 1
qui sont les bonnes valeurs au rang 3.
C'est bien comme ça que nous calculons mentalement, f(3) à partir de f(1) et
f(2) et en retenant f(2) et f(3), puis f(4) à partir de f(2) et f(3) et en
retenant f(3) et f(4), etc.

Pour corriger le code et en améliorer la lisibilité :
- Utiliser le même nom dans le prototype et la définition.
- "position" est ambiguë, puisqu'il sera utilisé dans une boucle.
Choisissons "valeur", ou "rang" par exemple.
- Sauf nécessité, je préfère considérer constant ce paramètre effectif, au
moins pour que le nom garde son sens. Faire confiance au compilateur (ou
alors en changer), créer une vraie variable de boucle ne va pas dégrader
grandement les performances!
- Personnellement, je n'en fais pas une règle absolue, mais ici un seul
return suffit ici.
- Coller autant que faire se peut à la réalité : éviter de faire une boucle
à l'envers de l'intuitif.
- "n" est un int, pas un bool. Donc, le test aurait du être (n != 0). En
fait, il eut mieux valu utiliser des unsigned int, et tester (n > 0).
- n -= 3 au niveau du for(;;) est un gag.
- Ne pas confondre compacité du source et rapidité et/ou compacité du code
généré.

int fib(int valeur)
{
int reponse;
if (valeur < 3)
{
reponse = 1;
}
else
{
for (int compteur = 3, moinsUn = 1, moinsDeux = 1;
compteur <= valeur;
compteur++)
{
reponse = moinsUn + moinsDeux;//f(n) = f(n-1) + f(n-2)
// préparation pour l'éventuelle itération suivante
moinsDeux = moinsUn; //f(n-1) devient f(n-2)
moinsUn = reponse; //f(n) devient f(n-1)
}
}
return reponse;
}

Vous pouvez également ne pas aimer les multiples initialisations dans le
for(;;), et rendre le code compatible C pour pas cher :

int fib(int valeur)
{
int reponse;
if (valeur < 3)
{
reponse = 1;
}
else
{
int compteur;
int moinsUn = 1;
int moinsDeux = 1;
for (compteur = 3;
compteur <= valeur;
compteur++)
{
reponse = moinsUn + moinsDeux;/*f(n) = f(n-1) + f(n-2)*/
/*préparation pour l'itération suivante éventuelle*/
moinsDeux = moinsUn; /*f(n-1) devient f(n-2)*/
moinsUn = reponse; /*f(n) devient f(n-1)*/
}
}
return reponse;
}

Cordialement,
Pierre




Bonjour, je vous remercie pour toutes ces réponses.

Mais mon problème était pas de savoir si mon code source était le
meilleur mais que quelqu'un m'explique le fonctionnement de la fonction
car je ne comprenais pas pourquoi par ex. la boucle for fait - 3 à
chaque fois. Et je vous demande de l'aide car mes connaisences en
mathématiques sont très limitées, je ne suis qu'à la 3 eme année à
l'école secondaire.

"Tim" <timythe@freemail.ru> a écrit...
[...]

Bonjour, je vous remercie pour toutes ces réponses.
Mais mon problème était pas de savoir si mon code source était le
meilleur mais que quelqu'un m'explique le fonctionnement de la fonction
C'est comme ça que je l'avais compris, mais j'ai un peu brodé .. comme

d'hab.

car je ne comprenais pas pourquoi par ex. la boucle for fait - 3 à
chaque fois. Et je vous demande de l'aide car mes connaisences en
mathématiques sont très limitées, je ne suis qu'à la 3 eme année à
l'école secondaire.
Ce n'est pas grave, c'est de la simple arithmétque.

La boucle ne fait pas "-3 à chaque fois". Commençons par une forme générale
(un simple exemple) :
for(ActionI; Test; ActionF){//Code}
peut s'écrire :

ActionI;
si(Test)
faire {//Code}
ActionF;
Aller au si(Test)
(sinon)
//suite du programme

Ou plus C++ :

ActionI;
while(Test)
{
{//Code}
ActionF;
}

C'est important de bien maitriser cette structure, parcequ'en réalité on
peut mettre à peu près n'importe quoi à la place de ActionI, Test, ActionF.
Reste à traduire ces trois termes dans votre cas :
for (n -= 3; n; n--)

n -= 3, c'est n = n - 3. Si vous faites fib(12), n est réinitialisé à 9, une
fois avant le début de la boucle. Il eut été équivalent mais plus lisible de
passer par une autre variable :
for(int compteur = (n - 3); compteur; compteur--)

Le test if(n) signifie if(n != 0). Dans notre cas, ça peut s'écrire if(n >
0).

n-- signifie n = (n - 1). La forme n-- est répandue, elle correspond à une
instruction comme dec dans d'autres langages.

for (n = n - 3; n > 0; n--)
{
//Code
}

ou

for (int compteur = (n - 3); compteur > 0; compteur--){//Code}

n n'est pas utilisé dans la boucle. Donc, le seul résultat est de faire
tourner {//Code} (n - 3) fois. Bien voir que {//Code} ne tourne pas pour n 0.

Pierre

Pierre Maurette wrote:

"Tim" <timythe@freemail.ru> a écrit...
[...]

Bonjour, je vous remercie pour toutes ces réponses.
Mais mon problème était pas de savoir si mon code source était le
meilleur mais que quelqu'un m'explique le fonctionnement de la fonction

C'est comme ça que je l'avais compris, mais j'ai un peu brodé .. comme
d'hab.

car je ne comprenais pas pourquoi par ex. la boucle for fait - 3 à
chaque fois. Et je vous demande de l'aide car mes connaisences en
mathématiques sont très limitées, je ne suis qu'à la 3 eme année à
l'école secondaire.

Ce n'est pas grave, c'est de la simple arithmétque.
La boucle ne fait pas "-3 à chaque fois". Commençons par une forme générale
(un simple exemple) :
for(ActionI; Test; ActionF){//Code}
peut s'écrire :

ActionI;
si(Test)
faire {//Code}
ActionF;
Aller au si(Test)
(sinon)
//suite du programme

Ou plus C++ :

ActionI;
while(Test)
{
{//Code}
ActionF;
}

C'est important de bien maitriser cette structure, parcequ'en réalité on
peut mettre à peu près n'importe quoi à la place de ActionI, Test, ActionF.
Reste à traduire ces trois termes dans votre cas :
for (n -= 3; n; n--)

n -= 3, c'est n = n - 3. Si vous faites fib(12), n est réinitialisé à 9, une
fois avant le début de la boucle. Il eut été équivalent mais plus lisible de
passer par une autre variable :
for(int compteur = (n - 3); compteur; compteur--)

Le test if(n) signifie if(n != 0). Dans notre cas, ça peut s'écrire if(n >
0).

n-- signifie n = (n - 1). La forme n-- est répandue, elle correspond à une
instruction comme dec dans d'autres langages.

for (n = n - 3; n > 0; n--)
{
//Code
}

ou

for (int compteur = (n - 3); compteur > 0; compteur--){//Code}

n n'est pas utilisé dans la boucle. Donc, le seul résultat est de faire
tourner {//Code} (n - 3) fois. Bien voir que {//Code} ne tourne pas pour n > 0.

Pierre










Grace à vous pierre, j'ai enfin compris !! 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 ?

"Tim" <timythe@freemail.ru> a écrit ..

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;

if (n < 3)
return 1;

for (n -= 3; n; n--)
{
moinsDeux = moinsUn;
moinsUn = reponse;
reponse = moinsUn + moinsDeux;
}

return reponse;
}

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.

Pierre