Sujet
Corrigé
Question 1
def mur(laby, i, j):
return laby[i][j] == 1Question 2a
Si les deux cases données en paramètres sont sur la même ligne,
>> alors l1 et l2 sont identiques et donc l1 - l2 vaut 0 ;
>> si les deux cases sont adjacentes, c1 - c2 vaudra -1 ou +1 selon que case1 précède ou succède à case2.
Mais dans tous les cas on obtiendra 1 en élevant c1 - c2 au carré. Et donc le test d == 1 renverra True.
>> si les deux cases ne sont pas adjacentes, c1 - c2 sera inférieur à -1 ou supérieur à +1 selon que case1 précède ou succède à case2.
Mais dans tous les cas on obtiendra une valeur supérieure à 1 en élevant c1 - c2 au carré. Et donc le test d == 1 renverra False.
Donc si les deux cases sont situées sur la même ligne, la fonction ne renvoie 'True' que si les deux cases sont adjacentes.
Si les deux cases données en paramètres sont sur la même colonne,
>> alors c1 et c2 sont identiques et donc c1 - c2 vaut 0 ;
>> si les deux cases sont adjacentes, l1 - l2 vaut -1 ou +1 selon que case1 est au dessus ou en dessous de case2.
Mais dans tous les cas on obtiendra 1 en élevant l1 - l2 au carré. Et donc le test d == 1 renverra True.
>> si les deux cases ne sont pas adjacentes, l1 - l2 sera inférieur à -1 ou supérieur à +1 selon que case1 est au dessus ou en dessous de case2.
Mais dans tous les cas on obtiendra une valeur supérieure à 1 en élevant l1 - l2 au carré. Et donc le test d == 1 renverra False.
Donc si les deux cases sont situées sur la même colonne, la fonction ne renvoie 'True' que si les deux cases sont adjacentes.Question 2b
def adjacentes(cases):
"""Vérifie si toutes les cases d'une liste sont adjacentes
Parameters
----------
cases : LIST
liste de cases sous la forme de tuples.
Returns
-------
adj : BOOL
True si toutes les cases de 'cases' sont adjacentes, sinon False.
"""
ind = 0 # index d'un case dans la liste 'cases'
adj = True
while adj and ind < len(cases) - 1:
adj = voisine(cases[ind], cases[ind + 1])
ind += 1
return adjQuestion 3
def teste(cases, laby):
if not adjacentes(cases):
return False
possible = True
i = 0
while i < len(cases) and possible:
if mur(laby, cases[i][0], cases[i][1]):
possible = False
i = i + 1
return possibleD'une façon générale, le bloc d'instructions d'une boucle 'while' est exécuté tant que la condition indiquée reste vraie : 'Tant que (Condition est vraie), Faire...'
Or dans le cas de la boucle 'while' de la fonction 'teste', cette condition est définie par deux tests liés par un opérateur booléen "and" (ET). Donc pour que cette condition soit vraie il faut que les deux tests renvoient 'vrai'.| Test 1 : ‘i < len(cases)’ | Test 2 : ‘possible (is True)’ | Condition de la boucle While | Conséquence |
| Vrai | Vrai | Vraie | Exécution du bloc d’instructions |
| Vrai | Faux | Fausse | Sortie de boucle |
| Faux | Vrai | Fausse | Sortie de boucle |
| Faux | Faux | Fausse | Sortie de boucle |
En ce qui concerne le test qui repose sur la valeur de 'possible' :
- A chaque tour de boucle, un test (cf ligne 7 ci-dessus) indique si la case du parcours proposé est un mur ou non.
- Si c'est un mur, alors 'possible' prend la valeur 'False' (cf ligne 8 ci-dessus) et donc le test 'possible (is True)' renvoie "Faux", ce qui entraîne une sortie de la boucle while.
- Mais si aucune des cases proposées n'est un mur alors le test 'possible (is True)' renverra toujours 'Vrai' et dans ce cas on pourrait ne jamais sortir de la boucle 'while'.Le second test repose sur la valeur de 'i' qui prend la valeur 0 avant la boucle 'while'.
- A chaque tour de boucle la valeur de 'i' est incrémentée, et quant à la valeur de 'len(cases)' elle reste constante et supérieure à zéro ;
- donc lorsque la valeur de 'i' sera égale à 'len(cases)', le test 'i < len(cases)' renverra 'Faux' ;
- et donc cela mettra un terme à l'itération.Donc quelque soit la liste de cases donnée en argument de la fonction 'teste', la boucle 'while' de cette fonction se terminera.Question 4
def echappe(cases, laby):
"""Indique si le chemin 'cases' conduit de l'entrée à la sortie de 'laby'.
Parameters
----------
cases : LIST
Liste de cases sous la forme de tuples
laby : LIST
Tableau carré représentant un labyrynthe.
Returns
-------
BOOL
True si le chemin 'cases' conduit de l'entrée à la sortie de 'laby',
sinon False.
"""
nta = len(laby) - 1 # index maxi du tableau carré
nca = len(cases) - 1 # index maxi des cases du chemin
return cases[0] == (0, 0) and cases[nca] == (nta, nta) \
and teste(cases, laby)Ressources annexes
Code Python complet
laby = [[0, 1, 1, 1, 1, 1, 1, 1, 1, 1],
[0, 0, 0, 0, 0, 0, 0, 1, 0, 1],
[1, 0, 1, 1, 1, 1, 0, 1, 0, 1],
[1, 0, 1, 0, 0, 0, 0, 0, 0, 1],
[1, 0, 1, 1, 1, 1, 1, 0, 1, 1],
[1, 0, 1, 0, 0, 0, 1, 0, 1, 1],
[1, 0, 1, 0, 1, 0, 1, 0, 1, 1],
[1, 0, 1, 1, 1, 0, 1, 0, 1, 1],
[1, 0, 0, 0, 0, 0, 1, 0, 0, 1],
[1, 1, 1, 1, 1, 1, 1, 1, 0, 0]]
def mur(laby, i, j):
return laby[i][j] == 1
def voisine(case1, case2):
l1, c1 = case1
l2, c2 = case2
# on vous rappelle que **2 signifie puissance 2
d = (l1 - l2) ** 2 + (c1 - c2) ** 2
return (d == 1)
def adjacentes(cases):
"""Vérifie si toutes les cases d'une liste sont adjacentes
Parameters
----------
cases : LIST
liste de cases sous la forme de tuples.
Returns
-------
adj : BOOL
True si toutes les cases de 'cases' sont adjacentes, sinon False.
"""
ind = 0 # index d'un case dans la liste 'cases'
adj = True
while adj and ind < len(cases) - 1:
adj = voisine(cases[ind], cases[ind + 1])
ind += 1
return adj
def teste(cases, laby):
if not adjacentes(cases):
return False
possible = True
i = 0
while i < len(cases) and possible:
if mur(laby, cases[i][0], cases[i][1]):
possible = False
i = i + 1
return possible
def echappe(cases, laby):
"""Indique si le chemin 'cases' conduit de l'entrée à la sortie de 'laby'.
Parameters
----------
cases : LIST
Liste de cases sous la forme de tuples
laby : LIST
Tableau carré représentant un labyrynthe.
Returns
-------
BOOL
True si le chemin 'cases' conduit de l'entrée à la sortie de 'laby',
sinon False.
"""
nta = len(laby) - 1 # index maxi du tableau carré
nca = len(cases) - 1 # index maxi des cases du chemin
return cases[0] == (0, 0) and cases[nca] == (nta, nta) \
and teste(cases, laby)
if __name__ == "__main__":
assert mur(laby, 2, 3) is True
assert mur(laby, 1, 8) is False
assert voisine((3, 3), (3, 4)) is True
assert voisine((3, 1), (4, 1)) is True
assert voisine((3, 1), (4, 2)) is False
assert adjacentes([(1, 4), (1, 5), (1, 6), (2, 6), (3, 6), (3, 5),
(3, 4)]) is True
assert adjacentes([(1, 6), (2, 6), (3, 6), (3, 7), (4, 7), (5, 7),
(6, 7)]) is True
assert adjacentes([(0, 0), (1, 0), (1, 1), (5, 1), (6, 1)]) is False
assert adjacentes([(3, 4), (3, 5), (3, 6), (4, 7), (5, 8)]) is False
assert teste([(1, 4), (1, 5), (1, 6), (2, 6), (3, 6), (3, 5),
(3, 4)], laby) is True
assert teste([(1, 6), (2, 6), (3, 6), (3, 7), (4, 7), (5, 7),
(5, 8)], laby) is False
cases = [(0, 0), (1, 0), (1, 1), (2, 1), (3, 1), (4, 1), (5, 1), (6, 1),
(7, 1), (8, 1), (8, 2), (8, 3), (8, 4), (8, 5), (8, 6), (8, 7),
(8, 8), (8, 9), (9, 9)]
assert echappe(cases, laby) is False
cases = [(0, 0), (1, 0), (1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (1, 6),
(2, 6), (3, 6), (3, 7), (4, 7), (5, 7), (6, 7), (7, 7), (8, 7),
(8, 8), (9, 8), (9, 9)]
assert echappe(cases, laby) is True