PGCD par l'algorithme d'Euclide

Application directe du cours · niveau 1 (application) · NSI (terminale), chapitre 5 — La récursivité

É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 $pgcd (a, 0) = a$ et $pgcd (a, b) = pgcd (b, a mod b)$ .

Corrigé

Le variant est $b$ , 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 12

Les autres exercices de ce chapitre Le cours du chapitre

Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.