TP Python – Compter les opérations

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

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 – Somme avec compteur

Écris somme_compte(n) qui calcule s = 0 ; for i in range(n): s = s + i et renvoie le couple (s, nb_additions).

J'anticipe. Combien d'additions pour n = 5 ?

###

Lancer assert sommepy-undcompte(5) == (10, 5)bksl-nlassert sommepy-undcompte(0) == (0, 0)bksl-nlassert sommepy-undcompte(100) == (4950, 100)bksl-nlbksl-nl Valider ∞/∞ Télécharger Téléverser Recharger Sauvegarder

def sommepy-undcompte(n):bksl-nl """Renvoie (s, nbpy-undadditions) pour la somme des i de 0 a n-1."""bksl-nl ...bksl-nlbksl-nl

---

---

Exercice B – Recherche séquentielle comptée

Écris recherche_compte(L, x) qui parcourt L de gauche à droite et renvoie (indice, nb_comparaisons) à la première occurrence de x, ou (-1, len(L)) si x est absent.

J'anticipe. Combien de comparaisons pour trouver 3 dans [3, 5, 7] ? Et 7 ? Et 9 ?

###

Lancer assert recherchepy-undcompte([3, 5, 7], 3) == (0, 1)bksl-nlassert recherchepy-undcompte([3, 5, 7], 7) == (2, 3)bksl-nlassert recherchepy-undcompte([3, 5, 7], 9) == (-1, 3)bksl-nlassert recherchepy-undcompte([], 1) == (-1, 0)bksl-nlassert recherchepy-undcompte([4, 4], 4) == (0, 1)bksl-nlbksl-nl Valider ∞/∞ Télécharger Téléverser Recharger Sauvegarder

def recherchepy-undcompte(L, x):bksl-nl """Renvoie (indice, nbpy-undcomparaisons), ou (-1, len(L)) si absent."""bksl-nl ...bksl-nlbksl-nl

---

---

Exercice C – Doublons comptés

Écris doublons_compte(L) qui applique la méthode des deux boucles (i, puis j de i+1 à la fin) et renvoie (a_doublon, nb_comparaisons) ; elle s'arrête à la première égalité trouvée.

J'anticipe. Pour [1, 2, 1, 4], dans quel ordre les comparaisons ont-elles lieu ?

###

Lancer assert doublonspy-undcompte([1, 2, 3, 4]) == (False, 6)bksl-nlassert doublonspy-undcompte([1, 2, 1, 4]) == (True, 2)bksl-nlassert doublonspy-undcompte([5, 5]) == (True, 1)bksl-nlassert doublonspy-undcompte([]) == (False, 0)bksl-nlassert doublonspy-undcompte(list(range(10))) == (False, 45)bksl-nlbksl-nl Valider ∞/∞ Télécharger Téléverser Recharger Sauvegarder

def doublonspy-undcompte(L):bksl-nl """Renvoie (True/False, nbpy-undcomparaisons)."""bksl-nl ...bksl-nlbksl-nl

---

---

Je comprends. Que vaut le nombre de comparaisons pour une liste de 10 éléments sans doublon ?

Exercice D – Tours d'une division

Écris tours_log2(n) qui renvoie le nombre de tours de while n > 1: n = n // 2 (pour n >= 1).

J'anticipe. Combien de tours pour n = 1000 (exercice 4) ?

###

Lancer assert tourspy-undlog2(1000) == 9bksl-nlassert tourspy-undlog2(1) == 0bksl-nlassert tourspy-undlog2(2) == 1bksl-nlassert tourspy-undlog2(1000000) == 19bksl-nlassert all(tourspy-undlog2(k) == k.bitpy-undlength() - 1 for k in range(1, 3000))bksl-nlbksl-nl Valider ∞/∞ Télécharger Téléverser Recharger Sauvegarder

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

---

---

Exercice E – Premier n où B dépasse A

Écris premier_n_pire(f, g) qui renvoie le plus petit entier n >= 1 tel que g(n) > f(n). On suppose qu'un tel n existe (pas de boucle infinie sur les cas de test).

J'anticipe. Que renvoie l'appel pour A = 3n + 5 et B = n²/10 (exercice 5) ?

###

Lancer assert premierpy-undnpy-undpire(lambda n: 3 py-str n + 5, lambda n: n py-str n / 10) == 32bksl-nlassert premierpy-undnpy-undpire(lambda n: 100 py-str n, lambda n: n py-str n) == 101bksl-nlassert premierpy-undnpy-undpire(lambda n: 10, lambda n: n) == 11bksl-nlbksl-nl Valider ∞/∞ Télécharger Téléverser Recharger Sauvegarder

def premierpy-undnpy-undpire(f, g):bksl-nl """Plus petit n >= 1 tel que g(n) > f(n)."""bksl-nl ...bksl-nlbksl-nl

---

---