Niveau algorithmique

Algorithme de PGCD

Posté par
shrike 10-07-09 à 12:17

Bonjour,

Je cherche à écrire un algorithme inspiré de celui d'Euclide qui détermine le PGCD de plusieurs nombres (pas seulement deux). Le nombre de nombres dont il faut déterminer le PGCD doit par exemple être donné par l'utilisateur.

Merci d'avance de vos suggestions.

Edit jamo : forum modifié.

Posté par re : Algorithme de PGCD 10-07-09 à 13:13

Bonjour,

Si tu peux utiliser la récursivité, alors la meilleure solution est de se servir de la propriété :

PGCD(a,b,c)=PGCD(PGCD(a,b),c)...

Posté par re : Algorithme de PGCD 10-07-09 à 13:32

Et oui je sais bien...
Mais je ne vois pas comment écrire cet algorithme.

Posté par re : Algorithme de PGCD 10-07-09 à 21:46

Voici une solution possible :

Variables :
A,B,N,I,Q,R sont des entiers

Début Algorithme PGCD
   Lire N  //nombre d'entiers dans la liste
   Lire A  //premier entier de la liste
   Affecter 1 à I
   TantQue I<N faire
      Lire B   //entier suivant dans la liste
      Affecter I+1 à I   //I est le compteur d'entiers à lire
      TantQue PartieEntière(A/B)A/B faire :   //algorithme classique d'Euclide
         Affecter PartieEntière(A/B) à Q
         Affecter A-B*Q à R
         Affecter B à A
         Affecter R à B
      FinTantQue
   FinTantQue
   Affecter A à PGCD
Fin Algorithme

Je n'ai pas testé, mais ça devrait marcher, sans même faire appel à la récursivité !