Algorithme d'Euclide étendu (TS spé Math)
Répondre à la discussion
Affichage des résultats 1 à 5 sur 5

Algorithme d'Euclide étendu (TS spé Math)



  1. #1
    Jon83

    Algorithme d'Euclide étendu (TS spé Math)


    ------

    Bonjour!

    Je n'arrive pas à trouver une présentation pratique de l'algorithme d'Euclide étendu afin de mener les calculs à la main, sans faire d'erreur!
    Si vous en avez une, elles sera la bienvenue!

    -----

  2. #2
    sylvainc2

    Re : Algorithme d'Euclide étendu (TS spé Math)

    Il y a deux versions de l'algo, récursive et itérative, je vais donner un exemple de la version itérative.

    On veut calculer 99x + 78y = pgcd(98,78):



    À chaque ligne à partir de la ligne 3, on calcule:
    ai = bi-1
    bi = ri-1
    qi = quotient de ai / bi
    ri = reste de ai / bi
    xi = xi-2 - qi xi-1
    yi = yi-2 - qi yi-1

    le pgcd est le dernier ri > 0, et x et y ceux de la même ligne, donc 99 * -11 + 78 * 14 = 3

    La version récursive est un peu différente, je peux donner aussi un tableau pour son détail. Je peux aussi expliquer pourquoi l'algo fonctionne, le calcul des xi et yi est pas évident, pour la version itérative en tout cas.

  3. #3
    Cherchell

    Re : Algorithme d'Euclide étendu (TS spé Math)

    Bonjour,

    Je te renvoie à cette adresse où est détaillée une méthode pour y arriver
    http://storage.canalblog.com/27/79/477615/53797774.pdf
    Bon courage

  4. #4
    Jon83

    Re : Algorithme d'Euclide étendu (TS spé Math)

    Super! Merci pour vos réponses

  5. A voir en vidéo sur Futura
  6. #5
    OY1951

    Re : Algorithme d'Euclide étendu (TS spé Math)

    Bonjour ,

    Je ne sais pas si c'est une bonne chose de donner une deuxième "vie"(je préfère dire cela à la place de "déterrer") à cette discussion
    et ce malgré que Jon83 a été très satisfait des réponses qui lui ont été proposées. Si non alors j'en ouvrirai une autre page de discussion.
    Cordialement.
    Dernière modification par OY1951 ; 29/11/2014 à 08h49.

Discussions similaires

  1. Algorithme d'Euclide
    Par learning dans le forum Mathématiques du collège et du lycée
    Réponses: 9
    Dernier message: 02/05/2010, 09h41
  2. hésitation entre spé math et spé physique ...
    Par invited20112f2 dans le forum Orientation avant le BAC
    Réponses: 14
    Dernier message: 04/04/2009, 18h58
  3. Matrice et algorithme (spé)
    Par invite441314de dans le forum Mathématiques du supérieur
    Réponses: 1
    Dernier message: 03/01/2007, 00h22
  4. algorithme d'Euclide, pgcd TS
    Par invitebf3eb25e dans le forum Mathématiques du collège et du lycée
    Réponses: 5
    Dernier message: 16/11/2006, 16h26