Inscription / Connexion Nouveau Sujet
Niveau terminale
Partager :

algorithme PGCD

Posté par
bapouline
11-01-15 à 16:29

Bonjour !
Besoin d'un petit peu d'aide. Je suis en terminale S, et j'ai un exo sur le PGCD (maths spé), je n'arrive pas à m'en sortir.
Je vous le met ici :

Soit a et b deux entiers naturels tels que 0<b<a. On considère l'algorithme suivant :

ENTRÉE : Saisir a, saisir b
TRAITEMENT : Tantque b ne divise pas a faire :
              c reçoit max(b,a-b)
              b reçoit min(b;a-b)
              a reçoit c
            Fin Tantque
SORTIE : Afficher b


Question : Justifier que cet algorithme s'arrête et qu'il affiche le PGCD de a et b.

Pour l'instant la seule chose que j'ai remarqué c'est que cela ressemble à la détermination du PGCD en faisant des soustractions successives (j'ai trouvé cela ici : http://mathematiques3.free.fr/2troisieme/arithmetique/arit010.php )Le problème c'est que quand on utilise cette méthode on prend le dernier résultat différent de 0 or ici on cherche jusqu'à ce que b divise a.
Quelqu'un pourrait m'aider ?
Merci beaucoup!

Posté par
Sylvieg Moderateur
re : algorithme PGCD 11-01-15 à 18:10

Bonjour,
Si b divise a, quel est le PGCD de a et b ?

Essaye avec 432 et 240, en faisant les soustraction.
Si tu le fais à la main , tu vas arriver à 144 et 48, sans voir que 48 divise 144.
Tu vas donc continuer jusqu'à 0.
Mais si tu avais vu que 48 divise 144, tu aurais pu conclure toutde suite que le PGCD de 432 et 240 est 48.

Posté par
bapouline
re : algorithme PGCD 11-01-15 à 18:46

Si b divise a, alors pgcd(a;b)=b
Donc en fait il s'agit de la même méthode que les différences successives sauf qu'à chaque boucle on regarde si b divise a (donc on regarde si le pgcd est b) ?
Si c'est ça je pense avoir compris la méthode mais je ne vois pas trop comment l'expliquer.
Je propose une formulation :
On sait que si un nombre en divise 2 autres, il en divise une combinaison linéaire, plus particulièrement leur différence.
On cherche donc le PGCD aux deux nombres en faisant des différences jusqu'à ce que l'un divise l'autre.  En effet, quand on arrive à b divise a, pgcd(a;b)=b

Posté par
Sylvieg Moderateur
re : algorithme PGCD 11-01-15 à 19:18

Oui ; il faut aussi justifier que cet algorithme s'arrête.
Je n'ai pas trop le temps d'expliquer. A chaque étape, b est remplacé par un entier au moins inférieur ou égal à l'ancienne valeur de b-1 ou de a-1 .

Posté par
Sylvieg Moderateur
re : algorithme PGCD 11-01-15 à 21:13

Il me semble plus facile de travailler sur a :
On a toujours 0 < b < a :
C'est vrai au départ ; puis 0 < min(b;a-b) < max(b,a-b) ; donc nouvelle valeur de b < nouvelle valeur de a
A chaque étape, la nouvelle valeur de a est max(b,a-b) qui est strictement inférieur à a .
La nouvelle valeur de a est donc inférieure ou égale à a-1.
Il y a donc moins de a étapes.

Posté par
Sylvieg Moderateur
re : algorithme PGCD 11-01-15 à 21:28

Je recommence en complétant après "C'est vrai au départ".

On a toujours 0 < b < a :
C'est vrai au départ ; puis 0 < min(b;a-b) max(b,a-b) ; l'inégalité entre le min et le max est une égalité que si b = a-b équivalent à a = 2b ; dans ce cas b divise a et le "tant que" s'arrête. L'inégalité est donc stricte quand on passe à l'étape suivante et 0 < nouvelle valeur de b < nouvelle valeur de a .

A chaque étape, la nouvelle valeur de a est max(b,a-b) qui est strictement inférieur à a .
La nouvelle valeur de a est donc inférieure ou égale à a-1.
Il y a donc moins de a étapes.

Posté par
bapouline
re : algorithme PGCD 12-01-15 à 18:38

Bonsoir,
merci beaucoup de m'expliquer tout ceci, j'ai bien compris!

Posté par
Sylvieg Moderateur
re : algorithme PGCD 12-01-15 à 18:40

De rien, et à une autre fois sur l'île



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 1742 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 !