3. Maximum et minimum⚓︎
La plupart des algorithmes de recherche de maximum ou de minimum sont basés sur le principe suivant :
- On initialise une variable
maxi
oumini
suivant le contexte - On parcourt les éléments à comparer en remplaçant le
maxi
(oumini
) si nécessaire
3.1 Maximum et minimum d'une liste d'entiers⚓︎
Écrire une fonction extremum(liste)
qui renvoie le maximum et le minimum des éléments de la liste sous forme d'un tuple (maxi , mini)
, sans bien sûr utiliser les fonctions min
et max
de python
Cette fonction devra passer les tests suivants:
assert extremum([1,-2,12,5,54,-10]) == (-10,54)
assert extremum([]) == 'liste vide'
A
Z
3.2 Un tableau de tuples⚓︎
Écrire une fonction maximum1(tableau)
qui renvoie le tuple dont le second élément est le plus grand.
Cette fonction devra passer les tests suivants:
assert extremum([(12,-5),(5,13),(-9,15),(0,0)]) == (-9,15)
assert extremum([]) == 'liste vide'
A
Z
3.3 Un dictionnaire⚓︎
On considère le dictionnaire suivant, dont les clés sont des noms d'élèves et les valeurs des notes.
classe = {"gérard":[12,8,6,15],
"louis":[17,5,12],
"sylvie":[2,18,15,13],
"mariane":[12,13,7,10]}
maximum2(classe)
qui renvoie l'élève qui a la meilleure moyenne et sa moyenne sous forme de tuple, le résultat attendu est ('sylvie', 12.0)
A
Z
Recherche d'éléments dans un tableau
3.4 Recherche d'un élément dans un tableau non trié⚓︎
La recherche d'un objet dans un tableau, consiste à parcourir le tableau et à renvoyer True
si l'objet est trouvé et False
sinon.
Écrire une fonction recherche1(tab,element)
qui renvoie True
si l'élément est présent dans le ntableau et False
sinon
Cette fonction devra passer les tests suivants:
assert recherche1([1,-2,5,-4,0,10,45],0) == True
assert recherche1([1,-2,5,-4,0,10,45],2) == False
assert recherche(['lapin','autruche','castor','chat','chien'],'chien') == True
assert recherche1([],0) == 'tableau vide'
A
Z
3.5 Recherche dans un tableau trié⚓︎
On utilise ici l'algorithme de recherche par dichotomie, copier-coller le code à compléter ci-dessous et compléter-le.
def recherche2(tab,element):
debut = ...
fin = ...
while debut <= ...:
milieu = (.......)//2
if tab[milieu] == .....:
return ....
else:
if ......:
fin = milieu - 1
else:
debut = milieu + 1
return False
t =[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14]
assert recherche2(t,-1) == False
assert recherche2(t,0) == True
assert recherche2(t,7) == True
assert recherche2(t,14) == True
assert recherche2(t,15) == False
A
Z
Pour le 3.6 et 3.7, on n'utilisera ni la fonction index, ni la fonction find.
Rappel
On peut parcourir les tableaux(liste) et les chaînes de caractères par leur indices:
ma_chaine = 'ceci est un exmple'
for i in range(len(ma_chaine)):
print(machaine[i])
# affiche toutes les lettre de ma_chaine
3.6 Indice de la première occurrence⚓︎
Écrire une fonction indice
qui prend en paramètres element
un nombre entier, tableau
un tableau de nombres entiers, et qui renvoie l'indice de la première occurrence de element
dans tableau
.
La fonction devra renvoyer None
si element
est absent de tableau
# Exemple
indice(1, [10, 12, 1, 56])
#affiche
2
indice(1, [1, 50, 1])
#affiche
0
indice(15, [8, 9, 10, 15])
#affiche
3
indice(1, [2, 3, 4])
#affiche
None
Cette fonction devra passer les tests suivants:
assert indice(1, [10, 12, 1, 56]) == 2
assert indice(1, [1, 50, 1]) == 0
assert indice(15, [8, 9, 10, 15]) == 3
assert indice(1, [2, 3, 4]) is None
A
Z
3.7 Occurrences d'un caractère dans un mot⚓︎
Écrire une fonction compte_occurrences
qui prend en paramètres cible
, un caractère (une chaine de caractères de longueur 1), et mot
, une chaine de caractères, et qui renvoie le nombre d'occurrences de cible
dans mot
; c'est-à-dire le nombre de fois où cible
apparait dans mot
.
On n'utilisera pas la méthode count
.
Cette fonction devra passer les tests suivants:
assert compte_occurrences("o", "bonjour") == 2
assert compte_occurrences("a", "abracadabra") == 5
assert compte_occurrences("i", "abracadabra") == 0
A
Z