TP Python – Piles, files et dictionnaires

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

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 – Parenthèses bien formées

Écris parentheses_ok(s) qui renvoie True si les parenthèses (), crochets [] et accolades {} de s sont bien formés. Les autres caractères sont ignorés. Utilise une pile.

J'anticipe. Déroule la pile pour "([)]".

###

Lancer assert parenthesespy-undok("{[()]}") == Truebksl-nlassert parenthesespy-undok("([)]") == Falsebksl-nlassert parenthesespy-undok("(()") == Falsebksl-nlassert parenthesespy-undok("") == Truebksl-nlassert parenthesespy-undok(")(") == Falsebksl-nlassert parenthesespy-undok("a(b)c[d]") == Truebksl-nlassert parenthesespy-undok("]") == Falsebksl-nlbksl-nl Valider ∞/∞ Télécharger Téléverser Recharger Sauvegarder

def parenthesespy-undok(s):bksl-nl """True si (), [], {} sont bien formes (pile)."""bksl-nl ...bksl-nlbksl-nl

---

---

Exercice B – Compter les adresses

Écris compte_ip(lignes) qui renvoie un dictionnaire adresse -> nombre d'occurrences pour une liste de chaînes (adresses d'un journal).

###

Lancer assert comptepy-undip(["10.0.0.1", "10.0.0.2", "10.0.0.1"]) == {"10.0.0.1": 2, "10.0.0.2": 1}bksl-nlassert comptepy-undip([]) == {}bksl-nlassert comptepy-undip(["a"]) == {"a": 1}bksl-nlassert comptepy-undip(list("reseau")) == {"r": 1, "e": 2, "s": 1, "a": 1, "u": 1}bksl-nlbksl-nl Valider ∞/∞ Télécharger Téléverser Recharger Sauvegarder

def comptepy-undip(lignes):bksl-nl """Dictionnaire adresse -> nombre d'occurrences."""bksl-nl ...bksl-nlbksl-nl

---

---

Je comprends. Quel est le coût en fonction du nombre de lignes ?

Exercice C – Les plus fréquentes

Écris top_n(compte, n) qui renvoie la liste des n couples (clé, nombre) les plus fréquents, triés par nombre décroissant puis par clé croissante (ordre alphabétique).

###

Lancer assert toppy-undn({"a": 3, "b": 5, "c": 3}, 2) == [("b", 5), ("a", 3)]bksl-nlassert toppy-undn({}, 3) == []bksl-nlassert toppy-undn({"x": 1}, 5) == [("x", 1)]bksl-nlassert toppy-undn({"b": 2, "a": 2}, 2) == [("a", 2), ("b", 2)]bksl-nlbksl-nl Valider ∞/∞ Télécharger Téléverser Recharger Sauvegarder

def toppy-undn(compte, n):bksl-nl """Les n couples (cle, nombre) les plus frequents."""bksl-nl ...bksl-nlbksl-nl

---

---

Exercice D – Tourniquet

Écris tourniquet(durees, quantum) : chaque tâche i a besoin de durees[i] unités ; on les traite avec une file, chacune au plus quantum unités par tour, puis elle retourne en fin de file si elle n'est pas finie. Renvoie la liste des indices dans l'ordre de fin. Utilise collections.deque.

J'anticipe. Retrouve l'ordre [1, 2, 0] de l'exercice 5.

###

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

from collections import dequebksl-nlbksl-nlbksl-nldef tourniquet(durees, quantum):bksl-nl """Indices des taches dans l'ordre de fin (file)."""bksl-nl ...bksl-nlbksl-nl

---

---

Exercice E – Annuler

Écris edition(ops) : ops est une liste de chaînes ; "ANNULE" retire le dernier élément ajouté (sans effet si rien à annuler), toute autre chaîne est ajoutée. Renvoie la liste finale. Utilise une pile.

###

Lancer assert edition(["a", "b", "ANNULE", "c"]) == ["a", "c"]bksl-nlassert edition([]) == []bksl-nlassert edition(["ANNULE"]) == []bksl-nlassert edition(["a", "ANNULE", "ANNULE", "b"]) == ["b"]bksl-nlassert edition(["x", "y"]) == ["x", "y"]bksl-nlbksl-nl Valider ∞/∞ Télécharger Téléverser Recharger Sauvegarder

def edition(ops):bksl-nl """Etat final apres ajouts et annulations (pile)."""bksl-nl ...bksl-nlbksl-nl

---

---