ALGORITHME D'EUCLIDE ETENDU
Cyberboy2054
Messages postés
173
Date d'inscription
jeudi 20 décembre 2001
Statut
Membre
Dernière intervention
22 août 2008
-
6 mars 2006 à 18:46
svenstek Messages postés 5 Date d'inscription jeudi 8 mai 2008 Statut Membre Dernière intervention 17 mars 2010 - 11 févr. 2009 à 00:16
svenstek Messages postés 5 Date d'inscription jeudi 8 mai 2008 Statut Membre Dernière intervention 17 mars 2010 - 11 févr. 2009 à 00:16
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/36400-algorithme-d-euclide-etendu
https://codes-sources.commentcamarche.net/source/36400-algorithme-d-euclide-etendu
11 févr. 2009 à 00:16
7 mars 2006 à 21:22
Merci Pamaury , pour ton commentaire.
7 mars 2006 à 18:50
7 mars 2006 à 12:42
Merci et aurevoir
7 mars 2006 à 10:33
7 mars 2006 à 10:21
>
"""
Ecris ton calcul de pgcd en itératif, c'est bien mieux et pas plus dur:
template<class T>
void Swap (T& a, T& b)
{
T c = b;
b = a;
a = c;
}
int pgcd (int a, int b)
{
int c = 1;
if (a < b)
Swap (a,b); // met le plus grand nombre dans a
while (1)
{
c = a%b;
if (c== 0)
return b;
a = b;
b= c;
}
return -1; // on est jamais a l'abris d'une boulette
}
"""
dans le code>
"""
# int find_pgcd(int a , int b)
# {
# if(a==0)
# return b;
# if(a<b)
# return find_pgcd(b%a,a);
# else
# return find_pgcd(a%b,b);
# }
"""
En quoi c'est mieux de faire de l'itératif ?
En tout cas ca simplifie pas le problème...
J'attends la réponse avec la plus grande impatience :p
6 mars 2006 à 21:44
BezoutFactors GetBezoutFactors(int a,int b)
{
//printf("pgcd(%d,%d)=%d\n",a,b,GetPgcd(a,b));
//printf("%d %% %d = %d\n",a,b,a%b);
if(b==0)
return BezoutFactors(1,-1);
if((a%b)==GetPgcd(a,b))
return BezoutFactors(1,-(a/b));
int mult=a/b;
BezoutFactors factors=GetBezoutFactors(b,a%b);
//printf("a=%d b=%d mult=%d facts: %d %d\n",a,b,mult,factors.first,factors.second);
return BezoutFactors(factors.second,-factors.second*mult+factors.first);
}
Cela ressemble un peu à ton algo amsi en beaucoup moins compliqué il me semble .
Et cela marche parfaitement d'après mes test.
Bonne soirée
6 mars 2006 à 21:33
tant que le reste c de la division euclidienne de a par b n'est pas nul, on met b dans a et c dans b, sinon, on renvoit b
Je trouve pas ca plus difficile qu'une fonction récursive, si bien sur c'est détaillé... Apres va falloir que tu m'explique en quoi ta fonction de calcul du pgcd ( find_pgcd ) est plus commentée que la mienne :)
Par contre, je ne savais pas que le pgcd n'etait pas limité qu'aux entiers. J'ai pas trop le temps de chercher la dessus, mais est ce que tu peux détailler un peu plus stp ? Je suis curieux de voir qu'elles applications cela peut avoir. En cryptographie, les entiers (meme s'ils sont tres grands) suffisent il me semble...
6 mars 2006 à 21:02
Cyberboy2054 , Merci pour ta critique mais ce site est destine a la comprehension des algorithmes , si j'avais mis une version beaucoup plus compliquee et moins commentee en serais - tu satisfait? et je tiens a te dire que le pgcd ne se limite pas a des entiers en passant.
Merci et aurevoir
6 mars 2006 à 18:51
6 mars 2006 à 18:46
template<class T>
void Swap (T& a, T& b)
{
T c = b;
b = a;
a = c;
}
int pgcd (int a, int b)
{
int c = 1;
if (a < b)
Swap (a,b); // met le plus grand nombre dans a
while (1)
{
c = a%b;
if (c== 0)
return b;
a = b;
b= c;
}
return -1; // on est jamais a l'abris d'une boulette
}