Toujours dans le cadre d'un exercice, je suis sur les suites de Fibonacci.
Et j'aimerais savoir au bout de combien de termes j'atteins le maximum du
type utilisé (en l'occurence, un long).
Au départ, je me suis dit que vu que la suite était croissante, si f(N+1)
était inférieur f(N), alors on avait rebouclé. Mais àa ne suffit pas.
Si mon type va de 0 à 10, on peut très bien passer de 8 à 6, tout en
rebouclant;
Cette action est irreversible, confirmez la suppression du commentaire ?
Signaler le commentaire
Veuillez sélectionner un problème
Nudité
Violence
Harcèlement
Fraude
Vente illégale
Discours haineux
Terrorisme
Autre
Pierre Maurette
Hello,
Toujours dans le cadre d'un exercice, je suis sur les suites de Fibonacci. Et j'aimerais savoir au bout de combien de termes j'atteins le maximum du type utilisé (en l'occurence, un long).
Au départ, je me suis dit que vu que la suite était croissante, si f(N+1) était inférieur f(N), alors on avait rebouclé. Mais àa ne suffit pas.
Si mon type va de 0 à 10, on peut très bien passer de 8 à 6, tout en rebouclant;
Il y a une méthode ? Merci. Vous testez :
LONG_MAX - f(N) >= f(N-1) avant chaque f(N+1) = f(N) + f(N-1) Remplacer éventuellement LONG_MAX par ULONG_MAX avec des unsigned long. Tout ça défini dans <climits>.
Pour le reste de votre raisonnement, ce qui me gêne c'est que vous parlez d'un long (donc signed). Pour des unsigned long, il est valable. La norme garantit que si le résultat est plus grand que ULONG_MAX, alors le résultat renvoyé est le résultat exact modulo ULONG_MAX + 1. A ce moment là, f(N-1) < f(N) < ULONG_MAX (inégalités strictes) fournit la preuve que (f(N-1) + f(N))%(ULONG_MAX+1) < f(N) si et seulement si il y a eu dépassement.
Pour des long, je pense qu'il y a comportement indéfini. Néanmoins, pour des entiers naturels en complément à 2 se comportant civilement, le résultat sera négatif si et seulement si on a dépassé.
Tout ceci n'est valable que si on le fait à chaque opération.
-- Pierre
Hello,
Toujours dans le cadre d'un exercice, je suis sur les suites de Fibonacci.
Et j'aimerais savoir au bout de combien de termes j'atteins le maximum du
type utilisé (en l'occurence, un long).
Au départ, je me suis dit que vu que la suite était croissante, si f(N+1)
était inférieur f(N), alors on avait rebouclé. Mais àa ne suffit pas.
Si mon type va de 0 à 10, on peut très bien passer de 8 à 6, tout en
rebouclant;
Il y a une méthode ? Merci.
Vous testez :
LONG_MAX - f(N) >= f(N-1)
avant chaque
f(N+1) = f(N) + f(N-1)
Remplacer éventuellement LONG_MAX par ULONG_MAX avec des unsigned long.
Tout ça défini dans <climits>.
Pour le reste de votre raisonnement, ce qui me gêne c'est que vous
parlez d'un long (donc signed). Pour des unsigned long, il est valable.
La norme garantit que si le résultat est plus grand que ULONG_MAX,
alors le résultat renvoyé est le résultat exact modulo ULONG_MAX + 1. A
ce moment là, f(N-1) < f(N) < ULONG_MAX (inégalités strictes) fournit
la preuve que (f(N-1) + f(N))%(ULONG_MAX+1) < f(N) si et seulement si
il y a eu dépassement.
Pour des long, je pense qu'il y a comportement indéfini. Néanmoins,
pour des entiers naturels en complément à 2 se comportant civilement,
le résultat sera négatif si et seulement si on a dépassé.
Tout ceci n'est valable que si on le fait à chaque opération.
Toujours dans le cadre d'un exercice, je suis sur les suites de Fibonacci. Et j'aimerais savoir au bout de combien de termes j'atteins le maximum du type utilisé (en l'occurence, un long).
Au départ, je me suis dit que vu que la suite était croissante, si f(N+1) était inférieur f(N), alors on avait rebouclé. Mais àa ne suffit pas.
Si mon type va de 0 à 10, on peut très bien passer de 8 à 6, tout en rebouclant;
Il y a une méthode ? Merci. Vous testez :
LONG_MAX - f(N) >= f(N-1) avant chaque f(N+1) = f(N) + f(N-1) Remplacer éventuellement LONG_MAX par ULONG_MAX avec des unsigned long. Tout ça défini dans <climits>.
Pour le reste de votre raisonnement, ce qui me gêne c'est que vous parlez d'un long (donc signed). Pour des unsigned long, il est valable. La norme garantit que si le résultat est plus grand que ULONG_MAX, alors le résultat renvoyé est le résultat exact modulo ULONG_MAX + 1. A ce moment là, f(N-1) < f(N) < ULONG_MAX (inégalités strictes) fournit la preuve que (f(N-1) + f(N))%(ULONG_MAX+1) < f(N) si et seulement si il y a eu dépassement.
Pour des long, je pense qu'il y a comportement indéfini. Néanmoins, pour des entiers naturels en complément à 2 se comportant civilement, le résultat sera négatif si et seulement si on a dépassé.
Tout ceci n'est valable que si on le fait à chaque opération.
-- Pierre
Pierre Maurette
Hello,
Toujours dans le cadre d'un exercice, je suis sur les suites de Fibonacci. Et j'aimerais savoir au bout de combien de termes j'atteins le maximum du type utilisé (en l'occurence, un long).
Au départ, je me suis dit que vu que la suite était croissante, si f(N+1) était inférieur f(N), alors on avait rebouclé. Mais àa ne suffit pas.
Si mon type va de 0 à 10, on peut très bien passer de 8 à 6, tout en rebouclant;
Il y a une méthode ? Merci. Vous testez :
LONG_MAX - f(N) >= f(N-1) avant chaque f(N+1) = f(N) + f(N-1) Remplacer éventuellement LONG_MAX par ULONG_MAX avec des unsigned long. Tout ça défini dans <climits>.
Pour le reste de votre raisonnement, ce qui me gêne c'est que vous parlez d'un long (donc signed). Pour des unsigned long, il est valable. La norme garantit que si le résultat est plus grand que ULONG_MAX, alors le résultat renvoyé est le résultat exact modulo ULONG_MAX + 1. A ce moment là, f(N-1) < f(N) < ULONG_MAX (inégalités strictes) fournit la preuve que (f(N-1) + f(N))%(ULONG_MAX+1) < f(N) si et seulement si il y a eu dépassement.
Pour des long, je pense qu'il y a comportement indéfini. Néanmoins, pour des entiers naturels en complément à 2 se comportant civilement, le résultat sera négatif si et seulement si on a dépassé.
Tout ceci n'est valable que si on le fait à chaque opération.
-- Pierre
Hello,
Toujours dans le cadre d'un exercice, je suis sur les suites de Fibonacci.
Et j'aimerais savoir au bout de combien de termes j'atteins le maximum du
type utilisé (en l'occurence, un long).
Au départ, je me suis dit que vu que la suite était croissante, si f(N+1)
était inférieur f(N), alors on avait rebouclé. Mais àa ne suffit pas.
Si mon type va de 0 à 10, on peut très bien passer de 8 à 6, tout en
rebouclant;
Il y a une méthode ? Merci.
Vous testez :
LONG_MAX - f(N) >= f(N-1)
avant chaque
f(N+1) = f(N) + f(N-1)
Remplacer éventuellement LONG_MAX par ULONG_MAX avec des unsigned long.
Tout ça défini dans <climits>.
Pour le reste de votre raisonnement, ce qui me gêne c'est que vous
parlez d'un long (donc signed). Pour des unsigned long, il est valable.
La norme garantit que si le résultat est plus grand que ULONG_MAX,
alors le résultat renvoyé est le résultat exact modulo ULONG_MAX + 1. A
ce moment là, f(N-1) < f(N) < ULONG_MAX (inégalités strictes) fournit
la preuve que (f(N-1) + f(N))%(ULONG_MAX+1) < f(N) si et seulement si
il y a eu dépassement.
Pour des long, je pense qu'il y a comportement indéfini. Néanmoins,
pour des entiers naturels en complément à 2 se comportant civilement,
le résultat sera négatif si et seulement si on a dépassé.
Tout ceci n'est valable que si on le fait à chaque opération.
Toujours dans le cadre d'un exercice, je suis sur les suites de Fibonacci. Et j'aimerais savoir au bout de combien de termes j'atteins le maximum du type utilisé (en l'occurence, un long).
Au départ, je me suis dit que vu que la suite était croissante, si f(N+1) était inférieur f(N), alors on avait rebouclé. Mais àa ne suffit pas.
Si mon type va de 0 à 10, on peut très bien passer de 8 à 6, tout en rebouclant;
Il y a une méthode ? Merci. Vous testez :
LONG_MAX - f(N) >= f(N-1) avant chaque f(N+1) = f(N) + f(N-1) Remplacer éventuellement LONG_MAX par ULONG_MAX avec des unsigned long. Tout ça défini dans <climits>.
Pour le reste de votre raisonnement, ce qui me gêne c'est que vous parlez d'un long (donc signed). Pour des unsigned long, il est valable. La norme garantit que si le résultat est plus grand que ULONG_MAX, alors le résultat renvoyé est le résultat exact modulo ULONG_MAX + 1. A ce moment là, f(N-1) < f(N) < ULONG_MAX (inégalités strictes) fournit la preuve que (f(N-1) + f(N))%(ULONG_MAX+1) < f(N) si et seulement si il y a eu dépassement.
Pour des long, je pense qu'il y a comportement indéfini. Néanmoins, pour des entiers naturels en complément à 2 se comportant civilement, le résultat sera négatif si et seulement si on a dépassé.
Tout ceci n'est valable que si on le fait à chaque opération.
-- Pierre
Jean-Marc Bourguet
Dudule writes:
Au départ, je me suis dit que vu que la suite était croissante, si f(N+1) était inférieur f(N), alors on avait rebouclé. Mais àa ne suffit pas.
Loin de la. Si tu utilises un type signe, le comportement devient indefini, il n'est pas garanti que ca va boucler (mais c'est bien ce qui se passe sur la plupart des machines).
Il y a une méthode ? Merci.
Tester avant l'addition. Genre
if (std::numeric_limits<long>::max() - f1 < f2) { traite le depassement } else { long tmp = f2; f2 = f1; f1 += tmp; }
A+
-- Jean-Marc FAQ de fclc++: http://www.cmla.ens-cachan.fr/~dosreis/C++/FAQ C++ FAQ Lite en VF: http://www.ifrance.com/jlecomte/c++/c++-faq-lite/index.html Site de usenet-fr: http://www.usenet-fr.news.eu.org
Dudule <nospam_svdbg_nospam@free.fr> writes:
Au départ, je me suis dit que vu que la suite était croissante, si f(N+1)
était inférieur f(N), alors on avait rebouclé. Mais àa ne suffit pas.
Loin de la. Si tu utilises un type signe, le comportement devient
indefini, il n'est pas garanti que ca va boucler (mais c'est bien ce
qui se passe sur la plupart des machines).
Il y a une méthode ? Merci.
Tester avant l'addition. Genre
if (std::numeric_limits<long>::max() - f1 < f2) {
traite le depassement
} else {
long tmp = f2;
f2 = f1;
f1 += tmp;
}
A+
--
Jean-Marc
FAQ de fclc++: http://www.cmla.ens-cachan.fr/~dosreis/C++/FAQ
C++ FAQ Lite en VF: http://www.ifrance.com/jlecomte/c++/c++-faq-lite/index.html
Site de usenet-fr: http://www.usenet-fr.news.eu.org
Au départ, je me suis dit que vu que la suite était croissante, si f(N+1) était inférieur f(N), alors on avait rebouclé. Mais àa ne suffit pas.
Loin de la. Si tu utilises un type signe, le comportement devient indefini, il n'est pas garanti que ca va boucler (mais c'est bien ce qui se passe sur la plupart des machines).
Il y a une méthode ? Merci.
Tester avant l'addition. Genre
if (std::numeric_limits<long>::max() - f1 < f2) { traite le depassement } else { long tmp = f2; f2 = f1; f1 += tmp; }
A+
-- Jean-Marc FAQ de fclc++: http://www.cmla.ens-cachan.fr/~dosreis/C++/FAQ C++ FAQ Lite en VF: http://www.ifrance.com/jlecomte/c++/c++-faq-lite/index.html Site de usenet-fr: http://www.usenet-fr.news.eu.org
Dudule
Pierre Maurette wrote:
Vous testez : LONG_MAX - f(N) >= f(N-1) avant chaque f(N+1) = f(N) + f(N-1) Remplacer éventuellement LONG_MAX par ULONG_MAX avec des unsigned long. Tout ça défini dans <climits>.
Merci !
Pour le reste de votre raisonnement, ce qui me gêne c'est que vous parlez d'un long (donc signed). Pour des unsigned long, il est valable.
Je parlais effectivement d'un unsigned long.
Pierre Maurette wrote:
Vous testez :
LONG_MAX - f(N) >= f(N-1)
avant chaque
f(N+1) = f(N) + f(N-1)
Remplacer éventuellement LONG_MAX par ULONG_MAX avec des unsigned long.
Tout ça défini dans <climits>.
Merci !
Pour le reste de votre raisonnement, ce qui me gêne c'est que vous
parlez d'un long (donc signed). Pour des unsigned long, il est valable.
Vous testez : LONG_MAX - f(N) >= f(N-1) avant chaque f(N+1) = f(N) + f(N-1) Remplacer éventuellement LONG_MAX par ULONG_MAX avec des unsigned long. Tout ça défini dans <climits>.
Merci !
Pour le reste de votre raisonnement, ce qui me gêne c'est que vous parlez d'un long (donc signed). Pour des unsigned long, il est valable.
Toujours dans le cadre d'un exercice, je suis sur les suites de Fibonacci. Et j'aimerais savoir au bout de combien de termes j'atteins le maximum du type utilisé (en l'occurence, un long).
Au départ, je me suis dit que vu que la suite était croissante, si f(N+1) était inférieur f(N), alors on avait rebouclé. Mais àa ne suffit pas.
Si mon type va de 0 à 10, on peut très bien passer de 8 à 6, tout en rebouclant;
Il y a une méthode ? Merci.
Pour une suite croissante, le critère à évaluer est la différence entre le prochain accroissement et la réserve de capacité du type. Si la réserve est calculable par soustraction à partir de la constante adéquate de limits.h, par contre pour le prochain accroissement, soit on en dispose, soit il faut calculer la prochaine valeur et de soustraire la valeur courante : on déborde en faisant le test (à moins de le faire dans un autre type de capacité suffisante).
Puisque vous travaillez sur une suite pour laquelle la formule de récurrence s'écrit explicitement f(n+1) = f(n) + f(n-1), vous disposez déjà du prochain accroissement avec f(n-1). Par contre avec une factorielle par exemple, ce serait plus difficile.
Donc AMHA, c'est faisable avec une telle suite, mais avec d'autres ça reste un problème transcendant au codage, donc relevant de l'intelligence du concepteur du code, non transférable.
Cordialement,
A part ça, ceci ne relève pas trop du langage C++, de C tout au plus.
-- /*************************************** * Patrick BRUNET * E-mail: lien sur http://zener131.free.fr/ContactMe ***************************************/
Bonjour.
Hello,
Toujours dans le cadre d'un exercice, je suis sur les suites de
Fibonacci. Et j'aimerais savoir au bout de combien de termes
j'atteins le maximum du type utilisé (en l'occurence, un long).
Au départ, je me suis dit que vu que la suite était croissante, si
f(N+1) était inférieur f(N), alors on avait rebouclé. Mais àa ne
suffit pas.
Si mon type va de 0 à 10, on peut très bien passer de 8 à 6, tout en
rebouclant;
Il y a une méthode ? Merci.
Pour une suite croissante, le critère à évaluer est la différence entre le
prochain accroissement et la réserve de capacité du type.
Si la réserve est calculable par soustraction à partir de la constante
adéquate de limits.h, par contre pour le prochain accroissement, soit on en
dispose, soit il faut calculer la prochaine valeur et de soustraire la
valeur courante : on déborde en faisant le test (à moins de le faire dans un
autre type de capacité suffisante).
Puisque vous travaillez sur une suite pour laquelle la formule de récurrence
s'écrit explicitement f(n+1) = f(n) + f(n-1), vous disposez déjà du prochain
accroissement avec f(n-1). Par contre avec une factorielle par exemple, ce
serait plus difficile.
Donc AMHA, c'est faisable avec une telle suite, mais avec d'autres ça reste
un problème transcendant au codage, donc relevant de l'intelligence du
concepteur du code, non transférable.
Cordialement,
A part ça, ceci ne relève pas trop du langage C++, de C tout au plus.
--
/***************************************
* Patrick BRUNET
* E-mail: lien sur http://zener131.free.fr/ContactMe
***************************************/
Toujours dans le cadre d'un exercice, je suis sur les suites de Fibonacci. Et j'aimerais savoir au bout de combien de termes j'atteins le maximum du type utilisé (en l'occurence, un long).
Au départ, je me suis dit que vu que la suite était croissante, si f(N+1) était inférieur f(N), alors on avait rebouclé. Mais àa ne suffit pas.
Si mon type va de 0 à 10, on peut très bien passer de 8 à 6, tout en rebouclant;
Il y a une méthode ? Merci.
Pour une suite croissante, le critère à évaluer est la différence entre le prochain accroissement et la réserve de capacité du type. Si la réserve est calculable par soustraction à partir de la constante adéquate de limits.h, par contre pour le prochain accroissement, soit on en dispose, soit il faut calculer la prochaine valeur et de soustraire la valeur courante : on déborde en faisant le test (à moins de le faire dans un autre type de capacité suffisante).
Puisque vous travaillez sur une suite pour laquelle la formule de récurrence s'écrit explicitement f(n+1) = f(n) + f(n-1), vous disposez déjà du prochain accroissement avec f(n-1). Par contre avec une factorielle par exemple, ce serait plus difficile.
Donc AMHA, c'est faisable avec une telle suite, mais avec d'autres ça reste un problème transcendant au codage, donc relevant de l'intelligence du concepteur du code, non transférable.
Cordialement,
A part ça, ceci ne relève pas trop du langage C++, de C tout au plus.
-- /*************************************** * Patrick BRUNET * E-mail: lien sur http://zener131.free.fr/ContactMe ***************************************/
Dudule
Patrick 'Zener' Brunet wrote:
Donc AMHA, c'est faisable avec une telle suite, mais avec d'autres ça reste un problème transcendant au codage, donc relevant de l'intelligence du concepteur du code, non transférable.
C'est effectivement la conclusion à laquelle je suis finalement arrivé. Merci pour l"exposé. :-)
A part ça, ceci ne relève pas trop du langage C++, de C tout au plus.
Cela ne relève en fait d'aucun langage particulier... Désolé :-(
Patrick 'Zener' Brunet wrote:
Donc AMHA, c'est faisable avec une telle suite, mais avec d'autres ça
reste un problème transcendant au codage, donc relevant de l'intelligence
du concepteur du code, non transférable.
C'est effectivement la conclusion à laquelle je suis finalement arrivé.
Merci pour l"exposé. :-)
A part ça, ceci ne relève pas trop du langage C++, de C tout au plus.
Cela ne relève en fait d'aucun langage particulier...
Désolé :-(
Donc AMHA, c'est faisable avec une telle suite, mais avec d'autres ça reste un problème transcendant au codage, donc relevant de l'intelligence du concepteur du code, non transférable.
C'est effectivement la conclusion à laquelle je suis finalement arrivé. Merci pour l"exposé. :-)
A part ça, ceci ne relève pas trop du langage C++, de C tout au plus.
Cela ne relève en fait d'aucun langage particulier... Désolé :-(
Dudule
Dudule wrote:
A part ça, ceci ne relève pas trop du langage C++, de C tout au plus.
Cela ne relève en fait d'aucun langage particulier... Désolé :-(
Quoique si. Quand j'ai posé la question, j'ai pensé qu'il pouvait exister une classe/fonction du C++ standart qui aurait pu faire le boulot pour moi. :-)
Dudule wrote:
A part ça, ceci ne relève pas trop du langage C++, de C tout au plus.
Cela ne relève en fait d'aucun langage particulier...
Désolé :-(
Quoique si.
Quand j'ai posé la question, j'ai pensé qu'il pouvait exister une
classe/fonction du C++ standart qui aurait pu faire le boulot pour moi. :-)
A part ça, ceci ne relève pas trop du langage C++, de C tout au plus.
Cela ne relève en fait d'aucun langage particulier... Désolé :-(
Quoique si. Quand j'ai posé la question, j'ai pensé qu'il pouvait exister une classe/fonction du C++ standart qui aurait pu faire le boulot pour moi. :-)
