Le PGCD de 2 nombres

[moussaxp]

bon jour..j'ai un probleme sur l'algorithme qui cherche le PGCD de deux entiers a et b sachant que le recherche de PGCD de a et b devient de chercher le PGCD de a et (a-b) avec a > b .en utulise les fonctions ou/et des procedeures ( PGCD=le plus grand diveseur commun de a et b ) .quelqu'un peut m'aider S.V.P .donne au moins le decopage modulair....Merci

[abcd22]

Bonjour, si a > b on a pgcd(a,b) = pgcd(a-b,b) plutôt que pgcd(a-b,a) (les deux sont corrects mathématiquement, mais le 2e ne sert à rien algorithmiquement : ça donne pgcd(a,b) = pgcd(a-b,a) = pgcd(a-(a-b),a) = pgcd(a,b)...).
Pour calculer le PGCD de deux nombres on peut faire par exemple un algorithme récursif :

pgcd(a,b)
si a = 0 alors pgcd = b
si b = 0 alors pgcd = a
si a < b alors pgcd = pgcd(a,b-a)
sinon pgcd = pgcd(a-b,b)

Voilà il ne reste plus qu'à traduire ça en programme, comme tu vois ce n'est pas la peine de le découper en modules :happy3: