Sept questions courtes sur les boucles imbriquées.
1.Une boucle externe effectue n tours ; à chaque tour, une boucle interne effectue m tours, dont le corps a un coût constant. Quel est le coût total ?
2.Quel est le coût de tri_a_bulles dans le pire des cas ?
3.Dans paire_plus_proche, pourquoi l’indice interne j part-il de i + 1 plutôt que de 0 ?
4.Parmi les affirmations suivantes sur le coût quadratique, lesquelles sont vraies ?
5.Quel est le coût, dans le pire cas, de la recherche naïve d’un motif de longueur m dans un texte de longueur n ?
6.Dans la démonstration de correction du tri à bulles, quel invariant est établi après le tour i de la boucle externe ?
7.Quand la boucle interne d’un algorithme à deux boucles a elle-même un comportement non trivial (comme dans recherche_motif), combien de niveaux d’invariants la méthode du cours recommande-t-elle d’utiliser ?
Soit a = [5, 3, 4].
Dérouler l’exécution de tri_a_bulles(a), en indiquant le contenu du tableau après chaque échange.
Passe i=0 :
Passe i=1 :
Le tableau final est [3, 4, 5], bien trié.
n=3. À la passe i=0, j parcourt range(n - 1 - i), soit j=0,1. À la passe i=1, j parcourt range(n - 1 - i), soit j=0 seulement.
Soit a = [4, 10, 7, 12].
Calculer ∣ai−aj∣ pour chacun des six couples (i,j) avec i<j.
∣a0−a1∣=6∣a0−a2∣=3∣a0−a3∣=8 ∣a1−a2∣=3∣a1−a3∣=2∣a2−a3∣=5
En déduire le couple (imin,jmin) renvoyé par paire_plus_proche(a).
Le plus petit écart est 2, atteint pour le couple (1,3) (soit a1=10 et a3=12). La fonction renvoie donc (1,3).
Encore 3 blocs dans ce document. Créer un compte ne demande qu'une adresse e-mail.