Aller au contenu

Extremum☘

Important

Les algorithmes et programmes de cette page sont considérés comme des algorithmes de référence.
Vous devez parfaitement les maîtriser et être capables de redonner leur code très rapidement.

Maximum☘

Écrire le code possible pour le corps de la fonction suivante:

def elementMax(liste):
    """
    liste -- liste d'entiers

    renvoie la valeur du plus grand élément contenu dans liste.
    """

Pour tester votre fonction

Lorsqu'on veut tester une fonction générique sur les listes, il est intéressant de générer au hasard des listes à tester.
Pour cela, on peut utiliser le module random.

Ici, on utilisera plus particulièrement la fonction randint: si a et b sont deux entiers (a ≤ b), randint(a,b) tire au hasard un entier entre a et b (a et b compris).

from random import randint

# liste de 10 éléments choisis au hasard entre 2 et 8 (au sens large)
a = [randint(2,8) for i in range(10)]
Principe

On utilise une variable pge destinée à recevoir la plus grande valeur présente dans la liste. Cette variable va parcourir la liste.

L'idée est de faire en sorte qu'à chaque étape, la variable pge ait pour valeur la plus grande valeur des éléments déjà parcourus.
En fin de liste, pge sera égal à la plus grande valeur des éléments déjà parcourus, mais comme en fin de liste on les aura tous parcourus, pge sera égal à la plus grande valeur contenue dans la liste.

Pour que la propriété « pge a pour valeur la plus grande valeur des éléments déjà parcourus» soit satisfaite après chaque étape, on procède comme suit:

  • On initialise pge par pge ← liste[0] (à ce stade, pge n'a parcouru que l'élément d'indice 0 de la liste et vaut donc la plus grande valeur des éléments déjà parcourus).
  • Ensuite, pge parcourt les éléments de la liste (dans l'ordre des indices) et à chaque fois que la valeur rencontrée est plus grande que pge, cette valeur devient la nouvelle valeur de pge (ainsi la propriété « pge a pour valeur la plus grande valeur des éléments déjà parcourus» est conservée).
Un code possible
def elementMax(liste):
    """
    liste -- liste d'entiers

    renvoie la valeur du plus grand élément contenu dans liste.
    """
    pge = liste[0] # pge sera le plus grand élément
    for element in liste:
        if element > pge: pge = element
        # à ce stade pge est le plus grand des éléments déjà vus
    return pge

Exemples et tests: fichier ipynb (version html).

Indice du maximum☘

Écrire le code possible pour le corps de la fonction suivante:

def indicePremiereOccurrenceElementMax(liste):
    """
    liste -- liste d'entiers, non vide

    renvoie l'indice de la première occurrence
    du plus grand élément contenu dans liste.
    >>> indicePremiereOccurrenceElementMax([3, 4, 5, 3, 4, 5])
    2
    """
Indication

On procède essentiellement comme dans l'algorithme précédent, mais on maintient en plus à jour une variable indice_du_max lors du parcours.

Un code possible
def indicePremiereOccurrenceElementMax(liste):
    """
    liste -- liste d'entiers, non vide

    renvoie l'indice de la première occurrence
    du plus grand élément contenu dans liste.
    >>> indicePremiereOccurrenceElementMax([3, 4, 5, 3, 4, 5])
    2
    """
    assert liste != [], "Attention, liste doit être non vide."
    pge = liste[0] # pge sera le plus grand élément
    indicePge = 0 # indice du pge
    for indice, element in enumerate(liste):
        if element > pge: 
            pge = element
            indicePge = indice
    return indicePge

Indice du maximum, bis☘

Écrire le code possible pour le corps de la fonction suivante:

def indiceDerniereOccurrenceElementMax(liste):
    """
    liste -- liste d'entiers, non vide

    renvoie l'indice de la dernière occurrence
    du plus grand élément contenu dans liste.
    >>> indiceDerniereOccurrenceElementMax([3, 2, 6, 3, 4, 6])
    5
    """
Indication

Pour ne retenir que la première occurrence, on a mis à jour dans l'exercice précédent que si l'on rencontrait une valeur strictement plus grande que pge. Pour obtenir l'indice de la dernière occurrence, il suffit de remplacer cette comparaison stricte > par une comparaison large >=.

Un code possible

Vous veillerez à être sûr d'avoir bien saisi pourquoi il suffit de remplacer >
par >= pour obtenir l'indice de la dernière occurrence au lieu de l'indice de la première occurrence.

def indiceDerniereOccurrenceElementMax(liste):
    """
    liste -- liste d'entiers, non vide

    renvoie l'indice de la dernière occurrence
    du plus grand élément contenu dans liste.
    >>> indiceDerniereOccurrenceElementMax([3, 2, 6, 3, 4, 6])
    5
    """
    assert liste != [], "Attention, liste doit être non vide."
    pge = liste[0] # pge sera le plus grand élément
    indicePge = 0 # indice du pge
    for indice, element in enumerate(liste):
        if element >= pge: 
            pge = element
            indicePge = indice
    return indicePge

Minimum☘

Écrire un code possible pour le corps de la fonction suivante:

def indicePremiereOccurrenceElementMin(liste):
    """
    liste -- liste d'entiers, non vide

    renvoie l'indice de la première occurrence
    du plus petit élément contenu dans liste.
    >>> indicePremiereOccurrenceElementMin([3, 2, 6, 3, 2, 6])
    1
    """
Un code possible
def indicePremiereOccurrenceElementMin(liste):
    """
    liste -- liste d'entiers, non vide

    renvoie l'indice de la première occurrence
    du plus petit élément contenu dans liste.
    >>> indicePremiereOccurrenceElementMin([3, 2, 6, 3, 2, 6])
    1
    """
    assert liste != [], "Attention, liste doit être non vide."
    ppe = liste[0] # ppe sera le plus petit élément
    indicePpe = 0 # indice du ppe
    for indice, element in enumerate(liste):
        if element < ppe: 
            ppe = element
            indicePpe = indice
    return indicePpe

Nombre d'occurrences du minimum☘

Écrire le code possible pour le corps de la fonction suivante:

def nb_occ_min(liste):
    """
    liste -- liste d'entiers

    renvoie le couple (minimum, nombre d'occurrences du minimum)
    >>> nb_occ_min([4, 6, 7, 4, 9, 4])
    (4, 3)
    >>> nb_occ_min([4, 6, 7, 4, 9, 4, 2])
    (2, 1)
    """
Un code possible
def nb_occ_min(liste):
    """
    liste -- liste d'entiers

    renvoie le couple (minimum, nombre d'occurrences du minimum)
    >>> nb_occ_min([4, 6, 7, 4, 9, 4])
    (4, 3)
    >>> nb_occ_min([4, 6, 7, 4, 9, 4, 2])
    (2, 1)
    """
    compteur = 0
    mini = liste[0]
    for element in liste:
        if element < mini:
            mini = element
            compteur = 1
        elif element == mini:
            compteur += 1
        else:
            pass
    return (mini, compteur)
Un autre code

On peut aussi d'abord calculer le minimum puis déterminer son nombre d'occurrences:

def mini(liste):
    """
    liste -- liste d'entiers

    renvoie le minimum de la liste
    """
    m = liste[0]
    for x in liste:
        if x < m:
            m = x
    return m

def nb_occ_mini(liste):
    """
    liste -- liste d'entiers

    renvoie le couple (minimum, nombre d'occurrences du minimum)
    >>> nb_occ_mini([4, 6, 7, 4, 9, 4])
    (4, 3)
    >>> nb_occ_mini([4, 6, 7, 4, 9, 4, 2])
    (2, 1)
    """
    m = mini(liste)
    compteur = 0
    for x in liste:
        if x == m:
            compteur += 1
    return (m, compteur)

On parcourt ainsi deux fois la liste complète tandis qu'avec le code précédent, on ne la parcourt qu'une seule fois. Il y a donc dans le premier code un gain de temps à l'exécution qui peut ne pas être négligeable si l'on traite un grand nombre de données et/ou si l'on a besoin fréquemment de cette recherche du nombre d'occurrences du minimum.