Signaler

PGCD RÉCURSIF

Messages postés
455
Date d'inscription
mercredi 6 mars 2002
Statut
Membre
Dernière intervention
18 décembre 2003
 - - Dernière réponse : loraine9999
Messages postés
6
Date d'inscription
dimanche 12 janvier 2003
Statut
Membre
Dernière intervention
23 janvier 2003
 - 16 janv. 2003 à 18:12
Commentaires sur une source Signaler
Cette discussion concerne un article du site. Pour la consulter dans son contexte d'origine, cliquez sur le lien ci-dessous.

https://codes-sources.commentcamarche.net/source/10289-pgcd-recursif

Signaler
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 ;
Signaler
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
Signaler
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 ;-)
Signaler
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... ;-)