Leçon 23: Algorithme d'Euclide (PGCD) - Algorithme et programme Python (Exercice corrigé)

^{Toutes les leçons}

Algorithmique: Apprendre à écrire les algorithmes

Leçon 1
Qu'est ce qu'un algorithme?

Leçon 2
Les variables et les types

Leçon 3
Les opérateurs en algorithmique

Leçon 4
La lecture et l'écriture

Leçon 5
Les chaînes de caractères

Leçon 6
Les conditions (Structures conditionnelles)

Leçon 7
La structure sélective Selon (ou Cas)

Leçon 8
La boucle TantQue (Structures itératives)

Leçon 9
La boucle Pour (Structures itératives)

Leçon 10
La boucle Répéter (Structures itératives)

Leçon 11
Les tableaux

Leçon 12
Les fonctions et procédures (sous-programmes)

Leçon 13
La récursivité (Fonctions récursives)

Leçon 14
Calcul de la complexité des algorithmes

Leçon 15
Equation du second degré (Exercice corrigé)

Leçon 16
Calcul de la moyenne d'une classe (Exercice corrigé)

Leçon 17
Recensement des éléments d'un tableau selon leur signe (Exercice corrigé)

Leçon 18
Compter les voyelles dans une chaîne de caractères à l'aide d'une fonction (Exercice corrigé)

Leçon 19
Algorithme de tri à bulles appliqué à un tableau d'entiers (Exercice corrigé)

Leçon 20
Génération de nombres premiers - Algorithme et programme Python (Exercice corrigé)

Leçon 21
Conversion décimal-binaire - Algorithme et programme Pascal (Exercice corrigé)

Leçon 22
Tableaux à deux dimensions - Moyennes des étudiants sur plusieurs matières (Exercice corrigé)

Leçon 23
Algorithme d'Euclide (PGCD) - Algorithme et programme Python (Exercice corrigé)

Leçon 24
Recherche dichotomique dans un tableau - Algorithme et programme Python (Exercice corrigé)

Leçon 25
Calcul de la racine carrée par dichotomie - Algorithme et programme Python (Exercice corrigé)

Algorithme d'Euclide

Calcul du PGCD (Plus Grand Commun Diviseur)

Dans ce exercice corrigé d'algorithmique, nous allons écrire un algorithme qui permet de calculer le PGCD (plus grand commun diviseur) de deux nombres entiers positifs.

Bien qu'il existe plusieurs techniques qui permettent de calculer le PGCD (comme l'exposition des diviseurs éventuels des deux nombres ou la soustraction successive), l'algorithme d'Euclide reste quand même la méthode la plus utilisée vue sa rapidité. L'algorithme d'Euclide consiste à effectuer des divisions successives jusqu'à ce que le reste soit nul. Nous allons ensuite écrire le programme correspondant à l'aide du langage de programmation Python.

Algorithme d'Euclide en vidéo

https://www.youtube.com/watch?v=Z2AY4axxJUY

Playlist du cours d'algorithmique complet

Playlist d'exercices corrigés d'algorithmique