defmystere(l1,l2):n1=len(l1)n2=len(l2)lst=[]# initialisation de la fusion de l1 et l2 i1=0# indice qui sert à parcourir l1i2=0# indice qui sert à parcourir l2whilei1<n1andi2<n2:ifl1[i1]<l2[i2]:lst.append(l1[i1])i1=i1+1else:lst.append(l2[i2])i2=i2+1returnlstmystere([2,3,5,8],[1,4])
Recopier sur votre cahier le tableau suivant qui décrit le déroulement de l'exécution de : mystere([2, 3, 5, 8],[1, 4]) et le compléter.
Il y a une ligne par tour de boucle.
Pour vous aider, nous avons rajouté une colonne pour l1 et une pour l2. Vous pourrez entourer à chaque étape, dans une de ces colonnes, l'élément qui sera ajouté à lst (en gras ici)
i1
i2
l1
l2
lst
0
0
[2, 3, 5, 8]
[1, 4]
[1]
0
1
[2, 3, 5, 8]
[1, 4]
[1, 2]
...
...
...
...
...
...
Solution
i1
i2
l1
l2
lst
0
0
[2, 3, 5, 8]
[1, 4]
[1]
0
1
[2, 3, 5, 8]
[1, 4]
[1, 2]
1
1
[2, 3, 5, 8]
[1, 4]
[1, 2, 3]
2
1
[2, 3, 5, 8]
[1, 4]
[1, 2, 3, 4]
2
2
😥 Nous observons que les deux listes n'ont pas été complètement fusionnées, car nous avons "épuisé" tous les éléments de l2.
👉 Par contre, il est certain que les éléments restants de l1 qui n'ont pas été fusionnés, sont triés, et plus grands que tous les éléments déjà présents dans lst.
🤗 Pour obtenir la liste complètement fusionnée, il suffit donc d'exécuter : lst + [5, 8] c'est à dire lst + l1[i1:]
💻 A vous de jouer 1
Compléter le script suivant :
###(Dés-)Active le code après la ligne # Tests (insensible à la casse) (Ctrl+I)
Entrer ou sortir du mode "deux colonnes" (Ctrl+Clic pour inverser les colonnes)
Entrer ou sortir du mode "plein écran"
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
😥 Le problème, c'est que les "slices" ne sont pas vraiment au programme de NSI, et que leur utilisation n'est pas toujours efficace. Essayons une version qui n'utilise pas de "slices".
💻 A vous de jouer 2
Compléter le script suivant :
###(Dés-)Active le code après la ligne # Tests (insensible à la casse) (Ctrl+I)
Entrer ou sortir du mode "deux colonnes" (Ctrl+Clic pour inverser les colonnes)
Entrer ou sortir du mode "plein écran"
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
Nous disposons d'un tableau (type list de Python) de taille n.
Son premier rang est donc 0 et son dernier rang n-1.
On notera t[a -> b] la liste constituée des éléments de rang compris entre a et b (compris) de la liste t.
La fonction tri_fusion fait appel à la fonction fusion qui permet de fusionner deux listes triées en une liste triée.
fonction tri_fusion(t)
"""
entrée ː un tableau t
sortie ː renvoie un autre tableau qui correspond au tableau t trié
"""
n = longueur(t)
si n ≤ 1
renvoyer t
sinon
m = n//2
renvoyer fusion(tri_fusion(t[0 -> m-1]), tri_fusion(t[m -> n-1]))
La terminaison est justifiée par la décroissance stricte de n à chaque appel récursif.
💻 A vous de jouer 3
Compléter le script suivant :
###(Dés-)Active le code après la ligne # Tests (insensible à la casse) (Ctrl+I)
Entrer ou sortir du mode "deux colonnes" (Ctrl+Clic pour inverser les colonnes)
Entrer ou sortir du mode "plein écran"
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
deffusion(l1,l2):""" Précondition : l1 et l2 sont deux listes triées Postcondition : la fonction renvoie une liste triée constituée de la fusion de l1 et l2 Exemple : fusion([2, 3, 5, 8],[1, 4]) renvoie [1, 2, 3, 4, 5, 8] """n1=len(l1)n2=len(l2)lst=[]# initialisation de la fusion de l1 et l2 i1=0# indice qui sert à parcourir l1i2=0# indice qui sert à parcourir l2whilei1<n1andi2<n2:ifl1[i1]<l2[i2]:lst.append(l1[i1])i1=i1+1else:lst.append(l2[i2])i2=i2+1ifi1==n1:returnlst+l2[i2:]ifi2==n2:returnlst+l1[i1:]deftri_fusion(lst):""" Précondition : lst est une liste Postcondition : la fonction renvoie une liste qui est la liste triée """n=len(lst)ifn<=1:returnlstelse:m=n//2returnfusion(tri_fusion(lst[:m]),tri_fusion(lst[m:]))
# Tests
(insensible à la casse)(Ctrl+I)
(Ctrl+Clic pour inverser les colonnes)