Coloriage de carte⚓︎
D'après 2023, Métropole, J1, Ex. 3
Cet exercice traite de programmation orientée objet en Python et d’algorithmique.
Un pays est composé de différentes régions. Deux régions sont voisines si elles ont au moins une frontière en commun. L'objectif est d'attribuer une couleur à chaque région sur la carte du pays sans que deux régions voisines aient la même couleur et en utilisant le moins de couleurs possibles. La figure 1 ci-dessous donne un exemple de résultat de coloration des régions de la France métropolitaine.
Rappels
On rappelle quelques fonctions et méthodes des tableaux (le type list
en Python) qui pourront être utilisées dans cet exercice :
len(tab)
: renvoie le nombre d'éléments du tableau tab ;tab.append(elt)
: ajoute l'élément elt en fin de tableau tab ;tab.remove(elt)
: enlève la première occurrence de elt de tab si elt est dans tab. Provoque une erreur sinon.
Exemples :
len([1, 3, 12, 24, 3])
renvoie5
;- avec
tab = [1, 3, 12, 24, 3]
, l’instructiontab.append(7)
modifietab
en[1, 3, 12, 24, 3, 7]
; - avec
tab = [1, 3, 12, 24, 3]
, l’instructiontab.remove(3)
modifietab en [1, 12, 24, 3]
.
Les deux parties de cet exercice forment un ensemble. Cependant, il n’est pas nécessaire d’avoir répondu à une question pour aborder la suivante. En particulier, on pourra utiliser les méthodes des questions précédentes même quand elles n’ont pas été codées.
PARTIE 1⚓︎
On considère la classe Region qui modélise une région sur une carte et dont le début de l'implémentation est :
class Region:
'''Modélise une région d'un pays sur une carte.'''
def __init__(self, nom_region):
"""
initialise une région
: param nom_region (str) le nom de la région
"""
self.nom = nom_region
# tableau des régions voisines(instances de la classe Region), vide au départ
self.voisines = []
# tableau des couleurs disponibles pour colorier la région
self.couleurs_disponibles = ['rouge', 'vert', 'bleu', 'jaune', 'orange', 'marron']
# couleur attribuée à la région et non encore choisie au départ
self.couleur_attribuee = None
- Associer, en vous appuyant sur l’extrait de code précédent, les noms
nom
,voisines
,couleurs_disponibles
etcouleur_attribuee
au terme qui leur correspond parmi : objet, attribut, méthode ou classe. - Indiquer le type du paramètre nom_region de la méthode
__init__
de la classeRegion
. - Donner une instruction permettant de créer une instance nommée
ge
de la classeRegion
correspondant à la région dont le nom est"Grand Est"
. - Recopier et compléter la méthode
premiere_couleur_disponible
de la classeRegion
qui renvoie la première couleur du tableau des couleurs disponibles supposé non vide.🐍 Script Pythondef premiere_couleur_disponible(self): ...
Réponse
def premiere_couleur_disponible(self):
return self.couleurs_disponibles[0]
- Recopier et compléter la méthode nb_voisines de la classe Region qui renvoie le nombre de régions voisines.
🐍 Script Python
def nb_voisines(self) : ...
Réponse
def nb_voisines(self) :
return len(self.voisines)
- Compléter la méthode de la classe Region qui renvoie un valeur booléenne qui vaut True si une couleur a été attribuée à cette région et False sinon.
🐍 Script Python
def est_coloriee(self): ...
Réponse
def est_coloriee(self) :
return not self.couleur_attribuee is None
- Compléter la méthode
retire_couleur
de la classeRegion
qui retire lacouleur
passée en paramètre du tableau de couleurs disponibles de la région si cette couleur est dans ce tableau.🐍 Script Pythondef retire_couleur(self, couleur): ...
Réponse
def retire_couleur(self) :
return ...
- Compléter la méthode
est_voisine
de la classeRegion
qui renvoie une valeur booléenne à la valeurTrue
si la region passée en paramètre est une voisine etFalse
sinon.
Contrainte
On utilisera une boucle.
def est_voisine(self, region):
...
Réponse
def est_voisine(self, region) :
return ...
Partie 2⚓︎
Dans cette partie :
- on considère qu’on dispose d’un ensemble d’instances de la classe
Region
pour lesquelles l’attributvoisines
a été renseigné ; - on pourra utiliser les méthodes de la classe Region évoquées dans les questions de la partie 1 :
premiere_couleur_disponible
nb_voisines
est_coloriee
retire_couleur
est_voisine
On a créé une classe Pays
:
- cette classe modélise la carte d’un pays composé de régions ;
- l’unique attribut regions
de cette classe est un tableau (type list
en Python) dont les éléments sont des instances de la classe Region
.
- Recopier et compléter la méthode de la classe Pays qui renvoie un tableau dont les éléments sont les régions du pays sans couleur attribuée. :
🐍 Script Python
def regions_non_coloriees(self): ...
Réponse
def regions_non_coloriees(self):
regions_incolores = [region for region in self.regions if not region.est_coloriee()]
return regions_incolores
-
On considère la méthode de la classe Pays ci-dessous.
🐍 Script Pythona. Expliquer dans quel cas cette méthode renvoiedef renvoie_max(self): nb_voisines_max = -1 region_max = None for reg in self.renvoie_tab_regions_non_coloriees(): if reg.renvoie_nb_voisines() > nb_voisines_max: nb_voisines_max = reg.renvoie_nb_voisines() region_max = reg return region_max
None
. b. Indiquer, dans le cas où cette méthode ne renvoie pasNone
, les deux particularités de la région renvoyée. -
Coder la méthode
colorie
de la classePays
qui choisit une couleur pour chaque région du pays de la façon suivante : - On récupère la région non coloriée qui possède le plus de voisines.
- Tant que cette région existe :
- La couleur attribuée à cette région est la première couleur disponible dans son tableau de couleurs disponibles.
- Pour chaque région voisine de la région :
- si la couleur choisie est présente dans le tableau des couleurs disponibles de la région voisine alors on la retire de ce tableau.
- On récupère à nouveau la région non coloriée qui possède le plus de voisines.