Indices sur certains exercices sur les tableaux
Exercice 7
Écrire un algorithme triant un tableau dans l’ordre croissant.
- Implémenter le tri bulle qui consiste, tant que le tableau n’est pas trié à parcourir le tableau et si deux éléments consécutifs sont dans le mauvais ordre, les inverser.
- Implémenter le tri sélection : trouver le minimum du tableau de départ, le mettre dans le tableau
resultat; fabriquer un tableau qui sera le tableau initial privé de ce minimum ; dans ce deuxième tableau, trouver le minimum et l’ajouter au tableauresultat; fabriquer un tableau qui sera le tableau initial privé de ce minimum ; …
Exercice 14
Voici à quoi ressemble le tableau pour la somme 49 :
| 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 1 |
| 2 | 0 | 0 | 2 |
| 3 | 0 | 0 | 3 |
| 4 | 0 | 0 | 4 |
| 5 | 0 | 0 | 5 |
| 6 | 0 | 0 | 6 |
| 7 | 0 | 0 | 7 |
| 8 | 0 | 0 | 8 |
| 9 | 0 | 0 | 9 |
| 1 | 0 | 1 | 0 |
| 2 | 0 | 1 | 1 |
| 3 | 0 | 1 | 2 |
| 4 | 0 | 1 | 3 |
| 5 | 0 | 1 | 4 |
| 6 | 0 | 1 | 5 |
| 7 | 0 | 1 | 6 |
| 8 | 0 | 1 | 7 |
| 9 | 0 | 1 | 8 |
| 10 | 0 | 1 | 9 |
| 2 | 0 | 2 | 0 |
| 3 | 0 | 2 | 1 |
| 4 | 0 | 2 | 2 |
| 5 | 0 | 2 | 3 |
| 6 | 0 | 2 | 4 |
| 1 | 1 | 0 | 0 |
| 2 | 1 | 0 | 1 |
| 3 | 1 | 0 | 2 |
| 4 | 1 | 0 | 3 |
| 5 | 1 | 0 | 4 |
| 3 | 0 | 3 | 0 |
| 4 | 0 | 3 | 1 |
| 5 | 0 | 3 | 2 |
| 6 | 0 | 3 | 3 |
| 7 | 0 | 3 | 4 |
| 2 | 1 | 1 | 0 |
| 3 | 1 | 1 | 1 |
| 4 | 1 | 1 | 2 |
| 5 | 1 | 1 | 3 |
| 6 | 1 | 1 | 4 |
| 4 | 0 | 4 | 0 |
| 5 | 0 | 4 | 1 |
| 6 | 0 | 4 | 2 |
| 7 | 0 | 4 | 3 |
| 8 | 0 | 4 | 4 |
| 3 | 1 | 2 | 0 |
| 4 | 1 | 2 | 1 |
| 5 | 1 | 2 | 2 |
| 6 | 1 | 2 | 3 |
| 7 | 1 | 2 | 4 |
En première colonne, le nombre minimal de pièces, puis la décomposition en pièces (nombre de pièces de 25 en 2-ième colonne, pièces de 10 en 3-ième colonne et pièces de 1 en 4-ième colonne).
Si je veux ajouter une ligne (pour la somme 50), il me suffit de regarder les lignes correspondant aux somme 49, 40 et 25 (je peux prendre les mêmes pièces que pour 49 et ajouter une pièce de 1 ou les pièces de 40 et ajouter une pièce de 10…). Ici :
| 1 | 1 | 0 | 0 | (25) |
| 4 | 0 | 4 | 0 | (40) |
| 7 | 1 | 2 | 4 | (49) |
L’optimal est ici de prendre la ligne 25 et d’ajouter une pièce de 25. Et donc la ligne suivante sera
| 2 | 2 | 0 | 0 |
Il faut donc généraliser ce raisonnement pour remplir le tableau pour trouver le nombre optimal de pièces pour chaque somme. Attention à ne pas essayer d’accéder à des lignes négatives (pour la somme 23, on ne peut pas ajouter une pièce de 25 à la somme -2…).
Exercice 15
Cet exercice est difficile à résoudre de façon exacte. Vous allez donc devoir chercher un algorithme qui donne des réponses qui pourraient ne pas être optimale.
Votre algorithme doit trouver une liste de poids dont la somme est inférieure à la capacité du sac. Il faut également qu’on ne puisse plus ajouter d’éléments sans dépasser cette capacité.
On peut penser à un algorithme glouton.
On peut essayer de faire de la programmation dynamique comme dans l’exercice précédent. Ici, cela signifie calculer les éléments que l’on peut mettre dans un sac à dos de capacité 0, puis de capacité 1, puis de capacité 2, etc. pour en déduire finalement ce que l’on peut mettre dans le sac à dos de départ.