Algorithmique II¶

2. Trie, cherche et trouve¶

Solutions des exercices¶

Exercice 1

Voir partie Apprendre.

Exercice 2

Voir partie Apprendre.

Exercice 3

Voir partie Apprendre.

Exercice 4

Voir partie Apprendre.

Exercice 5 – L’algorithme de votre journée

Réfléchissez à votre journée : y a-t-il des actions qui se retrouvent chaque jour ouvrable ? Arrivez-vous à esquisser un algorithme que vous suivez sans que vous en ayez conscience ?

Solution 5 – L’algorithme de votre journée

Exercice 6 – Trois algorithmes de tri

Trier la liste [2,5,3,4,7,1,6] en utilisant les trois algorithmes de tri vus adans le cours. Représenter l’état de la liste après chaque étape.

Solution 6 – Trois algorithmes de tri

Cliquer ici pour voir la réponse

Voici le détail de toutes les étapes intermédiaires des trois algorithmes de tri.

Tri par insertion :

[2,5,3,4,7,1,6]  # on considère le 2e élément et on l'ordonne par rapport au premier élément
[2,5,3,4,7,1,6]  # on considère le 3e élément et on l'ordonne par rapport aux deux premiers éléments
[2,3,5,4,7,1,6]  # on considère le 4e élément et on l'insère au bon endroit du tableau déjà trié
[2,3,4,5,7,1,6]  # on considère le 5e élément et on l'insère au bon endroit du tableau déjà trié
[2,3,4,5,7,1,6]  # on considère le 6e élément et on l'insère au bon endroit du tableau déjà trié
[1,2,3,4,5,7,6]  # on considère le 7e élément et on l'insère au bon endroit du tableau déjà trié
[1,2,3,4,5,6,7]

Tri par sélection :

[2,5,3,4,7,1,6]  # on sélectionne le plus petit élément et on l'échange avec le premier élément
[1,5,3,4,7,2,6]  # on sélectionne le 2e plus petit élément et on l'échange avec le 2e élément 
[1,2,3,4,7,5,6]  # on sélectionne le 3e plus petit élément et on l'échange avec le 3e élément 
[1,2,3,4,7,5,6]  # on sélectionne le 4e plus petit élément et on l'échange avec le 4e élément 
[1,2,3,4,5,7,6]  # on sélectionne le 5e plus petit élément et on l'échange avec le 5e élément 
[1,2,3,4,5,6,7]  # on sélectionne le 6e plus petit élément et on l'échange avec le 6e élément 

Tri à bulles :

[2,5,3,4,7,1,6]  # on compare 2 et 5
[2,5,3,4,7,1,6]  # on compare 5 et 3 et on les déplace
[2,3,5,4,7,1,6]  # on compare 5 et 4 et on les déplace
[2,3,4,5,7,1,6]  # on compare 5 et 7
[2,3,4,5,7,1,6]  # on compare 7 et 1 et on les déplace
[2,3,4,5,1,7,6]  # on compare 7 et 6 et on les déplace, tableau trié [7]
[2,3,4,5,1,6,7]  # on compare 2 et 3
[2,3,4,5,1,6,7]  # on compare 3 et 4
[2,3,4,5,1,6,7]  # on compare 4 et 5
[2,3,4,1,5,6,7]  # on compare 5 et 1 et on les déplace
[2,3,4,1,5,6,7]  # on compare 5 et 6, tableau trié [6, 7]
[2,3,4,1,5,6,7]  # on compare 2 et 3
[2,3,4,1,5,6,7]  # on compare 3 et 4
[2,3,1,4,5,6,7]  # on compare 4 et 1 et on les déplace
[2,3,1,4,5,6,7]  # on compare 4 et 5, tableau trié [5, 6, 7]
[2,3,1,4,5,6,7]  # on compare 2 et 3 
[2,1,3,4,5,6,7]  # on compare 3 et 1 et on les déplace
[2,1,3,4,5,6,7]  # on compare 3 et 4, tableau trié [4, 5, 6, 7]
[1,2,3,4,5,6,7]  # on compare 2 et 1 et on les déplace
[1,2,3,4,5,6,7]  # on compare 2 et 3, tableau trié [3, 4, 5, 6, 7]
[1,2,3,4,5,6,7]  # on compare 1 et 2, tableau trié [2, 3, 4, 5, 6, 7]

Exercice 7 – Vérificateur de tri

Ecrivez un algorithme qui vérifie si une liste est triée.

Que prend l’algorithme en entrée et que retourne-t-il en sortie ?

Demandez ensuite à un autre élève de suivre les opérations décrites par votre algorithme. Est-ce que votre algorithme est correct ?

Comparer vos algorithmes. Sont-ils différents ?

Solution 7 – Vérificateur de tri

Exercice 8 – Mondrian

Analysez les œuvres cubistes de Piet Mondrian. Trouvez un algorithme qui permet de créer une œuvre qui pourrait être attribuée à Mondrian.

Solution 8 – Mondrian