Je suis en train d'etudier en la complexité d'un algorithme, on compare les différences entre une fonction récursive et une fonction itérative.
Pour essayer, j'ai donc réaliser une fonction permettant de calculer la somme des N premiers entiers, comme prévu, lors de tests avec des nombres plus grand, je me retrouve rapidement avec un depassement de capacité, et changer le type de la variable ne fait que repousser le pb.
J'aimerais donc savoir s'il existe une solution pour éviter ou prévoir ce dépassement de capacité (en C, je précise), car je me vois mal tester à partir de quel nombre le programme va planter, surtout que les 2 méthodes n'utilisent pas les mêmes ressources...
Il existe des librairies comme GMP qui proposent des nombres extrêmement grands.
Mais a part pour certains cas bien précis, il n'est pas commun de manipuler des nombres aussi grands (4 milliards pour les entiers 32 bits, et 4 milliards au carré pour les nombres 64 bits)
Peut-être devrais-tu tester les fonction récursives et itératives avec autre chose que la somme des N premiers entiers ? Je pense par exemple au calcul de la moyenne, qui peut être fait itérativement ou récursivement, et qui ne nécessite pas de calculer la somme (oui c'est la définition, mais il y a moyen de calculer autrement).
Bonjour à vous, tout d'abord merci pour vos reponses !
Oui j'ai vu qu'il existait une librairie comme celle-ci mais mon but est plus de savoir comment gérer 'les exceptions', j'ai beau chercher, avec le C, le try/catch n'existe pas et donc je suis un peu perdu...(étant plus habitué au java où tt est controlé)
Robun, oui je pourrais essayer sur d'autres, c'est juste que là c'était la fonction à faire pour cet exercice, le prof ne nous a pas demandé de nous occuper de ces valeurs max mais par principe j'aimerais bien savoir comment faire pour que mon code soit 'robuste' à ce type d'erreur.
Alors une division par zero balancer une exception (en C++ ou en Java) mais un overflow en crée t il ? En C, je ne suis pas sur que ça puisse etre détecté proprement (en tout cas, pas de façon standard). Et en Java c'est détecté ?
En assembleur x86, je sais qu'un flag est levé en cas d'overflow, mais je ne sais pas si le C - qui fait abstraction des CPU - permet de le détecter.
Alors pour répondre à ta question, oui l'overflow lève une exception en Java
D'accord donc sinon si je comprend bien, on a pas vraiment moyen d'en detecter un de manière standard...d'accord c'est ce que j'avais cru comprendre mais ça me semblait bizarre, bon ba je vais fixé un entier a pas dépasser alors !
Mettons qu'on n'additionne que des nombres positifs de type 'unsigned'. On pourrait utiliser ce genre de fonction (je n'ai pas testé, c'est juste une idée) :
bool addition(unsigned a, unsigned b, unsigned *s)
/* calcule a + b et le range dans la variable pointée par s */
/* retourne true si la somme calculée est valide, false sinon */
{
*s = a + b ; // valide si et seulement si a+b <= UINT_MAX
return (b <= UINT_MAX - a) ; // càd ssi b <= UINT_MAX-a (qui est forcément un unsigned valide)
}
Pour prévenir l'overflow tu pourrais faire un truc de ce genre :
#include <stdio.h>
#include <limits.h>
int main(void)
{
int i = 0;
int sum = 0;
while(sum < INT_MAX - i)
sum += i++;
printf("i=%d sum=%d\n", i, sum);
return 0;
}
Ooh magma ! Merci t'es un champion ! J'avoue ne pas y avoir pensé, ma boucle tournait dans l'autre sens, je l'ai donc modifié et ça marche impec, le programme s’arrête proprement s'il y a dépassement de capacité
Encore merci à vous !
ps : Robun ta méthode est pas un peu lourde ?
EDIT : l'un de vous sait comment vérifier la valeur pour une fonction récursive ? (je sais je connais pas grand chose )
- Edité par Murdock93 23 septembre 2017 à 17:53:36
Pas faux en effet, c'est vrai c'est que souvent pour moi une fonction c'est plus lourd alors qu'en fait pas forcément^^
Du coup dernière question je pense, est-ce que tu connais un moyen pour tester la valeur d'une fonction récursive ? (j'ai l'impression qu'on ne peut pas vu que chaque op est en attente...)
Je viens d'essayer d'écrire une telle fonction récursive, je ne l'ai pas essayée donc peut-être qu'elle ne marche pas, c'est juste pour illustrer l'idée.
bool somme(unsigned n, unsigned *resultat)
/* Renvoie la somme des entiers de 0 à n dans la variable
pointée par resultat.
En cas de dépassement de capacité, retourne false, sinon true */
{
if (n == 0) // condition d'arrêt
{
*resultat = 0 ; // somme de 0 à 0
return true ;
}
else // on va utiliser la récursivité
{
unsigned *r ; // résultat intermédiaire : somme de 0 à n-1
if ((somme(n-1, r) // pas de dépassement de capacité jusque n-1
&& (*r <= UINT_MAX - n)) // donc *r + n <= UINT_MAX
{
*resultat = *r + n ;
return true ;
}
else // dépassement de capacité
{
return false ;
}
}
}
Je pense avoir compris ta fonction...hormis le fait que tu utilises des pointeurs. Est-il vraiment nécessaire de passer par des pointeurs ?
Et une autre question...je n'arrive pas a savoir si le résultat est vraiment calculé avec ta fonction ou si nous vérifions que ce calcul est réalisable ?
La fonction retourne un booléen qui indique s'il y a eu dépassement ou non de capacité. Donc le résultat de l'addition doit forcément passer par adresse, c'est-à-dire via un pointeur. Une autre façon de faire aurait été de retourner le résultat de l'addition, et de passer le booléen par adresse. Puisqu'il faut retourner deux choses (le résultat du calcul et le booléen indiquant si c'est OK), forcément l'un des deux doit être passé par adresse via un pointeur. J'ai préféré la première solution car, en général, les fonctions qui gèrent des erreurs retournent les codes d'erreur.
La fonction que j'ai écrite, si elle fait bien ce que je crois (mais c'est à vérifier), réalise le calcul de la somme (et retourne un booléen qui indique si on a dépassé la limite ‒ si on l'a dépassée (else de la ligne 20), le dernier calcul n'est pas effectué).
Pour tester un dépassement suite à une addition de non signés, il y a plus optimum. On utilise le fait que (a+b)>=a et (a+b)>=bSSIil n'y a pas dépassement. Ce qui donne :
bool somme( unsigned n , unsigned *res ) {
if ( n == 0 ) {
*res = 0;
return true;
}
bool ok = somme( n-1 , res );
*res += n;
return ok && (*res >= n);
}
Mais ici on parcourra toute la hiérarchie. Tous les appels à somme seront effectués N fois. On ne détecte le dépassement de capacité qu'à la fin. Pour éviter cela il faut changer le prototype de la fonction.
Wow merci pour toutes vos réponses ! Je réponds un peu tard mais je vais essayer vos méthodes, Robun merci pour l'explication, c'est désormais plus clairs ! En effet, ça revient au même que si l'on avait passé une variable par adresse.
Mad Scientist, ta méthode est encore un peu flou pour moi, je n'ai pas encore bc etudié cette partie du C.
Bonjour asmaadaho, tout d'abord déterrer un sujet de plus d'un an n'est pas vraiment conseillé, tu ferais mieux de créer ton propre sujet
Et surtout, développes ton problème ! Parce que "un programme qui calcule la capacité d'un algorithme" n'est pas vraiment très explicite...
Dépassement de capacité en C
× Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
× Attention, ce sujet est très ancien. Le déterrer n'est pas forcément approprié. Nous te conseillons de créer un nouveau sujet pour poser ta question.
Recueil de code C et C++ http://fvirtman.free.fr/recueil/index.html
Recueil de code C et C++ http://fvirtman.free.fr/recueil/index.html
En recherche d'emploi.