TP Python – Dichotomie, puissance rapide et tri fusion

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

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 – Recherche dichotomique

Écris dicho(L, x) qui renvoie l'indice de x dans la liste triée L (valeurs distinctes), ou -1 s'il est absent, par dichotomie (récursive ou avec une boucle).

J'anticipe. Pour L = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91] et x = 23, quel indice attends-tu ?

###

Lancer assert dicho([2, 5, 8, 12, 16, 23, 38, 56, 72, 91], 23) == 5bksl-nlassert dicho([2, 5, 8, 12, 16, 23, 38, 56, 72, 91], 40) == -1bksl-nlassert dicho([2, 5, 8, 12, 16, 23, 38, 56, 72, 91], 2) == 0bksl-nlassert dicho([2, 5, 8, 12, 16, 23, 38, 56, 72, 91], 91) == 9bksl-nlassert dicho([], 3) == -1bksl-nlassert all(dicho(list(range(0, 100, 3)), v) == (v // 3 if v % 3 == 0 and 0 <= v <= 99 else -1) for v in range(-5, 110))bksl-nlbksl-nl Valider ∞/∞ Télécharger Téléverser Recharger Sauvegarder

def dicho(L, x):bksl-nl """Indice de x dans la liste triee L, ou -1."""bksl-nl ...bksl-nlbksl-nl

---

---

Je comprends. Quel est le variant (nombre d'éléments restant à examiner) ?

Exercice B – Compter les comparaisons

Écris etapes_dicho(L, x) qui renvoie le nombre d'éléments examinés (un par milieu) par la dichotomie, que x soit présent ou non.

J'anticipe. Quelles valeurs attends-tu pour 23 et pour 40 (exercice 1) ?

###

Lancer assert etapespy-unddicho([2, 5, 8, 12, 16, 23, 38, 56, 72, 91], 23) == 3bksl-nlassert etapespy-unddicho([2, 5, 8, 12, 16, 23, 38, 56, 72, 91], 40) == 4bksl-nlassert etapespy-unddicho([2, 5, 8, 12, 16, 23, 38, 56, 72, 91], 1) == 3bksl-nlassert all(etapespy-unddicho(list(range(1000)), v) <= 10 for v in range(-3, 1004))bksl-nlbksl-nl Valider ∞/∞ Télécharger Téléverser Recharger Sauvegarder

def etapespy-unddicho(L, x):bksl-nl """Nombre d'elements examines par la dichotomie."""bksl-nl ...bksl-nlbksl-nl

---

---

Je comprends. Compare avec \(\lfloor \log_2 n \rfloor + 1\) pour len(L) = 10.

Exercice C – Puissance rapide

Écris puissance_rapide(x, n) (\(n \ge 0\)) récursive : si n est pair, calcule y = puissance_rapide(x, n // 2) une seule fois et renvoie y * y ; sinon x * puissance_rapide(x, n - 1).

###

Lancer assert puissancepy-undrapide(2, 10) == 1024bksl-nlassert puissancepy-undrapide(3, 0) == 1bksl-nlassert puissancepy-undrapide(5, 1) == 5bksl-nlassert puissancepy-undrapide(2, 100) == 2 py-strpy-str 100bksl-nlassert all(puissancepy-undrapide(a, b) == a py-strpy-str b for a in range(-3, 5) for b in range(0, 30))bksl-nlbksl-nl Valider ∞/∞ Télécharger Téléverser Recharger Sauvegarder

def puissancepy-undrapide(x, n):bksl-nl """x puissance n par exponentiation rapide (recursive)."""bksl-nl ...bksl-nlbksl-nl

---

---

Je comprends. Que se passerait-il pour le nombre d'appels si tu écrivais deux fois l'appel sur n // 2 ?

Exercice D – Fusion de deux listes triées

Écris fusion(A, B) qui renvoie la liste triée contenant les éléments de A et de B, deux listes déjà triées, en un seul passage (deux indices).

J'anticipe. Écris la fusion de [2, 5, 9] et [1, 6, 7, 10] étape par étape.

###

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

def fusion(A, B):bksl-nl """Fusionne deux listes triees en une liste triee."""bksl-nl ...bksl-nlbksl-nl

---

---

Exercice E – Tri fusion

Écris tri_fusion(L) récursive qui renvoie une nouvelle liste triée. Tu peux réécrire ou réutiliser fusion : copie sa définition dans l'éditeur.

###

Lancer assert tripy-undfusion([5, 2, 9, 1, 7]) == [1, 2, 5, 7, 9]bksl-nlassert tripy-undfusion([]) == []bksl-nlassert tripy-undfusion([4]) == [4]bksl-nlassert tripy-undfusion([3, 3, 1, 2, 2]) == [1, 2, 2, 3, 3]bksl-nlassert all(tripy-undfusion(list(range(n, 0, -1))) == list(range(1, n + 1)) for n in range(0, 40))bksl-nlassert tripy-undfusion([8, 3, 5, 1, 9, 2, 7, 4, 6]) == sorted([8, 3, 5, 1, 9, 2, 7, 4, 6])bksl-nlbksl-nl Valider ∞/∞ Télécharger Téléverser Recharger Sauvegarder

def fusion(A, B):bksl-nl resultat = []bksl-nl i = 0bksl-nl j = 0bksl-nl while i < len(A) and j < len(B):bksl-nl if A[i] <= B[j]:bksl-nl resultat.append(A[i])bksl-nl i = i + 1bksl-nl else:bksl-nl resultat.append(B[j])bksl-nl j = j + 1bksl-nl return resultat + A[i:] + B[j:]bksl-nlbksl-nldef tripy-undfusion(L):bksl-nl """Liste triee (nouvelle liste), par tri fusion."""bksl-nl ...bksl-nlbksl-nl

---

---

Je comprends. Quel est le cas de base ? Quel est le variant ?

Exercice F – Multiplications de la puissance rapide

Écris nb_mult(n) qui renvoie le nombre de multiplications effectuées par puissance_rapide(x, n) : 0 si n == 0 ; 1 + nb_mult(n // 2) si n est pair ; 1 + nb_mult(n - 1) sinon.

J'anticipe. Pour n = 10, combien (exercice 3) ?

###

Lancer assert nbpy-undmult(0) == 0bksl-nlassert nbpy-undmult(1) == 1bksl-nlassert nbpy-undmult(10) == 5bksl-nlassert nbpy-undmult(16) == 5bksl-nlassert nbpy-undmult(1000) == 15bksl-nlassert all(nbpy-undmult(k) <= 2 py-str k.bitpy-undlength() for k in range(1, 5000))bksl-nlbksl-nl Valider ∞/∞ Télécharger Téléverser Recharger Sauvegarder

def nbpy-undmult(n):bksl-nl """Nombre de multiplications de puissancepy-undrapide(x, n)."""bksl-nl ...bksl-nlbksl-nl

---

---