Overblog Suivre ce blog
Editer l'article Administration Créer mon blog
6 juillet 2011 3 06 /07 /juillet /2011 12:00

Dans cet article je donne une formulation de l'algorithme d'Euclide afin qu'il soit programmée. Une traduction est donnée en Python.

 

On veut un programme permettant de caculer le PGCD de deux entiers positifs a et b, avec a>b.

Version récursive

 

Un algortihme est dit récursif lorsqu'il s'utilise lui-même. Ici pour calculer le PGCD de a et b, le programma va, sauf si b est nul calculer le PGCD de b et du reste de la division euclidienne de a par b. Donc pour calculer PGCD(a,b), on calcule PGCD(b,r) où r est le reste. Donc le programme recommencera avec des nombres de plus en plus petit jusqu'à ce que le deuxième soit 0.

 

Algorithme


%commentaire% version récursive du calcul de PGCD 
variables : a,b  (entrée), r

Si b=0 alors retourner a
sinon r reçoit le reste de la division Euclidienne de a par b
        recommencer le programme avec b et r en entrée
 

 

Vérification : Si b n'est pas égal à zéro, on utilise la propriété PGCD(a,b)=PGCD(b,r). Ceci correspond bien à l'agorithme d'Euclide (voir article cité en haut). Le fait que le deuxième nombre soit nul signifie que le premier est le dernier reste non-nul de l'agorithme d'Euclide.


 

Remarque : Ce programme est très court, si comme ici, l'on suppose que l'on dispose d'un programme ou d'une fonction annexe qui calcule directemnt le reste de la division euclidienne, ce qui est le cas dans tous les langages de programmation.

 

Version Python

def algo_euclide(a,b) :
    %%calcul récursif du pgcd de a et b
    if (b==0) :
        return(a)
    else :
        r=a%b
        return algo_euclide(b,r)


Remarque :
En Python, a%b donne le reste de la division Euclidienne de a par b.

 

D'autres versions de l'algorithme d'Euclide existent. Une version itérative (par opposition à la version récursive le programme ne s'apelle pas lui-même) est possible mais nécessite l'utilisation d'une boucle tant que .
D'autres versions plus élaborées existent également. L'agorithme d'Euclide étendu sera présenté plus tard sur ce blog.

Partager cet article

Repost 0
Published by Maths_Buchwald - dans Programmes
commenter cet article

commentaires

Présentation

  • : Maths Otak'
  • Maths Otak'
  • : Au départ, j'ai créé ce blog pour y publier des articles reliant Maths et histoire de l'art et la culture. Maintenant, il me permet d'aborder des sujets simples de la culture mathématique. J'aime parler de jeux vidéos. Vous trouverez aussi sur ce site des fiches de maths et Histoire des Arts de 2009-2010 au format *.pdf. Je ne sais pas où me mène ce blog donc il ne sera sans doute plus le même si je continue à l'alimenter dans un an. N'hésitez pas à laisser des commentaires.
  • Contact

Twitter

Recherche

Mes vidéos

Catégories