Bonjour tout le monde,

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...

Je vous remercie d 'avance pour votre aide !

Salut,

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.

Salut,

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.

Salut Fvirtman,

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 !

Merci à tous pour votre aide en tt cas !

Tu peux utiliser les constantes prédéfinies dans <limits.h> comme INT_MAX : http://www.tutorialspoint.com/c_standard_library/limits_h.htm

Oui j'y ais pensé mais de toute façon je ne pourrais pas m en servir, je doute que :

if(resultat >= INT_MAX) fonctionne correctement, à moins que j'ai raté quelque chose

Ou alors il faut bricoler...

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)
}

-
Edité par robun 23 septembre 2017 à 12:21:03

Salut,

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;
}

...

-
Edité par magma 23 septembre 2017 à 14:12:14

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

> ps : Robun ta méthode est pas un peu lourde ?

C'est exactement la même que celle de magma (le copieur ), sauf que j'en ai fait une fonction et que j'ai mis des commentaires.

-
Edité par robun 23 septembre 2017 à 17:56:10

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 ;
        }
    }
}

-
Edité par robun 23 septembre 2017 à 18:29:11

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é).

-
Edité par robun 23 septembre 2017 à 23:04:15

On peut faire la même chose sans pointeurs en utilisant une structure:

#include <limits.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>

struct overflow
{
    unsigned int value;
    bool flag;
};

static struct overflow
overflow_make(unsigned int n)
{
    return (struct overflow)
    {
        .value = n
    };
}

static struct overflow
overflow_add(struct overflow a, struct overflow b)
{
    return (struct overflow)
    {
        .value = a.value + b.value,
        .flag = a.flag || b.flag || b.value > UINT_MAX - a.value
    };
}

static struct overflow
overflow_sum(unsigned int n)
{
    if (n == 0)
    {
        return overflow_make(0);
    }

    return overflow_add
    (
        overflow_sum(n - 1),
        overflow_make(n)
    );
}

int
main(void)
{   
    unsigned int i;
    
    for (i = 0; i < UINT_MAX; ++i)
    {   
        struct overflow sum = overflow_sum(i);
        
        if (sum.flag)
        {   
            break;
        }
        
        if (printf("sum(%u) = %u.\n", i, sum.value) < 0)
        {   
            perror("printf");
            return EXIT_FAILURE;
        }
    }
    
    if (printf("sum(%u) overflows !\n", i) < 0)
    {   
        perror("printf");
        return EXIT_FAILURE;
    }   
    
    if (fflush(stdout) == EOF)
    {   
        perror("fflush");
        return EXIT_FAILURE;
    }
}

-
Edité par Mad scientist 24 septembre 2017 à 1:50:09

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)>=b SSI il 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.

-
Edité par Dalfab 24 septembre 2017 à 12:07:28

Astucieux ! (J'ai dû faire quelques essais pour me persuader de la propriété...)

-
Edité par robun 24 septembre 2017 à 12:33:25

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.

Edit : Dalfab, j'essaie ta méthode de suite !

bonjour, j'ai besoin d'un programme qui calcule la capacité d'un algorithme en c ++ svp c urgent et merci

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...