1er février 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/33202/download
Sujet : retourner l’indice de la première occurrence d’un élément dans un tableau, -1 si il est absent
Il est naturel de penser à faire une boucle sur les indices valides. Chercher l’indice de la première valeur suggère de sortir de cette boucle, et pourquoi ne pas en profiter pour retourner l’indice ?
def recherche(element, tableau):
for i in range(len(tableau)):
if tableau[i] == element:
return i
return -1
print ("Tests")
assert recherche(1, [2, 3, 4]) == -1
assert recherche(1, [10, 12, 1, 56]) == 2
assert recherche(50, [1, 50, 1]) == 1
assert recherche(15, [8, 9, 10, 15]) == 3
print ("OK")
En prenant le problème différemment, on peut aussi faire une boucle sur les valeurs (for v in tableau
), en contrôlant manuellement un indice
def recherche(element, tableau):
= 0
indice for v in tableau:
if v == element:
return indice
+= 1
indice return -1
while
)def recherche(element, tableau):
= len(tableau)
taille = 0
indice while indice < taille and tableau[indice] != element:
+= 1
indice if indice == taille:
return -1
else:
return indice
def recherche(element, tableau):
= len(tableau)
taille = 0
indice = False
trouve while indice < taille and not trouve:
if tableau[indice] == element:
= True
trouve else:
+= 1
indice if trouve:
return indice
else:
return -1
L’affirmation péremptoire “c’est encore pire” est justifiée par la comparaison sur
pour arriver au même résultat.
Code fourni
def insere(a, tab):
= list(tab) #l contient les mêmes éléments que tab
l
l.append(a)= ... # 1
i while a < ... and i >= 0: # 2
+1] = ... # 3
l[i= a
l[i] = ... # 4
i return l
Les deux premières instructions ajoutent l’élément, au bout d’une copie de la liste fournie en paramètre.
Ca s’arrêtera de toutes facons en arrivant tout a fait à gauche, quand il n’y a plus de prédécesseur.
Prêtons attention aux indices
i
(on affecte a
à cet endroit)Les deux premières instructions du corps de boucle sont donc
+1] = l[i] # 3 décalage
l[i= a # remplissage l[i]
l[len(l) - 1]
, il faut que i+1
puisse prendre la valeur len(l)-1
. La première valeur pour i
devra donc être len(l) - 2 # 1
et bien sûr à chaque tour on va vers la gauche, en diminuant i
: i = i - 1 # 4
.
Reste la condition : si on déplace l[i]
, c’est parce qu’on a détecté qu’il n’était pas à sa place par rapport à a
, après comparaison a < l[i]
def insere(a, tab):
= list(tab) #l contient les mêmes éléments que tab
l
l.append(a)= len(l) - 2 # 1
i while a < l[i] and i >= 0: # 2
+1] = l[i] # 3
l[i= a
l[i] = i - 1 # 4
i return l
print ("Tests insertion")
assert insere(3,[1,2,4,5]) == [1, 2, 3, 4, 5]
assert insere(10,[1,2,7,12,14,25]), [1, 2, 7, 10, 12, 14, 25]
assert insere(1,[2,3,4]) == [1, 2, 3, 4]
print ("OK");