NSI (terminale) · Chapitre 8 · Exercice d'entraînement
Couvrir des maisons avec des antennes
Les algorithmes gloutons · Planifier et couvrir · niveau 1 (application)
Énoncé
Couvrir des maisons avec des antennes.
Des maisons sont situées le long d'une route droite, aux kilomètres [1, 2, 4, 9, 10, 16, 18, 25]. Une antenne placée au kilomètre couvre toutes les maisons situées entre les kilomètres et . On veut couvrir toutes les maisons avec le moins d'antennes possible.
- Stratégie gloutonne : on prend la première maison non couverte (la plus à gauche) et on place une antenne le plus à droite possible tout en la couvrant, soit km plus loin. Appliquer cette stratégie à la main.
- Écrire une fonction
antennes(maisons, r)qui renvoie la liste des positions des antennes, pour un rayon de couverture .
Un exercice à chercher : son corrigé n'est pas publié. Sur Adloun, le tuteur guide par questions, sans donner la réponse.