Pgcd récursif

Soyez le premier à donner votre avis sur cette source.

Snippet vu 13 371 fois - Téléchargée 35 fois

Contenu du snippet

calcul du PGCD en récursif
  • Remarques : le pgcd de 2 nombres a et b, avec a >=b, peut etre défini de la

facon suivante : il est egal a b si b divise a.
sinon il est egal au pgcd de 'b' et de 'a mod b'

Source / Exemple :


#pragma hdrstop

#pragma argsused

#include <conio.h>
#include <iomanip.h>
#include <iostream.h>

int pgcd(int a, int b) ;

void main(void)
    {
    int nb1, nb2 ;
    int ret ;

    cout << "entrez le 1er nombre : " ;
    cin >> nb1 ;

    cout << endl << "entrez le 2eme nombre : " ;
    cin >> nb2 ;

    ret = pgcd(nb1, nb2) ;

    cout << endl << "le pgcd de " << nb1 << " et " << nb2 << " est : " << ret ;

    cout << endl << endl << "appuyer sur une touche pour terminer..." ;
    getch() ;
    }
//---------------------------------------------------------------------------

int pgcd(int a, int b)
    {
    if (a % b == 0)
        return b ;

    return pgcd(b, a % b) ;
    }

A voir également

Ajouter un commentaire

Commentaires

cmarsc
Messages postés
455
Date d'inscription
mercredi 6 mars 2002
Statut
Membre
Dernière intervention
18 décembre 2003
-
#pragma hdrstop #pragma argsused sont - ils indispensables
#include ne sert pas à grand chose
void main(void) return ;
cs_GoldenEye
Messages postés
527
Date d'inscription
vendredi 14 septembre 2001
Statut
Membre
Dernière intervention
6 octobre 2008
2 -
Mêmes remarques que mon collègue.
Petite astuce d'optimisation : tu sais que l'opération modulo est très coûteuse en termes de temps de calcul dans la mesure où elle fait intervenir une division. Or tu calcules deux fois a%b dans ta fonction PGCD. Sauve le premier calcul dans une variable auxiliaire que tu réutiliseras afin de ne pas refaire le même calcul une seconde fois

int pgcd(int a, int b)
{
int temp;
if ((temp=a % b) == 0)
return b ;

return pgcd(b, temp) ;
}

Par ailleurs, tu m'as l'air d'être un(e) maniaque de la récursivité (c'est peut-être ton programme actuel de cours :-)). Si l'élégance de la méthode est incontestable, ses performances le sont moins (sauf dans des cas particuliers. En l'occurence ici, la méthode itérative du calcul de PGCD (l'algorithme d'Euclide) est plus performante.

Voilà pour cette fois
cs_GoldenEye
Messages postés
527
Date d'inscription
vendredi 14 septembre 2001
Statut
Membre
Dernière intervention
6 octobre 2008
2 -
Autre chose, vive la compacité du C:

int pgcd(int a,int b)
{
int temp;
return((!(temp=a%b))?b:pgcd(b,temp));
}

Juste pour le clin d'oeil ;-)
loraine9999
Messages postés
6
Date d'inscription
dimanche 12 janvier 2003
Statut
Membre
Dernière intervention
23 janvier 2003
-
hé oui c est la récursivité en puissance en cours ces temps ci alors je fais partager... ;-)

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.