Algoritme

typi -  
Hxyp Messages postés 401 Date d'inscription   Statut Membre Dernière intervention   -
Bonjour, j aimerais avoir un cours explicite sur l algorithme d euclide merci d'avance

1 réponse

  1.
    Hxyp Messages postés 401 Date d'inscription   Statut Membre Dernière intervention   54
     
    Bonjour,
    Comme il l'est indiqué sur wikipedia :
    https://fr.wikipedia.org/wiki/Algorithme_d%27Euclide
    «L'algorithme d'Euclide est un algorithme permettant de déterminer le plus grand commun diviseur (P.G.C.D.) de deux entiers dont on ne connaît pas la factorisation.»
    Dans l'exemple : 
    Calculons, par exemple, le PGCD de 1071 et de 1029 à l'aide de l'algorithme d'Euclide :

1071 = 1029 × 1 + 42

1029 = 42 × 24 + 21

42 = 21 × 2 + 0

Il faut prendre le dernier reste avant le zéro, donc PGCD(1071 ; 1029) = 21

    C'est le reste de la division (modulo) qui est utilisé :

    1071/1029=1
    1071-1029*1=42

    1029/42=24
    1029-42*24=21

    42/21=2
    42-21*2=0

    alors le PGCD est de 21
    0