NSI (terminale) · Chapitre 5 · Application directe du cours
PGCD par l'algorithme d'Euclide
La récursivité · niveau 1 (application)
Énoncé
PGCD par l'algorithme d'Euclide.
Écrire une fonction récursive pgcd(a, b) calculant le plus grand commun diviseur de deux entiers positifs, en utilisant et .
Corrigé
Le variant est , qui décroît strictement à chaque appel (propriété du reste euclidien).
def pgcd(a, b):
if b == 0:
return a
return pgcd(b, a % b)
print(pgcd(48, 36)) # affiche 12100 % gratuit
Essaie le suivant avec le tuteur
- L'exercice suivant avec le tuteur, sans compte : il guide pas à pas, sans donner la réponse
- 8 autres exercices corrigés dans ce chapitre
- Les 2 QCM du chapitre, le premier sans compte
- Le podcast et la vidéo du chapitre : 2 minutes d'écoute sans compte
Sans compte : le cours, le premier QCM, 2 minutes de podcast et de vidéo et un exercice avec le tuteur. Pour tout le reste : inscription gratuite en 30 secondes, sans carte bancaire.