Correction du DS ITC N°5 : CCINP2024¶
Problème 1: Colorier un graphe¶
1. Introduction sur un exemple¶
Q1¶
In [1]:
M=[[0,1,0,1, 1,0,1,1],
[1,0,1,1, 0,0,0,0],
[0,1,0,1, 0,0,0,0],
[1,1,1,0, 1,0,0,0],
[1,0,0,1,0,1,1,1],
[0,0,0,0,1,0,1,1],
[1,0,0,0,1,1,0,1],
[1,0,0,0,1,1,1,0]]
Chaque sommet est associé à une ligne. $M_{i,j}$ vaut 1 s'il existe une arête entre le sommet $i$ et le sommet $j$, 0 sinon. M est symétrique car le graphe est non orienté.
Q2¶
In [2]:
LA=[[1,3,4,6,7],[0,2,3],[1,3],[0,1,2,4],[0,3,5,6,7],[4,6,7],[0,4,5,7],[0,4,5,6]]
In [3]:
LA[7]
Out[3]:
[0, 4, 5, 6]
Q3¶
Marice d'ajacence :
- avantages : opération matricielle ; déterminer s'il existe une arête entre les sommets $i$ et $j$ est à coût constant.
- inconvénients : obtenir la liste des voisins est à coût linéaire ; difficultés pour faire des sous graphes (en enlevant un sommet du graphe, tous les sommets doivent être renommés) ; occupation en mémoire plus importante.
Liste d'ajacence :
- avantages : faible occupation en mémoire, accès à coût constant à la liste des voisins.
- inconvénients : déterminer si deux sommets sont adjacents est à coût linéaire.
Q4¶
In [4]:
for i in range(len(LA)):
print(len(LA[i])) # degré = longueur d'une liste d'adjacence
5 3 2 4 5 3 4 4
2. Tester si une coloration est valide¶
Q5¶
In [5]:
def voisins(i:int, j:int, La:list)->bool:
"""Teste si les sommets i et j sont reliés par une arète"""
return j in La[i]
# version plus longue mais de même complexité
def voisins(i:int, j:int, La:list)->bool:
"""Teste si les sommets i et j sont reliés par une arète"""
for v in La[i]:
if v == j:
return True
return False
In [6]:
voisins(0,5,LA)
Out[6]:
False
In [7]:
voisins(0,7,LA)
Out[7]:
True
Q6¶
In [8]:
def coloration_valide(La:list, C:list)->bool:
"""Teste si la coloration est valide (pas de voisin avec la même couleur)"""
for sommet in range(len(La)): # pour chaque sommet
for voisin in La[sommet]: # on vérifie que les voisins ont une couleur différente
if C[voisin]==C[sommet]:
return False
return True
Q7¶
Complexité quadratique en $O(n^2)$ dans le pire des cas, si le graphe est complet.
3.Un algorithme intuitif de coloration¶
Q8¶
In [9]:
n = len(LA)
In [10]:
C = [-1 for i in range(n)]
C = [-1] * n # répétition utilisable car -1 est un entier, donc non mutable (non modifiable)
In [11]:
C
Out[11]:
[-1, -1, -1, -1, -1, -1, -1, -1]
Q9¶
In [12]:
def colore_sommet(C:list, s:int, La:list):
#ondétermine la liste des couleurs des voisins de s déjà colorés
coul_vois = []
for voisin in La[s]:
if C[voisin] != -1:
coul_vois.append(C[voisin])
#coul_vois est maintenant déterminée et on recherche la
#plus petite couleur,notée num_coul, absente de coul_vois:
num_coul = 0
while num_coul in coul_vois:#On suppose qu'il existe une solution
num_coul = num_coul + 1
#la valeur num_coul trouvée devient la couleur du sommet s:
C[s] = num_coul
In [13]:
Ctest=[0,1,-1,-1,-1,-1,-1,-1]
colore_sommet(Ctest,2,LA)
Ctest
Out[13]:
[0, 1, 0, -1, -1, -1, -1, -1]
Q10¶
In [14]:
def colorer1(La:list)->list:
n = len(La)
C = [-1] * n
for sommet in range(n): # pour chaque sommet
colore_sommet(C, sommet, La) # on le colorie en mettant à jour la liste C
return C
In [15]:
colorer1(LA)
Out[15]:
[0, 1, 0, 2, 1, 0, 2, 3]
Q11¶
In [16]:
def colorer2(La:list, ordre:list)->list:
C=[-1] * len(La)
for sommet in ordre: # pour chaque sommet de la liste ordre
colore_sommet(C, sommet, La) # on le colorie en mettant à jour la liste C
return C
Q12¶
In [17]:
colorer2(LA, [7,6,5,4,3,2,1,0])
Out[17]:
[4, 2, 1, 0, 3, 2, 1, 0]
On utlise 5 couleurs alors qu'on en utilisait 4 précédemment.
4 Variante de Welsh- Powell¶
Q13¶
In [18]:
LA = [[1,2], [0,2,3], [0,1,3], [1,2,4], [3]]
In [19]:
def degre(La: list)->list:
liste_deg = []
for i in range(len(La)): # pour chaque sommet
liste_deg.append(len(La[i])) # son degré est la longueur de la liste de ses voisins
return liste_deg
def degre(La: list)->list:
liste_deg = []
for Vi in La: # pour liste de voisins
liste_deg.append(len(Vi)) # son degré est la longueur de la liste de ses voisins
return liste_deg
In [20]:
degre(LA)
Out[20]:
[2, 3, 3, 3, 1]
Q14¶
In [21]:
# A retenir :
def init (n:int)->list:
return[[] for i in range(n)] # chaque élément est une liste, donc mutable, on ne peut pas utiliser la répétition !
# autre version qui fonctionne, de même complexité
def init(n:int)->list:
L = []
for i in range(n):
L.append([])
return L
In [22]:
init(3)
Out[22]:
[[], [], []]
In [23]:
# pour les tétus de la répétition, un exemple de ce que cela fait :
tmp = [[]]*5 # A oublier. On ne peut pas construire une liste de liste de cette manière, cf. effet de bord ci-dessous
print(tmp) # on a l'impression que cela donne le résultat attendu
tmp[0].append(1) # on ajoute un élément à la première liste
print(tmp) # et toutes les listes sont modifiées, car ce sont toutes les mêmes !! Ce n'est pas ce qui est attendu !
[[], [], [], [], []] [[1], [1], [1], [1], [1]]
Q15¶
In [24]:
def ranger(LA:list)->list:
n = len(LA)
R = init(n)
liste_deg = degre(LA)
for i in range(n): # pour chaque sommet
R[liste_deg[i]].append(i)
return R
# la version proposée permet une complexité linéaire !
In [25]:
ranger(LA)
Out[25]:
[[], [4], [0], [1, 2, 3], []]
Q16¶
In [26]:
# version à retenir
def renverse(L:list)->list:
n = len(L)
return [L[n-1-i] for i in range(n)]
In [27]:
renverse([1,2,3,4])
Out[27]:
[4, 3, 2, 1]
Q17¶
In [28]:
def trier_sommets(LA:list)->list:
"""liste des sommets triés dans l'ordre décroissant de leur degré"""
Rdec = renverse(ranger(LA))
sommet_trie = []
for element in Rdec:
for sommet in element:
sommet_trie.append(sommet)
return sommet_trie
In [29]:
trier_sommets(LA)
Out[29]:
[1, 2, 3, 0, 4]
Q18¶
Complexité de ranger : $O(n)$
Complexité de renverse : $O(n)$
Dans la double boucle for imbriquée, il n'y a que $n$ éléments à stockés. La complexité globale est donc une complexité linéaire.
Q19¶
In [30]:
def colorer3(LA:list)->list:
ordre = trier_sommets(LA) # il faut utiliser les fonctions précédentes !
return colorer2(LA,ordre)
La complexité est toujours quadratique en raison de la complexité de colorer2.
Q20¶
In [31]:
colorer3(LA)
Out[31]:
[2, 0, 1, 2, 0]
4 couleurs
Problème 2 : Le jeu de l'awalé¶
Représentation du jeu¶
In [32]:
def initialisation(nom_joueur1,nom_joueur2):
jeu = {}
jeu['joueur1'] = nom_joueur1
jeu['joueur2'] = nom_joueur2
jeu['score'] = [0,0]
jeu['n'] = 0
jeu['plateau'] = [4]*12 # répétition possible car 4 est un entier, donc non mutable
return jeu
In [33]:
testjeu = initialisation('Alice','Bob')
Q21¶
In [34]:
def tour_joueur1(jeu):
return jeu['n']%2 == 0
In [35]:
tour_joueur1(testjeu)
Out[35]:
True
Q22¶
In [36]:
# Il faut échanger les termes d'indices de 0 à 5 avec ceux d'indices de 6 à 11
# plusieurs versions possibles
def tourner_plateau(jeu:dict)->None:
plateau = jeu['plateau']
debut = plateau[:6] # nouvelle liste comprenant les 6 premiers termes
fin = plateau[6:] # les 6 derniers termes
jeu['plateau'] = fin + debut # utilisation de la concaténation de liste
def tourner_plateau(jeu:dict)->None:
L = []
for i in range(12):
L.append(jeu['plateau'][(6+i)%12]) # par recopie des termes à partir de 6, modulo 12
jeu['plateau'] = L
def tourner_plateau(jeu:dict)->None:
for i in range(6):
jeu['plateau'][i], jeu['plateau'][6+i] = jeu['plateau'][6+i], jeu['plateau'][i] # par échange des termes d'indices i et i+6
In [37]:
testjeu['plateau']=[0,0,2,0,16,5,2,1,0,1,0,1]
tourner_plateau(testjeu)
testjeu['plateau']
Out[37]:
[2, 1, 0, 1, 0, 1, 0, 0, 2, 0, 16, 5]
Programmation d'un tour¶
Q23¶
In [38]:
def deplacer_graines(plateau,case):
"""case choisie en entrée, cas de fin en retour"""
nbasemer=plateau[case]
case_seme=case
plateau[case]=0
while nbasemer>0:
case_seme=(case_seme+1)%12
if case==case_seme:
case_seme=(case_seme+1)%12
plateau[case_seme]=plateau[case_seme]+1
nbasemer=nbasemer-1
return case_seme
In [39]:
testjeu['plateau']
Out[39]:
[2, 1, 0, 1, 0, 1, 0, 0, 2, 0, 16, 5]
In [40]:
deplacer_graines(testjeu['plateau'],5)
Out[40]:
6
In [41]:
testjeu['plateau']
Out[41]:
[2, 1, 0, 1, 0, 0, 1, 0, 2, 0, 16, 5]
Q24¶
In [42]:
def case_ramassable(plateau,case):
return (plateau[case]==2 or plateau[case]==3) and case>5
In [43]:
case_ramassable(testjeu['plateau'],8)
Out[43]:
True
Q25¶
In [44]:
def ramasser_graines(plateau,case):
if not case_ramassable(plateau,case): # cas de base
return 0
gain = plateau[case] # cas général
plateau[case] = 0
return gain + ramasser_graines(plateau, case-1)
# ou, sans distinguer le cas de base
def ramasser_graines(plateau,case):
gain = 0 # valeur pour le cas de base
if case_ramassable(plateau,case): # cas général
gain = plateau[case] # cas général
plateau[case] = 0
gain = gain + ramasser_graines(plateau, case-1)
return gain
In [45]:
plateautest=[0,0,2,0,16,6,2,2,2,2,2,2]
In [46]:
ramasser_graines(plateautest,11)
Out[46]:
12
In [47]:
plateautest
Out[47]:
[0, 0, 2, 0, 16, 6, 0, 0, 0, 0, 0, 0]
III. Programmation du jeu¶
Q26¶
In [48]:
def test_famine(plateau,case):
copieplateau = plateau[:] # copie superficielle
derniere_case = deplacer_graines(copieplateau, case)
ramasser_graines(copieplateau, derniere_case)
for case in range(6,12):
if copieplateau[case] != 0:
return False
return True
In [49]:
plateautest=[0,0,2,0,16,6,2,2,2,2,2,2]
In [50]:
test_famine(plateautest,5)
Out[50]:
True
Q27¶
In [51]:
def test_case(plateau,case):
condition3 = test_famine(plateau,case)
test= not condition3 and plateau[case]!=0 and case<6
return test
In [52]:
test_case(plateautest,5)
Out[52]:
False
Q28¶
In [53]:
def cases_possibles(jeu:dict)->list:
possible_case = []
for case in range(6):
if test_case(jeu['plateau'], case):
possible_case.append(case)
return possible_case
In [54]:
testjeu
Out[54]:
{'joueur1': 'Alice',
'joueur2': 'Bob',
'score': [0, 0],
'n': 0,
'plateau': [2, 1, 0, 1, 0, 0, 1, 0, 2, 0, 16, 5]}
In [55]:
cases_possibles(testjeu)
Out[55]:
[0, 1, 3]
Q29¶
In [56]:
def tour_suivant(jeu:dict)->bool:
if jeu['score'][0]>=25 or jeu['score'][1]>=25:
return False
elif jeu['n']>=100:
return False
elif 4*12-jeu['score'][0]-jeu['score'][1]<4:
return False
elif len(cases_possibles(jeu))==0:
return False
else:
return True
In [57]:
tour_suivant(testjeu)
Out[57]:
True
Q30¶
In [58]:
def tour_jeu(jeu,case):
plateau = jeu['plateau']
if test_case(plateau,case): # la case jouée est acceptable
casefin = deplacer_graines(plateau,case) # Instruction1
graines_gagnees = ramasser_graines(plateau,casefin) # Instruction 2
if tour_joueur1(jeu): # condition 1
jeu['score'][0] = jeu['score'][0] + graines_gagnees
else:
jeu['score'][1] = jeu['score'][1] + graines_gagnees
jeu['n'] = jeu['n'] + 1 # instruction 3
tourner_plateau(jeu)
return tour_suivant(jeu)
print("La case choisie n'est pas valable")
return True
Q31¶
In [59]:
def gagnant(jeu:dict)->str:# signifie que tour suivant à renvoyer False
case05=0
case611=0
for case in range(6):
case05 = case05 + jeu['plateau'][case]
for case in range(6,12):
case611 = case611 + jeu['plateau'][case]
if tour_joueur1(jeu):
jeu['score'][0] = jeu['score'][0] + case05
jeu['score'][1] = jeu['score'][1] + case611
else:
jeu['score'][1] = jeu['score'][1] + case05
jeu['score'][0] = jeu['score'][0] + case611
if jeu['score'][1] == jeu['score'][0]:
return "égalité"
elif jeu['score'][0] > jeu['score'][1]:# joueur 1 gagne
return jeu['joueur1']
else:
return jeu['joueur2']
On teste sur une partie ?¶
In [60]:
def affiche(data): # NON demandée
"""Data peut être le jeu ou le plateau"""
if isinstance(data, dict):
jeu = data
plateau = jeu['plateau']
j1 = jeu['joueur1'] + " (" + str(jeu['score'][0]) + ")"
j2 = jeu['joueur2'] + " (" + str(jeu['score'][1]) + ")"
h = "n=" + str(jeu['n']) + "\t"
if tour_joueur1(jeu):
h = h + j2 + "\n"
fin = "\n\t" + j1
else:
h = h + j1 + "\n"
fin = "\n\t" + j2
else:
plateau = data
h, fin = '', ''
b = ''
for i in range(6):
h = h + "\t" + str(plateau[11-i])
b = b + "\t" + str(plateau[i])
print("\n" + h + "\n" + b + fin)
In [61]:
testjeu=initialisation('Alice','Bob')
affiche(testjeu)
n=0 Bob (0) 4 4 4 4 4 4 4 4 4 4 4 4 Alice (0)
In [62]:
def awale_jcj(nom_joueur1:str, nom_joueur2:str)->str:
jeu = initialisation(nom_joueur1, nom_joueur2)
jeu_continue = True
while jeu_continue:
affiche(jeu)
case_choisie = int(input("Choisir une case : "))
jeu_continue = tour_jeu(jeu, case_choisie)
affiche(jeu)
return gagnant(jeu)
In [64]:
awale_jcj('Prof', 'étudiant_PCSI1')
n=0 étudiant_PCSI1 (0) 4 4 4 4 4 4 4 4 4 4 4 4 Prof (0)
n=1 Prof (0) 0 4 4 4 4 4 5 5 5 5 4 4 étudiant_PCSI1 (0)
n=2 étudiant_PCSI1 (0) 5 5 6 6 6 0 4 4 4 4 4 0 Prof (0)
n=3 Prof (0) 1 0 4 4 4 4 1 7 7 6 5 5 étudiant_PCSI1 (0)
n=4 étudiant_PCSI1 (0) 6 6 7 8 0 1 5 5 5 4 0 1 Prof (0)
n=5 Prof (2) 0 0 4 5 5 5 0 0 8 7 6 6 étudiant_PCSI1 (0)
n=6 étudiant_PCSI1 (0) 7 7 8 0 0 0 6 6 6 5 1 0 Prof (2)
n=7 Prof (2) 1 2 0 6 6 6 1 1 1 8 7 7 étudiant_PCSI1 (0)
n=8 étudiant_PCSI1 (0) 0 7 8 1 1 2 7 7 7 1 3 2 Prof (2)
n=9 Prof (9) 3 4 2 8 0 7 0 0 0 8 7 0 étudiant_PCSI1 (0)
n=10 étudiant_PCSI1 (0) 1 8 0 0 0 0 8 1 9 3 5 4 Prof (9)
n=11 Prof (11) 5 6 4 0 1 8 1 1 1 1 9 0 étudiant_PCSI1 (0)
n=12 étudiant_PCSI1 (0) 1 0 1 1 2 2 9 2 1 5 7 6 Prof (11)
n=13 Prof (21) 7 8 6 2 3 0 0 0 0 0 0 1 étudiant_PCSI1 (0)
n=14 étudiant_PCSI1 (0) 0 0 0 0 0 0 1 3 2 6 8 7 Prof (21)
n=15 Prof (21) 0 8 6 2 3 2 1 1 1 1 1 1 étudiant_PCSI1 (0)
n=16 étudiant_PCSI1 (0) 2 0 1 1 1 1 2 3 2 6 8 0 Prof (21)
n=17 Prof (29) 1 9 0 2 3 2 0 0 0 0 0 2 étudiant_PCSI1 (0)
Out[64]:
'Prof'
In [ ]: