TP Python – Variants, invariants et tests

BTS SIO SISR 2e année – Pour aller plus loin – S11

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 – Compter les tours

Écris tours_division(n) qui renvoie le nombre de tours de la boucle while n > 0: n = n // 2 pour n >= 0 (la boucle est à écrire, avec un compteur).

J'anticipe. Combien de tours pour n = 100 (exercice 1) ?

###

Lancer assert tourspy-unddivision(100) == 7bksl-nlassert tourspy-unddivision(0) == 0bksl-nlassert tourspy-unddivision(1) == 1bksl-nlassert tourspy-unddivision(1000) == 10bksl-nlassert all(tourspy-unddivision(k) == k.bitpy-undlength() for k in range(0, 2000))bksl-nlbksl-nl Valider ∞/∞ Télécharger Téléverser Recharger Sauvegarder

def tourspy-unddivision(n):bksl-nl """Nombre de tours de: while n > 0: n = n // 2."""bksl-nl ...bksl-nlbksl-nl

---

---

Je comprends. Quel est le variant ? Quelle fonction connue de n obtiens-tu (cherche : n.bit_length()) ?

Exercice B – Observer un invariant

Écris etats_somme(n) qui renvoie la liste [s_0, s_1, ..., s_n] des valeurs de s avant le premier tour puis après chaque tour de s = 0 ; for i in range(1, n + 1): s = s + i.

J'anticipe. Écris sur ta feuille les valeurs pour n = 4.

###

Lancer assert etatspy-undsomme(4) == [0, 1, 3, 6, 10]bksl-nlassert etatspy-undsomme(0) == [0]bksl-nlassert etatspy-undsomme(1) == [0, 1]bksl-nlassert all(etatspy-undsomme(n)[k] == k py-str (k + 1) // 2 for n in range(0, 20) for k in range(0, n + 1))bksl-nlbksl-nl Valider ∞/∞ Télécharger Téléverser Recharger Sauvegarder

def etatspy-undsomme(n):bksl-nl """Valeurs de s avant la boucle puis apres chaque tour (liste de n+1 valeurs)."""bksl-nl ...bksl-nlbksl-nl

---

---

Je comprends. Vérifie que s_k vaut k * (k + 1) // 2 : c'est l'invariant de l'exercice 3.

Exercice C – Maximum d'une liste

Écris maximum_boucle(L) (liste non vide) avec une boucle et l'invariant de l'exercice 4. Pas de max.

###

Lancer assert maximumpy-undboucle([3, 1, 2]) == 3bksl-nlassert maximumpy-undboucle([5]) == 5bksl-nlassert maximumpy-undboucle([-4, -1, -9]) == -1bksl-nlassert maximumpy-undboucle([2, 2, 2]) == 2bksl-nlassert maximumpy-undboucle([1, 2, 3]) == 3bksl-nlassert maximumpy-undboucle([3, 2, 1]) == 3bksl-nlassert all(maximumpy-undboucle([a, b, c]) == max(a, b, c) for a in range(-2, 3) for b in range(-2, 3) for c in range(-2, 3))bksl-nlbksl-nl Valider ∞/∞ Télécharger Téléverser Recharger Sauvegarder

def maximumpy-undboucle(L):bksl-nl """Maximum de la liste non vide L, avec une boucle."""bksl-nl ...bksl-nlbksl-nl

---

---

Je comprends. Quel test limite as-tu essayé en premier ? Que se passe-t-il pour L = [] ?

Exercice D – Liste triée ?

Écris est_trie(L) qui renvoie True si la liste est triée par ordre croissant (au sens large), False sinon, en examinant toutes les paires consécutives. Les tests incluent les pièges de l'exercice 7.

J'anticipe. Pourquoi est_trie([1, 2, 0]) doit-il renvoyer False ?

###

Lancer assert estpy-undtrie([1, 2, 3]) == Truebksl-nlassert estpy-undtrie([2, 1]) == Falsebksl-nlassert estpy-undtrie([1, 2, 0]) == Falsebksl-nlassert estpy-undtrie([]) == Truebksl-nlassert estpy-undtrie([7]) == Truebksl-nlassert estpy-undtrie([1, 1, 2, 2]) == Truebksl-nlassert estpy-undtrie([5, 4, 3]) == Falsebksl-nlassert all(estpy-undtrie(L) == (L == sorted(L)) for L in [[1, 3, 2], [1, 2, 2, 5], [3, 3, 3], [2, 4, 3, 5]])bksl-nlbksl-nl Valider ∞/∞ Télécharger Téléverser Recharger Sauvegarder

def estpy-undtrie(L):bksl-nl """True si L est triee (croissant, au sens large)."""bksl-nl ...bksl-nlbksl-nl

---

---

Exercice E – PGCD avec invariant

Écris pgcd_boucle(a, b) (entiers positifs ou nuls) avec une boucle : while b != 0: a, b = b, a % b. L'invariant est « le PGCD de a et b ne change pas » ; le variant est b.

J'anticipe. Écris les valeurs successives de (a, b) pour (252, 105).

###

Lancer assert pgcdpy-undboucle(252, 105) == 21bksl-nlassert pgcdpy-undboucle(84, 36) == 12bksl-nlassert pgcdpy-undboucle(7, 0) == 7bksl-nlassert pgcdpy-undboucle(0, 5) == 5bksl-nlassert all(pgcdpy-undboucle(a, b) == py-undpy-undimportpy-undpy-und('math').gcd(a, b) for a in range(0, 40) for b in range(0, 40))bksl-nlbksl-nl Valider ∞/∞ Télécharger Téléverser Recharger Sauvegarder

def pgcdpy-undboucle(a, b):bksl-nl """PGCD par l'algorithme d'Euclide, avec une boucle."""bksl-nl ...bksl-nlbksl-nl

---

---

Je comprends. Pourquoi b décroît-il strictement ? Que vaut le résultat à la sortie ?