Discussion :

[mullger]

Bonjour,

Je voudrais faire un algorithme permettant de caclculer le pgdc de 2 nombres à l'aide de soustractions successives.

(Vous vous doutez bien que ce n'est pas une lubie mais simplement un exercice pour un cours...)

J'ai cherché sur internet mais je n'ai rien trouvé. Pouvez-vous m'expliquer comment on fait pour calculer un PGDC à l'aide de soustraction successives ? Connaissez vous des sites qui l'expliquent ?

Merci d'avance,

[mullger]

Pour info, j'ai trouvé une solution je me suis aidée avec les infos du lien ci-dessous. C'est très simple en fait !

http://www.mathadoc.com/Documents/co...thm/activ2.pdf

[Charlemagne]

Ton lien ne marche pas.
Je sais que tu as marqué ton problème comme étant résolu.

Pour info voici quand même l'algorithme pour calculer le PGCD (et le PPCM).

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
template<class T>
T gcd(T a,T b)
{
  T c;
  while (b!=0) { c=a%b; a=b; b=c; } 
  return a;
}
 
template<class T>
T lcm(T a,T b)
{
  return (a/gcd(a,b))*b;
}

[ronan99999]

Je sais que c'est terminé mais pour etre plus précis par rapport à l'énoncé posé:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 
//par soustraction
PGCD(a:entier,b:entier):entier
debut
 
si (a=b)
    alors resultat:=a;
 sinon
     si (a>b) alors resultat:=PGCD(a-b,b) 
        sinon resultat:=PGCD(a,b-a)
     finsi
finsi
 
fin
 
PPCM(a:entier,b:entier):entier
debut
 
resultat := a*b/PGCD(a,b);
 
fin

[mullger]

Merci pour les solutions.

Désolé pour le lien, je l'ai trouvé en cherchant "algorithme PGDC soustractions succesives" c'était sur le site de mathadoc.

Voilà,