Solutions des exercices

1. Les algorithmes

Exercice 4. Forme mystère

L’algorithme suivant contrôle un crayon. Quelle forme dessine-t-il ?

Répéter 8 fois :
    Avance de 2 cm
    Tourne à droite de 60°

Solution 4. Forme mystère

Exercice 5. Nombre minimum

Ecrire un algorithme qui permet de trouver le plus petit nombre d’une liste. Penser à décomposer la solution en différentes étapes.

Appliquer votre algorithme à la liste [3, 6, 2, 8, 1, 9, 7, 5].

L’algorithme trouve-t-il la bonne solution ? Sinon, modifier votre algorithme afin qu’il trouve la bonne solution.

Solution 5. Nombre minimum

Exercice 6. Le prochain anniversaire

On souhaite déterminer l’élève dont la date d’anniversaire est la plus proche de la date d’aujourd’hui, dans le futur. Ecrire un algorithme qui permet de trouver cet élève (utiliser un langage familier). Penser à décomposer le problème en sous-problèmes.

Comparer votre solution à celle de la personne à côté de vous. Avez-vous procédé de la même manière ? Si non, expliquer vos raisonnements.

Un ordinateur peut-il réaliser les opérations décrites par votre algorithme ?

Solution 6. Le prochain anniversaire

Exercice 7. Echange de trois variables

Écrire un algorithme qui effectue la permutation circulaire des variables X, Y et Z : à la fin de l’algorithme, X contient la valeur de Z, Y la valeur de X et Z la valeur de Y. Pour rappel, une variable ne peut contenir qu’une valeur à la fois.

Conseil : mettez-vous à la place de la machine et représentez le contenu de chaque variable sous la forme d’un tiroir, dessinez le tiroir avec l’étiquette et son contenu après chaque opération de votre algorithme. Est-ce que l’algorithme donne le résultat attendu ? Si non, modifiez votre algorithme pour qu’il résolve le problème correctement.

Solution 7. Echange de trois variables

Exercice 8. Affectations

Quel est le résultat de la suite des trois affectations suivantes ?

Vérifier votre solution en représentant chaque variable et en y mettant des valeurs fictives. Suivre les opérations dans l’ordre et dessiner le contenu des variables après chaque étape.

X ← X + Y
Y ← X – Y
X ← X – Y

Solution 8. Affectations

2. Trie, cherche et trouve

Exercice 4. 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 4. L’algorithme de votre journée

Exercice 5. 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 5. Trois algorithmes de tri

Exercice 6. 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 6. Vérificateur de tri

Exercice 7. 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 7. Mondrian

3. Des algorithmes aux programmes

Exercice 1. Jeu de la devinette 🔌

Ecrire le programme suivant : le programme pense à un nombre au hasard. Lorsque vous lui proposez un nombre, il vous dit si «c’est plus» ou «si c’est moins» jusqu’à ce que vous ayez trouvé.

Solution 1. Jeu de la devinette 🔌

Exercice 2. Plus petit nombre 🔌

Transcrire l’algorithme de l’exercice qui permet de déterminer le plus petit nombre d’une liste, en un programme Python.

Solution 2. Plus petit nombre 🔌🔌

Exercice 3. Programmes de tri 🔌

Implémenter le tri à bulles et/ou le tri par insertion vus au cours.

Créer une liste qui contient les valeurs de 1 à n dans un ordre aléatoire, où n prend la valeur 10, par exemple. Vous pouvez utiliser la fonction shuffle() du module random.

Pour aller plus loin.

A l’aide du module time et de sa fonction time(), chronométrez le temps prend le tri d’une liste de 100, 500, 1000, 10000, 20000, 30000, 40000 puis 50000 nombres.

Noter les temps obtenus et affichez-les sous forme de courbe dans un tableur. Ce graphique permet de visualiser le temps d’exécution du tri en fonction de la taille de la liste. Que constatez‑vous ?

Sur la base de ces mesures, pouvez-vous estimer le temps que prendrait le tri de 100000 éléments ?

Lancer votre programme avec 100000 éléments et comparez le temps obtenu avec votre estimation.

Solution 3. Programmes de tri

Exercice 4. Bogosort 🔌

Coder l’algorithme du tri de Bogo en Python (voir chapitre 2 : Le saviez-vous ?).

Relancer l’algorithme plusieurs fois, en notant le nombre d’itération nécessaires pour qu’il termine.

A partir de quelle taille de liste cet algorithme est-il inutilisable ?

Solution 4. Tri de Bogo

Exercice 5. Fibonacci 🔌

Ecrire un algorithme qui calcule la suite des nombres de Fibonacci.

Traduire l’algorithme en une fonction Python.

Comparer avec les solutions trouvées par vos camarades de classe.

Solution 5. Fibonacci 🔌

Exercice 3.4. Une question à un million

Si une instruction prend 10-6 secondes, combien de temps faut-il pour trier un tableau d’un million d’éléments avec le tri à sélection comparé au tri rapide (sans tenir compte de la constante) ?

Solution 3.4. Une question à un million

Exercice 3.5. Une question de pivot

Trier le tableau suivant avec l’algorithme de tri rapide : [3, 6, 8, 7, 1, 9, 4, 2, 5] à la main, en prenant le dernier élément comme pivot. Représenter l’état du tableau lors de toutes les étapes intermédiaires.

Est-ce que le choix du pivot est important ?

Solution 3.5. Une question de pivot

Exercice 3.6. Une question de sélection

Trier le tableau suivant avec l’algorithme de tri par sélection : [3, 6, 8, 7, 1, 9, 4, 2, 5] à la main. Représenter l’état du tableau lors de toutes les étapes intermédiaires.

Solution 3.6. Une question de sélection

Exercice 3.7. Une question d’insertion

Trier le tableau suivant avec l’algorithme de tri par insertion : [3, 6, 8, 7, 1, 9, 4, 2, 5] à la main. Représenter l’état du tableau lors de toutes les étapes intermédiaires.

Solution 3.7. Une question d’insertion

Exercice 3.8. Une question de bulles

Trier le tableau suivant avec l’algorithme de tri à bulles : [3, 6, 8, 7, 1, 9, 4, 2, 5] à la main. Représenter l’état du tableau lors de toutes les étapes intermédiaires.

Solution 3.8. Une question de bulles

Exercice 3.9. Une question de chronomètre 🔌

Créer une liste qui contient les valeurs de 1 à n dans un ordre aléatoire, où n prend la valeur 100, par exemple. Indice : utiliser la fonction shuffle() du module random.

Implémenter au moins deux des trois algorithmes de tri vu au cours. A l’aide du module time et de sa fonction time(), chronométrer le temps prend le tri d’une liste de 100, 500, 1000, 10000, 20000, 30000, 40000 puis 50000 nombres.

Noter les temps obtenus et les afficher sous forme de courbe dans un tableur. Ce graphique permet de visualiser le temps d’exécution du tri en fonction de la taille de la liste. Que peut-on constater ?

Sur la base de ces mesures, peut-on estimer le temps que prendrait le tri de 100000 éléments ?

Lancer votre programme avec 100000 éléments et comparer le temps obtenu avec votre estimation.

Solution à compléter

Exercice 4.2. Une question de fusion

Trier le tableau suivant avec l’algorithme de tri par fusion : [3, 6, 8, 7, 1, 9, 4, 2, 5] à la main. Représenter l’état du tableau lors de toutes les étapes intermédiaires.

Solution à compléter

Exercice 4.3. Dans l’autre sens 🔌

En Python, proposer une fonction qui inverse l’ordre des lettres dans un mot. Vous pouvez parcourir les lettres du mot directement ou à travers un indice.

Proposer une autre fonction qui inverse l’ordre des lettres dans un mot de manière récursive.

Solution 4.3. Dans l’autre sens 🔌

Exercice 4.4. Factorielle 🔌

La fonction factorielle n! en mathématiques est le produit de tous les nombres entiers jusqu’à n. C’est une des fonctions les plus simples à calculer de manière récursive. Elle peut être définie comme ceci :

n! = (n-1)! * n

Programmer cette fonction de manière récursive en Python. Proposer également une implémentation itérative de la factorielle où les éléments de 1 à n sont traités l’un après l’autre.

Solution 4.4. Factorielle 🔌