C16 : Exercices
Méthode glouton
C16.E1 : Optimisation de la visite d'un parc d'attraction (sans ordinateur)
Vous visitez un parc d'attractions proposant des spectacles à différents horaires. Voici les horaires des différents spectacles :
| Spectacle | A | B | C | D | E | F | G | H | I | J |
|---|---|---|---|---|---|---|---|---|---|---|
| Horaire | 10 h à 11 h | 10 h 30 à 11 h 30 | 11 h à 12 h 30 | 11 h 30 à 12 h | 12 h à 13 h | 13 h à 15 h | 13 h 30 à 14 h | 14 h à 15 h 30 | 15 h à 16 h | 16 h à 17 h 30 |
Vous avez remarqué qu'il n'est pas possible d'assister à tous les spectacles puisque certains ont lieu à des moments communs. Vous souhaitez assister à un maximum de spectacles sur la journée. Quels spectacles devez-vous choisir ?
Voici deux stratégies gloutonnes possibles :
Stratégie n°1 : choisir le spectacle dont l'heure de début arrive le plus tôt (parmi les spectacles dont l'heure de début est postérieure aux créneaux des spectacles déjà choisis). Cette stratégie est basée sur l'idée que moins on attend entre deux spectacles, plus on en verra.
Stratégie n°2 : choisir le spectacle dont l'heure de fin arrive le plus tôt (parmi les spectacles dont l'heure de début est postérieure aux créneaux des spectacles déjà choisis). Cette stratégie est basée sur l'idée que plus un spectacle finit tôt, plus il reste de temps pour en voir d'autres.
1. Appliquez ces deux stratégies au problème.
2. Laquelle donne la meilleure solution ?
C16.E2 : La meilleure somme de cinq nombres
On dispose d'une liste de nombres entiers.
On cherche à sélectionner cinq nombres de cette liste :
- - de façon à ce que la somme de ces cinq nombres soit maximale ;
- - et sans que ces nombres soient voisins.
On choisit l'algorithme suivant :
- - Au départ, tous les nombres de la liste sont considérés comme disponibles ;
- - A chacune (ici cinq étapes), on choisit le plus grand nombre parmi les nombres disponibles et on rend indisponibles le nombre retenu et ses deux voisins.
1. Application à un exemple
On considère la liste suivante :
| 15 | 4 | 20 | 17 | 11 | 8 | 11 | 16 | 7 | 14 | 2 | 7 | 5 | 17 | 19 | 18 | 4 | 5 | 13 | 8 |
1.a. Appliquer, à la main, l'algorithme proposé et indiquer le résultat obtenu.
1.b. L'algorithme utilisé a-t-il donné la solution optimale ?
2. Écrire une fonction maxi5(li:list) -> list qui prend une liste de nombres entiers en paramètres et renvoie la liste des cinq nombre obtenu en appliquant l'algorithme proposé.