Comprendre le calcul du PGCD

Bjr,
je suis nouvelle dans le forum et débutante en programmation avec c++, donc j'arrive pas à résoudre un exercice qui dit:

Citation:

---

soit x et y deux nombres positifs,non nuls tel que: x>y. Ecrire un prog qui permet de calculer le plus grand commun diviseur (PGCD).

EXEMPLE:
x=20, y=15.
diviseurs de x={1,2,4,5,10,20}
diviseurs de y={1,2,5,15}
diviseurs communs={1,5}
PGCD=5

INDICATION:
on utilise la boucle while et for,sans utiliser les tableau.

---

s'il vous plait aidez moi car Je n'arrive pas résoudre l'exercice.
merci

Le PGCD est le dernier reste NON NUL de l'algorithme d'Euclide.
Tout ce que tu as à faire est une boucle pour diviser x par y tant que le reste n'est pas nul et évidemment actualiser x et y.

J'édite pour te donner un exemple si tu ne connais pas l'algorithme d'Euclide.
Je reprends tes nombres : x=20 et y=15
On a :
20 = 15*1+5 (reste=5 non nul donc on continue, on divise donc 15 par 5. Dans ton code, x prendra la valeur 15 et y la valeur 5)

15 = 5*3+0 (Youpi le reste est nul)

Le reste est nul, donc on s'arrête ici et le dernier reste non nul était 5

Eurêka on a notre PGCD

Faut d'abord comprendre comment trouver le PGCD de deux nombres et cella se fait grâce à l'algorithme d’Euclide que tu dois chercher à comprendre avant de le traduite de manière informatique dans le langage C++
Donc le post plus haut t'aidera grandement dans ce sens :roll:

Bonjour et bienvenue sur le forum

Pour que l'on puisse vous aider, il faut que vous postiez le code que vous avez déjà commencé ainsi que les bugs (ou résultats faux) que vous obtenez.
Pour rappel, le forum n'est pas destiné à faire le travail à la place des autres mais d'aider à résoudre par soi même les problèmes.

Bonne continuation

Bonjour.
Ce que propose Xtrem_Voyageur est totalement juste.
Mais je pense que si l'exercice était d'implémenter l'algorithme d'Euclide, ce serait précisé dans l'énoncé.

Vu comment il est présenté, j'imagine qu'il faut d'une manière ou d'une autre déterminer les diviseurs des nombres, avant de déterminer le plus grand commun aux deux.
Mais ça reste un point de vue...

Comme il est précisé "sans utiliser les tableau", j'imagine qu'il en faut pas calculer les diviseurs de chaque nombre. Je partirais sur la solution Xtrem_Voyageur.

Je n'ai pas dit qu'il fallait conserver tous les diviseurs en mémoire... :roll:

merci tous, grace à vos aide j'ai fais ce petit programme

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

#include<iostream> using namespace std; int main () { int x,y; double r; cout<<"donner les deux nombres";cin>>x;cin>>y; r=x%y; while (r!=0) { x=y; y=r; r=x%y; } cout<<"Le pgcd de x et y est:"<<y<<endl; system("pause"); return 0; }

---

et il m'a donné le résultat juste
merci encore une fois

c'est pas parce qu'il te donne un résultat juste qu'il est juste
tu dois le tester avec plusieurs occurrence afin de vérifier que ton programme est correcte !

j'ai essaiye plusieurs cas dont le résultat toujour juste

[blague] Tu n'en seras jamais sûre tant que tu n'auras pas écrit ton algo dans Coq ![/blague]

Fais-nous signe quand tu auras la correction.
J'aimerais bien savoir si on attendait vraiment l'implémentation de l'algorithme d'Euclide...

Citation:

---

Envoyé par Steph_ng8

Fais-nous signe quand tu auras la correction.
J'aimerais bien savoir si on attendait vraiment l'implémentation de l'algorithme d'Euclide...

---

Si le but de l'exo est d'afficher exactement ce que l'énnoncé dicte, alors il faut effectivement se passer de l'algorithme d'Euclide.