31 janvier 2022
Cette collection de notes est mise à disposition selon les termes de la Licence Creative Commons Attribution - Pas d’Utilisation Commerciale - Partage dans les Mêmes Conditions 2.0 France.
Se trouve sur la page https://eduscol.education.fr/2661/banque-des-epreuves-pratiques-de-specialite-nsi, dans https://eduscol.education.fr/document/33187/download
Sujet résumé : Exemples fournis
>> recherche([1, 4, 3, 5])
[]>>> recherche([1, 4, 5, 3])
4, 5)]
[(>>> recherche([7, 1, 2, 5, 3, 4])
1, 2), (3, 4)]
[(>>> recherche([5, 1, 2, 3, 8, -5, -4, 7])
1, 2), (2, 3), (-5, -4)] [(
Remarque : le nom recherche
n’est pas particulièrement bien choisi, comme expliqué dans un corrigé précédent. On fera avec.
Bien réfléchir aux termes employés :
(liste[i], liste[i+1])
pour un certain entier i
(n, n+1)
.On peut se demander si un couple (n+1, n)
est acceptable : c’est réfuté par le premier exemple, le couple (4,3)
ne fait pas partie du résultat.
La fonction sera de la forme
def recherche(liste):
...
Une solution évidente est de parcourir tous les couples de nombres voisins, et de stocker dans une liste resultat
ceux qui nous conviennent.
Pour parcourir l’ensemble de ces couples, on peut faire varier i
de 0 à len(liste) - 2
:
def recherche(liste):
= []
resultat for i in range(0, len(liste) - 1): # attention
if liste[i] + 1 == liste[i+1] :
+1]))
resultat.append((liste[i], liste[ireturn resultat
ou de 1
à len(liste) - 1
, avec un décalage d’indices
def recherche(liste):
= []
resultat for i in range(1, len(liste)):
if liste[i-1] + 1 == liste[i] :
-1], liste[i])) resultat.append((liste[i
Pour travailler sur un sujet d’examen, un environnement de test facilite la vie, en permettant de vérifier que les résultats obtenus sont bien ceux présentés dans le sujet
def test(liste):
print ("recherche(" + str(liste) + ") = " \
+ str(recherche(liste)))
1, 4, 3, 5])
test([1, 4, 5, 3])
test([7, 1, 2, 5, 3, 4])
test([5, 1, 2, 3, 8, -5, -4, 7]) test([
Affichage à l’exécution
recherche([1, 4, 3, 5]) = []
recherche([1, 4, 5, 3]) = [(4, 5)]
recherche([7, 1, 2, 5, 3, 4]) = [(1, 2), (3, 4)]
recherche([5, 1, 2, 3, 8, -5, -4, 7]) = [(1, 2), (2, 3), (-5, -4)]
La solution ci-dessous est plus proche de l’analyse du problème : produire une liste des couples, puis sélectionner.
def recherche(liste):
= [ (liste[i-1], liste[i]) for i in range(1, len(liste))]
couples return [ (a,b) for (a,b) in couples if a+1 == b ]
on peut aussi combiner les deux
def recherche(liste):
return [ (liste[i-1], liste[i])
for i in range(1, len(liste))
if liste[i-1] + 1 == liste[i]
]
def propager(M, i, j, val):
if M[i][j]== ...: # 1
return
=val
M[i][j]
# l'élément en haut fait partie de la composante
if ((i-1) >= 0 and M[i-1][j] == ...): # 2
-1, j, val)
propager(M, i
# l'élément en bas fait partie de la composante
if ((...) < len(M) and M[i+1][j] == 1): # 3
# 5
propager(M, ..., j, val)
# l'élément à gauche fait partie de la composante
if ((...) >= 0 and M[i][j-1] == 1): # 5
# 6
propager(M, i, ..., val)
# l'élément à droite fait partie de la composante
if ((...) < len(M) and M[i][j+1] == 1): # 7
# 8 propager(M, i, ..., val)
Remarque ; le sujet oublie de préciser que le tableau est carré. On le déduit du fait qu’en 3, on compare la coordonnée verticale avec len(M)
pour tester si on peut aller vers le bas, et en 7 la coordonnée horizontale pour aller à droite.
On pourrait avoir un tableau simplement rectangulaire, et dans ce cas la comparaison 6 se ferait avec len(M[i])
.
Mauvaise rédaction : “Une composante d’une image est un sous-ensemble de l’image constitué uniquement de 1 et de 0” : l’emploi du masculin implique de c’est le sous-ensemble qui est composé de 0 et de 1. Mais le dessin montre qu’une composante est composée soit de
zéros, soit de
uns.
Il s’agit d’un algorithme de “flooding”. Il faut repeindre la composante qui commence à un certain endroit et est marquée par des 1.
Algorithme : Pour repeindre à partir d’un certain endroit
if M[i][j] == 0: # 1
)if ((i-1) >= 0 and M[i-1][j] == 1):
(i-1,j)
, à gauche (i,j-1)
et à droite (i, j+1)
:
propager
Code, en enlevant les parenthèses inutiles qui encadrent les conditions, et en remplaçant les commentaires trompeurs :
def propager(M, i, j, val):
if M[i][j] == 0:
return
= val
M[i][j]
# haut
if (i-1) >= 0 and M[i-1][j] == 1 :
-1, j, val)
propager(M, i
# bas
if (i+1) < len(M) and M[i+1][j] == 1 :
+1, j, val)
propager(M, i
# gauche
if (j-1) >= 0 and M[i][j-1] == 1 :
-1, val)
propager(M, i, j
# droite
if (j+1) < len(M) and M[i][j+1] == 1 :
+1, val) propager(M, i, j