TP Python – L'algorithme d'Euclide en Python

BTS SIO SISR 1re année – Mathématiques pour l'informatique – S05

Note

Comment ce TP fonctionne. Chaque exercice a un éditeur Python intégré à la page (il s'exécute dans ton navigateur, rien à installer). Avant de lancer, écris sur ta feuille ce que tu anticipes (« J'anticipe »). Puis lance et compare. Le bouton Valider exécute des tests : un test réussi ne dispense pas de comprendre pourquoi.

Exercice A – La division euclidienne sans // ni %

Écris division_euclidienne(a, b) (\(a \ge 0\), \(b > 0\)) qui renvoie le couple (q, r) en retranchant b tant que c'est possible.

J'anticipe. Pour a = 17 et b = 5, combien de soustractions ? Quel est le variant de ta boucle ?

###

Lancer assert divisionpy-undeuclidienne(17, 5) == (3, 2)bksl-nlassert divisionpy-undeuclidienne(100, 7) == (14, 2)bksl-nlassert divisionpy-undeuclidienne(7, 100) == (0, 7)bksl-nlassert divisionpy-undeuclidienne(0, 3) == (0, 0)bksl-nlassert divisionpy-undeuclidienne(24, 6) == (4, 0)bksl-nlassert all(divisionpy-undeuclidienne(a, b) == (a // b, a % b) for a in range(0, 60) for b in range(1, 20))bksl-nlbksl-nl Valider ∞/∞ Télécharger Téléverser Recharger Sauvegarder

def divisionpy-undeuclidienne(a, b):bksl-nl """Renvoie (q, r) tels que a = bpy-strq + r et 0 <= r < b (a >= 0, b > 0)."""bksl-nl q = 0bksl-nl r = abksl-nl # À compléter : tant que r est supérieur ou égal à b,bksl-nl # on retranche b à r et on compte un quotient de plus.bksl-nl return (q, r)bksl-nlbksl-nl

---

---

Exercice B – Diviseurs

Écris diviseurs(n) (\(n \ge 1\)) qui renvoie la liste croissante des diviseurs positifs de n.

###

Lancer assert diviseurs(1) == [1]bksl-nlassert diviseurs(13) == [1, 13]bksl-nlassert diviseurs(36) == [1, 2, 3, 4, 6, 9, 12, 18, 36]bksl-nlassert diviseurs(84) == [1, 2, 3, 4, 6, 7, 12, 14, 21, 28, 42, 84]bksl-nlassert len(diviseurs(360)) == 24bksl-nlbksl-nl Valider ∞/∞ Télécharger Téléverser Recharger Sauvegarder

def diviseurs(n):bksl-nl """Liste croissante des diviseurs positifs de n (n >= 1)."""bksl-nl liste = []bksl-nl # À compléterbksl-nl return listebksl-nlbksl-nl

---

---

Exercice C – PGCD par l'algorithme d'Euclide

Écris pgcd(a, b) avec une boucle while, sans utiliser math.gcd.

Je comprends. Que renvoie pgcd(7, 0) ? pgcd(0, 7) ? Justifie avec l'algorithme.

###

Lancer assert pgcd(252, 198) == 18bksl-nlassert pgcd(1071, 462) == 21bksl-nlassert pgcd(17, 5) == 1bksl-nlassert pgcd(7, 0) == 7bksl-nlassert pgcd(0, 7) == 7bksl-nlassert pgcd(1920, 1080) == 120bksl-nlassert pgcd(756, 540) == 108bksl-nlimport mathbksl-nlassert all(pgcd(a, b) == math.gcd(a, b) for a in range(0, 50) for b in range(0, 50) if a + b > 0)bksl-nlbksl-nl Valider ∞/∞ Télécharger Téléverser Recharger Sauvegarder

def pgcd(a, b):bksl-nl """PGCD de deux entiers naturels non tous deux nuls (algorithme d'Euclide)."""bksl-nl # À compléter : tant que b n'est pas nul, remplacer (a, b) par (b, a mod b)bksl-nl return abksl-nlbksl-nl

---

---

Exercice D – PPCM et nombres premiers entre eux

À l'aide de pgcd, écris ppcm(a, b) et premiers_entre_eux(a, b).

###

Lancer assert ppcm(12, 18) == 36bksl-nlassert ppcm(15, 25) == 75bksl-nlassert ppcm(4, 6) == 12bksl-nlassert ppcm(6, 8) == 24bksl-nlassert ppcm(7, 5) == 35bksl-nlassert premierspy-undentrepy-undeux(17, 5) is Truebksl-nlassert premierspy-undentrepy-undeux(12, 18) is Falsebksl-nlassert premierspy-undentrepy-undeux(1, 99) is Truebksl-nlbksl-nl Valider ∞/∞ Télécharger Téléverser Recharger Sauvegarder

def pgcd(a, b):bksl-nl while b != 0:bksl-nl a, b = b, a % bbksl-nl return abksl-nlbksl-nldef ppcm(a, b):bksl-nl """PPCM de deux entiers strictement positifs."""bksl-nl ...bksl-nlbksl-nldef premierspy-undentrepy-undeux(a, b):bksl-nl """True si a et b sont premiers entre eux."""bksl-nl ...bksl-nlbksl-nl

---

---

Exercice E – Compter les étapes

Écris nombre_divisions(a, b) qui renvoie le nombre de divisions euclidiennes effectuées par l'algorithme d'Euclide jusqu'au reste nul (pour (252, 198), quatre divisions : voir le cours).

###

Lancer assert nombrepy-unddivisions(252, 198) == 4bksl-nlassert nombrepy-unddivisions(1071, 462) == 3bksl-nlassert nombrepy-unddivisions(17, 5) == 3bksl-nlassert nombrepy-unddivisions(10, 5) == 1bksl-nlassert nombrepy-unddivisions(5, 10) == 2bksl-nlbksl-nl Valider ∞/∞ Télécharger Téléverser Recharger Sauvegarder

def nombrepy-unddivisions(a, b):bksl-nl """Nombre de divisions euclidiennes de l'algorithme d'Euclide appliqué à (a, b), b > 0."""bksl-nl compteur = 0bksl-nl # À compléterbksl-nl return compteurbksl-nlbksl-nl

---

---