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/33193/download
Sujet : Écrire une fonction maxi
qui prend en paramètre une liste tab
de nombres entiers et qui renvoie un couple donnant le plus grand élément de cette liste ainsi que l’indice de la première apparition de ce maximum dans la liste.
Exemple
>>> maxi([1,5,6,9,1,2,3,7,9,8])
(9,3)
Problèmes :
tab
une liste ?maxi
sur une liste vide.Le calcul se fait en posant un résultat provisoire (valeur du minimum et de son indice), et en l’améliorant en utilisant les éléments suivants)
range()
“Du coup”, le range
peut démarrer à 1, puisque l’indice 0 a déjà été pris en compte
def maxi(tab):
= tab[0]
valeur_maxi = 0
indice_maxi for i in range(1, len(tab)):
if tab[i] > valeur_maxi:
= tab[i]
valeur_maxi = i
indice_maxi return (valeur_maxi, indice_maxi)
Ca serait mieux en renommant tab
en liste
, mais pour un examen, il vaut mieux s’en tenir à l’énoncé.
Si on tient traiter le cas de la liste vide, il faut expliciter le choix qui est fait, parce que la spécification d’origine ne permet pas de le supposer. Exemple
# Cette fonction retourne un couple (etc)
# La fonction retourne None (résultat = absence de couple)
# si la liste est vide
def maxi(tab):
if len(maxi) == 0:
return None
...
Quand on programme, on commet des erreurs, que l’on détecte en faisant passer des tests.
C’est parfaitement normal de commettre des erreurs, mais c’est agaçant. Et faire passer des tests pour vérifier, c’est fatigant. Le résultat, c’est qu’on a tendance à ne pas les faire sérieusement, parce que
Une solution à ce problème de psychologie du travail est d’automatiser autant que possible le passage des tests.
Un exemple simple, dans ce cas :
def verifier_maxi(tab, attendu):
print ("# appel maxi(" + str(tab) + ")")
print ("- résultat attendu = " + str(attendu))
print ("- resultat obtenu = " + str(maxi(tab)))
# tests
1,5,6,9,1,2,3,7,9,8], (9,3))
verifier_maxi([5, 1, 2, 3], (5, 0)) #cas du premier
verifier_maxi([5, 1, 2, 5], (5, 0)) #cas du premier
verifier_maxi([11, 22, 33], (33, 2)) #cas du dernier verifier_maxi([
Dans l’appel à verifier_maxi
, on fournit
La fonction verifier_maxi
affiche les deux, ainsi que le résultat obtenu, dans un format qui facilite les vérifications. Exécution :
# appel maxi([1, 5, 6, 9, 1, 2, 3, 7, 9, 8])
- résultat attendu = (9, 3)
- resultat obtenu = (9, 3)
# appel maxi([5, 1, 2, 3])
- résultat attendu = (5, 0)
- resultat obtenu = (5, 0)
# appel maxi([5, 1, 2, 5])
- résultat attendu = (5, 0)
- resultat obtenu = (5, 0)
# appel maxi([11, 22, 33])
- résultat attendu = (33, 2)
- resultat obtenu = (33, 2)
On peut aussi prévoir l’affichage d’un message ERREUR
bien visible si les résultats obtenus et attendus diffèrent.
Sujet résumé : compléter le code suivant pour qu’il indique si une chaîne (gene
) apparaît dans
def recherche(gene, seq_adn):
= len(seq_adn)
n = len(gene)
g = ... # 1
i = False
trouve while i < ... and trouve == ... : # 2
= 0
j while j < g and gene[j] == seq_adn[i+j]:
# 3
... if j == g:
= True
trouve # 4
... return trouve
Notes
g
pour la longueur de gene
, mais ça ne paraît pas cohérent avec n
pour la longueur de seq_adn
.trouve
devrait être un booléen (on lui affecte True
et False
), la comparaison “trouve == ...
” sent assez mauvais…Le plus simple est de repartir d’une description du résultat attendu :
on dit que la chaîne
a
est dans la chaîneb
si il existe un indicei
tel quea[0]==b[i]
,a[1]==b[i+1]
, etc.
en allant jusqu’à la fin de a
, c’est à dire
a[j]==b[i + j]
, pour toutj
de 0 à len(a)-1`
Il faut aussi tenir compte du fait que l’indice i+j
doit être valide dans b
, c’est à dire inférieur où égal à len(b)-1
De ces inégalités, on conclut que i
doit être entre 0 et len(b)-len(a)
compris.
Exemple : si les chaînes a
et b
sont respectivement de tailles 3 et 8, la dernière position possible pour a[0]
est i
= 5, a
occuperait alors les positions d’indice 5, 6 et 7 dans b
:
Identifions cette analyse et le code à trous.
La boucle while
intérieure :
j
suivant j += 1 # 3
j
a atteint la longueur de gene
, la chaine seq_adn
contenait bien une copie de gene
, à partir de l’indice i
La boucle while
extérieure :
gene
;i
:
n-g
est dépasséei
, c’est si on a trouvé.En se conformant strictement à l’énoncé, on obtient
def recherche(gene, seq_adn):
= len(seq_adn)
n = len(gene)
g = 0 # 1
i = False
trouve while i < n-g+1 and trouve == False : # 2
= 0
j while j < g and gene[j] == seq_adn[i+j]:
+= 1 # 3
j if j == g:
= True
trouve += 1 # 4
i return trouve
On obtient une solution plus propre en appliquant quelques recettes de nettoyage
a
, b
pour les chaînes,la
et lb
pour leurs longueurs, ia
et ib
pour les indices.not
au lieu de comparaison par ==
)if
# retourne True si et seulement si la chaîne a
# apparait dans la chaîne b
def est_contenue_dans(a, b):
= len(a)
la = len(b)
lb = 0 # 1
ib = False
trouve while ib <= lb-la and not(trouve) # 2
= 0
ia while ia < la and a[ia] == b[ib+ia]:
+= 1 # 3
ia = (ia == la)
trouve += 1 # 4
ib return trouve
Une des règles d’or de la programmation est de se simplifier la vie en découpant en fonctions qui font peu de choses, mais le font bien.
def est_contenue_dans(a, b):
for ib in range(len(b)-len(a)+1):
if est_contenu_a_la_position(a, b, ib):
return True
return False
def est_contenu_a_la_position(a, b, ib):
if i+len(a) > len(b): # précaution
return False
for ia in range(len(a)):
if a[ia] != b[ib+ia]:
return False
return True