Inscription / Connexion Nouveau Sujet
Niveau algorithmique
Partager :

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
patrice rabiller
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
shrike
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
patrice rabiller
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é !

Posté par
patrice rabiller
re : Algorithme de PGCD 11-07-09 à 08:37

J'ai testé avec le nouveau logiciel AlgoBox. Voici ce que ça donne :

Algorithme de PGCD

Posté par
shrike
re : Algorithme de PGCD 11-07-09 à 10:38

Ca marche, vraiment merci beaucoup, c'est génial !

Répondre à ce sujet

Seuls les membres peuvent poster sur le forum !

Vous devez être connecté pour poster :

Connexion / Inscription Poster un nouveau sujet
Une question ?
Besoin d'aide ?
(Gratuit)
Un modérateur est susceptible de supprimer toute contribution qui ne serait pas en relation avec le thème de discussion abordé, la ligne éditoriale du site, ou qui serait contraire à la loi.


Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :


Rester sur la page

Inscription gratuite

Fiches en rapport

parmi 1444 fiches de maths

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !