L’objectif de ce document est d’écrire et d’implémenter un algorithme s’appuyant sur le raisonnement « Diviser pour régner » qui permet de déterminer le maximum et le minimum des éléments dans un tableau.
- Générer une liste contenant un million de termes choisis aléatoirement entre un et mille milliards.
Réponse
1
2
3
4
|
from random import randint
if __name__ == "__main__":
tab = [randint(1, int(1e12)) for i in range(int(1e6))]
|
- Utiliser les fonctions
min
et max
fournies par le langage Python afin d’afficher les maximum et minimum dans la liste.
Réponse
1
2
3
4
|
print("Fonctions Python")
val_min, val_max = (min(tab), max(tab))
print("min = {}, max = {}".format(val_min, val_max))
|
- Écrire le code de la fonction
maxmin1
qui, à partir d’un algorithme de « brute force », détermine les maximum et minimum dans la liste passée en argument.
La spécification de la fonction est :
1
2
3
4
5
6
|
def maxmin1(tab: List[float]) -> Tuple[float, float]:
"""
Recherche du minimum et du maximum dans le tableau tab.
Paradigme « Brute force »
"""
|
Réponse
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
def maxmin1(tab: List[float]) -> Tuple[float, float]:
"""
Recherche du minimum et du maximum dans le tableau tab.
Paradigme « Brute force »
"""
val_max = tab[0]
val_min = tab[0]
for elt in tab:
if elt > val_max:
val_max = elt
if elt < val_min:
val_min = elt
return (val_min, val_max)
|
- Vérifier le bon fonctionnement de la fonction
maxmin1
en affichant les maximum et minimum dans la liste, à la suite de ceux déterminés à l’aide des fonctions fournies par Python.
Réponse
1
2
3
|
print("Recherche « Brute Force »")
val_min, val_max = maxmin1(tab)
print("min = {}, max = {}".format(val_min, val_max))
|
- Quelle est la complexité de la fonction
maxmin1
?
Réponse
Il est nécessaire de parcourir tout le tableau, la complexité est donc en $O(N)$.
[Lire]