Cyberboy2054
Messages postés173Date d'inscriptionjeudi 20 décembre 2001StatutMembreDernière intervention22 août 2008
-
6 mars 2006 à 18:46
svenstek
Messages postés5Date d'inscriptionjeudi 8 mai 2008StatutMembreDernière intervention17 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.
svenstek
Messages postés5Date d'inscriptionjeudi 8 mai 2008StatutMembreDernière intervention17 mars 2010 11 févr. 2009 à 00:16
Bonjour je cherche a ecrire un programme en C qui permet de calculer le pgcd de deux nombres quelconques et de aussi de calculer les coefficients de Bezout avez vous une idée ?
nickydaquick
Messages postés416Date d'inscriptionvendredi 31 janvier 2003StatutMembreDernière intervention19 décembre 20133 7 mars 2006 à 21:22
Merci Pamaury. Ton algorithme est en effet tres efficace. Je dirais meme que C'est l'algorithme pour les coefficients de Bezout. Moi j'ai en fait tente une autre approche en utilisant une formule tire d'une recurrence par des suites numeriques.
Merci Pamaury , pour ton commentaire.
Pamaury
Messages postés341Date d'inscriptionjeudi 3 avril 2003StatutMembreDernière intervention17 juin 20083 7 mars 2006 à 18:50
moi je t'ai mis un algo dans mon précédent message et il me semble qu'il est plus simple que le tiens mais je me trompe . En tout cas il est en récursif .
nickydaquick
Messages postés416Date d'inscriptionvendredi 31 janvier 2003StatutMembreDernière intervention19 décembre 20133 7 mars 2006 à 12:42
Merci pour tous vos commentaires ... Je suis d'avis avec vous que le recursif est plus couteux que l'iteratif . Seulement comme l'indique le titre de ma source mon but n'est pas d'ecrire une fonction trouver_pgcd , mais trouver les coefficients de Bezout grace a l'algorithme d'euclide etendu. J'aimerais bien avoir des commentaires la dessus. Et en passant , trouver un pgcd c faire des soustractions successives :D . J'attends vos commentaires avec impatience sur mon algorithme d'euclide Etendu.
Merci et aurevoir
BruNews
Messages postés21040Date d'inscriptionjeudi 23 janvier 2003StatutModérateurDernière intervention21 août 2019 7 mars 2006 à 10:33
La récurrence implique des passages de params et appels de fonction, l'empilage des params est très couteux. Un algo en itératif correctement écrit DOIT être plus performant car il n'a pas tout ces emplilages dépilages.
DormeurDev
Messages postés61Date d'inscriptionsamedi 5 février 2005StatutMembreDernière intervention20 avril 20061 7 mars 2006 à 10:21
Cyberboy2054
>
"""
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
Pamaury
Messages postés341Date d'inscriptionjeudi 3 avril 2003StatutMembreDernière intervention17 juin 20083 6 mars 2006 à 21:44
Cyberboy: ton Swap est inutile car si a BezoutFactors;
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
Cyberboy2054
Messages postés173Date d'inscriptionjeudi 20 décembre 2001StatutMembreDernière intervention22 août 2008 6 mars 2006 à 21:33
Expliquer l'algorithme d'euclide c'est pas dur,
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...
nickydaquick
Messages postés416Date d'inscriptionvendredi 31 janvier 2003StatutMembreDernière intervention19 décembre 20133 6 mars 2006 à 21:02
Merci pour vos commentaires. Pamaury, tu as absolument raison Les coefficients de Bezout sont x et y tels que ax+by = pgcd(a,b); seulement ils sont trouves ( ou resolus) grace a l'algorithme d'Euclide Etendu.
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
Pamaury
Messages postés341Date d'inscriptionjeudi 3 avril 2003StatutMembreDernière intervention17 juin 20083 6 mars 2006 à 18:51
il me semble que c'est ce qu'on appèle les coefficient de Bézout non ?
Cyberboy2054
Messages postés173Date d'inscriptionjeudi 20 décembre 2001StatutMembreDernière intervention22 août 2008 6 mars 2006 à 18:46
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
}
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
}